Одно из таких решений я и опишу в этой статье.
Не пытайтесь повторить эти эксперименты дома.
А если попытаетесь — то претензии по сгоревшим процессорам не принимаются.
Итак, есть датасет www.cs.cornell.edu/people/pabo/movie-review-data/review_polarity.tar.gz
Он состоит из 1000 негативных и 1000 позитивных отзывов.
Как с помощью
Очень просто.
1. Берем 100 случайных текстов (50 из негативов и 50 из позитивов)
2. Выкидываем их из датасета.
3. Для каждого из 1900 оставшихся считаем обобщенную дистанцию с каждым из 100 выкинутых следующим методом:
Пусть X и Y — два файла, для которых надо посчитать дистанцию.
И пусть Z(N) — длина файла N после сжатия его архиваторм xz.
Вычислим значения
X = Z(X)
Y = Z(Y)
XY = Z(XY)
YX = Z(YX)
Последние два значения — результат архивации конкатенации файлов X и Y в первом случае и Y и X — во втором.
И теперь считаем магическую формулу, взятую здесь
attribute = (min(XY,YX)-min(X,Y))/max(X,Y)
4. У нас получилась матрица 1900 х 100
Теперь ее надо нормализовать от 0 до 1.
5. Тадам:
$svm-train -v 10 -s 0 -t 0 -с 10 rand100.norm.svm
Cross Validation Accuracy = 75.6316%
Почему это работает?
Дело в том, что чем больше общих последовательностей в двух текстах, тем больше будет сжатие Z(XY)
Таким образом система сама выделяет общие группы символов.
Возможно что на 200 случайных файлах получилось бы лучше.
Но — помните предупреждение не повторять это дома?
Сам процесс вычисления матрицы на домашнем компьютере может занять сутки — если в одном потоке.
Или спалить процессор в мультипоточном режиме, если охлаждение слабое.
Это кстати не шутка — я так когда-то два сервера в датацентре на другом конце планеты сжег, правда другим алгоритмом еще более жестким.
И именно поэтому этот метод представляет лишь теоретический интерес в рамках прикладной фаллометрии.
PS
Кода не будет за тривиальностью — я все делал шеллом и перловыми онлайнерами, при попытке чтения которых гомосапами, архивация начинает происходить непосредственно в коре головного мозга. А нейронные сети, как известно, плохо приспособлены к такой нагрузке.
PPS
А вдохновил меня на сей эксперимент — вот этот пост.
UPDATE
Судя по отзывам, показав практическую часть, я не прояснил зачем это нужно.
В самом деле, в реальных задачах этот метод явно неприменим — затратность очень велика.
Метод вычисления дистанции компрессией известен давно и имеет под собой теоретический бэкграунд.
Желающим с ним ознакомиться рекомендую это.
Вопрос однако не в конкретном методе.
Современные аналитики строят классификаторы долго, дорого и руками.
Руками вообще делается многое — от feature sculpting до разработки структуры сети.
Здесь я показал полностью агностический метод, не требующий никаких знаний о предметной области. Вообще никаких. Нам наплевать на каком языке написано содержимое файла, единственное ограничение — это должен быть линейный поток байт (потому с изображениями не работает).
Да, пример относится к категории игрушечных, в реальных задачах такие алгоритмы бессмысленны.
Но если есть агностические методы в игрушечных задачах, то они могут существовать и в больших. И поиск таких методов намного более интересен, чем тренировки автоэнкодеров на L2 метрике.
Особенно учитывая то, что на использованной здесь NCD метрике автоэнкодер натренировать скорее всего не получится.
Комментарии (12)
MichaelBorisov
27.04.2015 23:55+1Вопрос: какого результата автор добился? Что дают полученные данные?
0decca Автор
28.04.2015 06:58+2Автор показал, что пока ведущие специалисты мира разрабатывают структуры слоев нейронных сетей или спорят о типах дистанции в автоэнкодерах — существуют полностью агностические методы, дающие сравнимый результат.
Что в свою очередь как бы намекает, что ни автоэнкодеры, ни сверточные слои, ни loss-функции не являются необходимым элементом для построения классификатора.
Вот здесь habrahabr.ru/company/meanotek/blog/256593 например конволюционка на 8 нейронах дает меньше. А на 16 — больше.
Разумеется в реальных задачах никто не делает троллейбусы из буханки черного хлеба.
Но в реальных задачах на больших данных приведение размерности к дистанциям выборки из базы — обычная практика и может быть названо deep learning для бедных.
Такой известный продукт как sofia-ml например его использует, скорость весьма впечатляет.
dcc0
28.04.2015 00:29Интересует практическое применение. Какова разница в результатах для разных языков? Для текстов разного уровня?
Что будете делать с завуалированным текстом? Метафорами, метонимиями, синекдохами, афоризмами и т.д…
Т.е. что можно, в конечном счете, решить с помощью данной модели?
Проанализировать комментарии к Mail.ru?
0decca Автор
28.04.2015 06:41Практического применения здесь нет — слишком затратен метод. Разве что использовать персональный десктоп в качестве зимнего отопления.
ServPonomarev
28.04.2015 10:40+2На самом деле метод крут. И спасибо, что обратили на него внимание. Дело в том, что полноценный разбор текста — ещё затратнее. И существенно алгоритмически сложнее.
Подобным архивированием можно из большой выборки выделять потенциально интересные сообщения, а уж их-то проверять полным разбором или даже оператором. 75% точности для первого фильтра — хороший результат.0decca Автор
28.04.2015 12:01+1Для полноценного разбора текста требуется еще и иметь языковую модель.
Которая не только разная для каждого языка, но и в пределах одного языка может сильно варьироваться.
Я как-то вытаскивал данные из сотни тысяч английских текстов, написанных индусами, китайцами и филиппинцами.
По результату пришлось писать свой экстрактор — готовые системы (коммерческие и бесплатные) давали очень плохое качество. Хотя казалось бы — где уже сделано все и все истоптано — так это в английском языке.
Поэтому агностические модели столь привлекательны — более традиционные схемы предполагают большой объем ручной адаптации, что реально дорого IRL.
Zveroloff
28.04.2015 11:40А почему бы не использовать обычный gzip? Разве метод не станет менее затратным? Для алгоритма, мне кажется, без разницы?
0decca Автор
28.04.2015 11:54Разница есть и gzip не подходит.
Вообще блочные упаковщики плохо работают для таких целей.
Проверить насколько хорош упаковщик можно простой процедурой.
cat somefile | packer >test1
cat somefile somefile | packer >test2
Если рамеры файлов test1 и test2 мало отличаются — то упаковщик подходит.
Второе требование — чем сильнее он пакует целевые файлы — тем лучше для результата.
elingur
28.04.2015 18:04Спасибо, не знал, что длина архива зависит от последовательности конкатенации файлов.
На самом деле ожидаемый результат точности. Думаю, если использовать сим-хеши для побайтового сравнения результат будет еще лучше.
Для промышленных решений такая точность маловата, но идею можно применить для предварительной классификации чего угодно. Кстати, все эти SVM и Байесы — так же методы классификации, столь популярные в русскоязычном сегменте тональности, достигают примерно такого же уровня точности или чуть лучше (все-таки там применяют всякие лингвистические эвристики типа н-грамм). Ну а чтобы получить более 90% нужна глубокая лингво информация, даже не языковая модель — что от нее толку — а грамматика и синтаксис.0decca Автор
28.04.2015 18:31Обычный Random Forest на случайных байтовых n-граммах так сразу мне показал 72.95% — без тюнинга.
При том, что быстрее Random Forest в детекции наверное ничего придумать и нельзя.
И это тоже агностический метод, количество параметров ненамного больше и знание содержимого файла не требуется — он будет работать и на классификации вирусов, спама, ДНК и чего угодно с линейной структурой и произвольной длиной.
Возможно n-граммы на словах или на синсетах покажут лучший результат, но они уже преполагают текст, причем на европейском языке, с пробелами и пунктуациями.
Для существенного поднятия точности нужен уже deep learning — трансфомация пространства признаков. И получать их лучше с очень больших объемов неклассифицированных данных.
Приведенный датасет для таких задач вообще непригоден, он слишком мал.
Alexlexandr
327 просмотров, 7 заносов в избранное и ни одного комментария за 2 часа с момента публикации, статистика интересная уже сама по себе :)