Головоломка (VSM и dimensionality reduction)

Поскольку любые три точки лежает в одной плоскости (!) использовать более чем двумерное пространство бесполезно.

О том как отобразить. Для трех точек оптимизационную задачу можно сформулировать следующим образом:

найти такие три точки, чтобы отличие попарных расстояний между ними от исходных данных было минимально в смысле какой-либо метрики.

Ответ сильно зависит от того, какую метрику вы использовали для измерения этих величин. Кстати, у вас не ясно это сходство или расстояние, это тоже важно.

Изометрически скорее всего не получится, но обычно и не надо, тем более для визуализации. Если у вас исходная метрика l_2 (т.е. эвклидова), то вам повезло и приближенно постороить вложение в то же l_2, уменьшающее размерность практически с любой точность, можно. Механизм -- лемма Джонсона-Линденштрауса (используются случайные гауссовые матрицы). При этом размерность целевого пространства для вложения нормы будет пропорциональна логарифму числа точек, расстояния между которыми необходимо сохранить в пределах и обратно пропорциональна квадрату требуемой точности. Т.е. особо надеяться уместить много точек на плоскости да и в объеме не стоит.

Более реально, что вам надо построить вложение, не зная заранее множества точек. Тогда вероятность, что расстояние между случаной парой точек искажилось уж слишком сильно, будет пропорциональной e^\Omega(d'/\epsilon^2), где d' -- требуемая размерность, \epsilon -- ошибка ((1-\epsilon)D(x,y)<=D'(x,y)<=(1+\epsilon)D(x,y))

Для неэвклидовых метрик типа l_1 вопрос сложнее. Есть результат, что такой же финт как с l_2 невозможен. Но есть вполне адекватные замены, вкладывающие не в l_1, а строящие некий скетч, вычислив по которому определенную функцию, можно оценить исходное расстояние.

Большое спасибо за ответы.

Это сходство (т.е. похожесть документов по тематике в

понятии среднестатистического человека).

Имеется в виду идеальная величина, хотя на практике мы можем, конечно, взять евклидовы расстояния между векторами имеющихся документов.

Я сейчас экспериментирую с SOM (Self Organising Map) Кохонена, и мне вот стало интересно, какая размерность должна быть у этой SOM, чтобы расставить документы с минимальными потерями. Без потерь, видимо, невозможно, я раньше пришел к тем же выводам что и Aleksey01. Если я правильно понял Ваш пост, оптимальная размерность будет логарифм от числа документов, т.е., например, log(700)=2.8 получается, небольшую коллекцию вполне реально отобразить в 3D. При этом расстояния между ними должны (по идее) отображать релевантность ближе к идеалу, чем евклидовы расстояния между входными векторами. Верно?

Со сходствами сложнее, для них меньше известно. В этой области лучше, если есть возможность, работать с метриками. Но в случае, если у вас интуитивное понятие сходства смоделировано, например, косинусом между векторами, то там тоже есть аналоги уменьшения размерности.

Насчет размерности для SOM не скажу, но у этих методов, как мне кажется, разные цели... Хотя, если задача всего лишь визуализировать небольшую коллекцию и есть основания предполагать, что документы организованы в VSM проще, чем просто любые точки (например, ложаться на какую-то поверхность или вытянуты вдоль оси), то возможно и SOM будет работать так же как и методы типа PCA. А dimensionality reduction это более мощное средство, которе применимо к целым пространствам и не зависит от конкретной коллекции. Уменьшается размерность всего пространства с равномерными гарантиями для любой пары точек, не зависимо от того как они расположены в пространстве.

Насчет размерности. Если быть точнее, то размерность вам понадобится 4*ln(n)/epsilon^2. При этом с большой вероятностью (1/n^2) расстоянием между любыми точками сохраниться в пределах (1-\epsilon)D(x,y)<=D'(x,y)<=(1+\epsilon)D(x,y). Чтобы узнать сколько это точно, вам надо задаться желаемым epsilon.

Не совсем понял. Расстояния между "уменьшеными" векторами будут удовлетворять неравенству выше с какой-то вероятностью. И все.

Если идеал -- это то сходство, которое понимается человеком, то начать лучше его отражать они могут только случайно.

Если идеал -- это эвклидово расстояние между исходными векторами, то опять же см. неравенство. В зависимости от значения epsilon они могут принимать близкие или не очень близкие значения к исходному.

А откуда эта формула и как выбирать эпсилон? Можно где-то почитать про это?

Есть такое соображение, что при уменьшении размерности тут учитываются закономерности в исходных данных, значит каким-то образом учитываются взаимодействия между словами в языке (особенно при большой входной коллекции), значит при уменьшении размерности это всё нормализуется и лингвистические факторы отфильтруются, останется только смысловая нагрузка (в данном случае в виде пространства знаний). 🚬

Формула, например, отсюда "An elementary proof of the Johnson-Lindenstrauss Lemma". Эпсилон выбираться, исходя из соображений желаемой точности. Например, вы хотите, чтобы расстояния при уменьшении размерности искажались не более, чем на 10%, значит эпсилон=0.1 .

А как такие соображения появились?:) Ведь тут помимо известной модели закономерностей еще надо знать как именно их оставить, уменьшая размерность. Т.е. врядли это верно для любого способа уменьшения размерности.

Понял, спасибо. Т.е., получается, ответ на изначальный вопрос - это возможно, но при погрешности 10% получается потребуется 4*ln(3)/0.01 = 439.44. Т.е. 439 измерений нужно чтобы спроецировать несчастные 3 точки? Правильно я посчитал? :)

