Я все-таки не стал бы делать выводы для SOM, исходя из размерности, полученной по JL-лемме. Все-таки это разные вещи, может какое-то ощущение порядка величин может и могут дать для друг друга, не знаю.
Для .pdf, по крайне мере, они парсятся не в plain text. Во всяком случае, все выделения и локальные ссылки внутри документа прекрасно видны в "View as HTML". Даже если Google вместо "View as HTML" предлагает "View as Text" (для .ps), то все равно форматирование остается.
Ну 4-ка там спрятана под O(), см. формулировку Theorem 2.1
Она не теорема, а гипотеза. И выражает лишь необоснованое предположение (надежду), что они попадут рядом, если удачно подобрать признаки. Но на самом деле это не обязано быть и часто не бывает так в реальности. Если вы докажете, что выбранные признаки отображают "компактные" множества в "компактные" (т.е. близкие точки в близкие, далекие в далекие и т.д. с четким определением расстояния), то тогда это можно утверждать.
Да, и при этом это 3 любые точки. Т.е. вы как бы освобождаетесь от конкретной выборки и можете гарантировать это для любого входа.
Сложно найти адекватную неформальной задаче формальную модель исходных данных. Когда (если) она найдена, то в общем-то уменьшение размерности носит чисто технический характер и служит только лишь для экономии ресурсов (как верно отмечено, это похоже на сжатие с потерями), но без "ореола" исскуственного интелекта.
Формула, например, отсюда "An elementary proof of the Johnson-Lindenstrauss Lemma". Эпсилон выбираться, исходя из соображений желаемой точности. Например, вы хотите, чтобы расстояния при уменьшении размерности искажались не более, чем на 10%, значит эпсилон=0.1 .
А как такие соображения появились?:) Ведь тут помимо известной модели закономерностей еще надо знать как именно их оставить, уменьшая размерность. Т.е. врядли это верно для любого способа уменьшения размерности.
Со сходствами сложнее, для них меньше известно. В этой области лучше, если есть возможность, работать с метриками. Но в случае, если у вас интуитивное понятие сходства смоделировано, например, косинусом между векторами, то там тоже есть аналоги уменьшения размерности.
Насчет размерности для 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 они могут принимать близкие или не очень близкие значения к исходному.
Ответ сильно зависит от того, какую метрику вы использовали для измерения этих величин. Кстати, у вас не ясно это сходство или расстояние, это тоже важно.
Изометрически скорее всего не получится, но обычно и не надо, тем более для визуализации. Если у вас исходная метрика 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, а строящие некий скетч, вычислив по которому определенную функцию, можно оценить исходное расстояние.
Это может быть также в сторону bias detection, stream comparison/computations, outlayer detection. Но это большая область с мощным мат. аппаратом и очень сильными результатами. В магистерской можно и загрузнуть.
В более прикладной сфере -- это fraud/anomaly detection, но как данные там обычно не тексты рассматриваются.
Если руководитель таки хочет видеть какие-то аномалии, то, наверное, стоит обратить внимание на алгоритмы alignment-а, вычисления строковых метрик и способы их ускорения. Тогда можно считать, что полученная версия документа есть в каком-то смысле аномалией по отношению к исходному тексту (отредактированной в некоторых местах). Только уточните с ним, что он понимает под аномалиями, на всякий случай:)
Как вариация на тему: еще возможно определять плагиатность документов по близости в какой-нибудь из метрик редактирования (lcs, хэмминг, классической Левенштайна, с переставлениями, с передвижением/копированием/удалением/реверсией блоков, etc)
См. также различные варианты метрик на строках ( http://www.dcs.shef.ac.uk/~sam/stringmetrics.html ), но это далеко не полный список.
В общем, надо определится, что есть плагиат в вашей конкретной области и для выбранного множества входных данных.
А что (для начала, по крайне мере) мешает считать мусор отдельной рубрикой? Вопрос, конечно, сразу возникнет о разнообразии семейства разделяющих поверхностей. Но, если оно позволяет отделить "сложный" мусор, то такой подход разделит и его, и настояшие рубрики.
Да, но попытаться можно. Например, SoftSVM или пытаться угадать ядро, которые разделит классы.