Для базы Гугла потребуется (я не знаю сколько она точно, допустим 40 млрд) 4*ln(40 000 000 000)/0.01 = 9764.

Для мелких коллекций порядка 4 тыс документов это будет около 3 тыс, т.е. где-то на уровне размерности исходных векторов.

Интересно..

Доказать не могу, но, мне кажется, это логично. Как оставить - подсказывают сами данные. Например, система индексирует много документов, и там встречается: "Маша пошла по грибы", "Петя пошел по грибы", "Маша почистила зубы", "Петя почистил зубы". В ходе уменьшения размерности Маша и Петя проецируются рядом, а идти по грибы и чистить зубы - в другом месте, а расстояния между ними отражают насколько эти понятия связаны. Изначальные факторы - правила языка, человеческие знания и личные какие-то факторы автора, при большой коллекции получается мы извлекаем только знания и язык (тоже частично обусловленный знаниями).

Вообще говоря, в этом топике описан алгоритм сворачивания и сжатия данных, в терминах прикладного анализа данных (ПАД). Насколько я помню теорию, здесь можно использовать гипотезу компактности, которая выражается в том, что точки, отображающие признаки в объекте одного класса, должны быть расположены в пространстве признаков ближе друг к другу, чем к точкам, отображающим признаки объектов других классов.

Получить пространство признаков (знаний) вполне реально, если подобрать правильную метрику, то есть определить, какие признаки объекта (ключевые слова в документе) являются смысловыми.

P.S. Вообще интересный топик получился, респект.

Точно!

Спасибо, респект делим с sokoloff. Вообще это развитие моей полусерьезной темы, которую в курилку выкинули:

/ru/forum/79111

:)

> Получить пространство признаков (знаний) вполне реально

таким образом мы имеем что реально получить пространство человеческих знаний на основе анализа всех документов в WWW, так? На основе этого пространства можно считать релевантность, строить какие-то отображения в 3D/2D для броузинга, и делать кучу еще разных полезных вещей.

Ясно, что задача трудоемкая и не по зубам современным искалкам, но в перспективе решаема. В качестве метрики нужно брать, конечно, не просто ранки термов, как в классической Information Retrieval, а что-нибудь более точное вроде лексических цепочек.