Всякая идея имеет простое, понятное и неправильное решение.
Одно из таких решений я и опишу в этой статье.
Не пытайтесь повторить эти эксперименты дома.
А если попытаетесь — то претензии по сгоревшим процессорам не принимаются.
Итак, есть датасет www.cs.cornell.edu/people/pabo/movie-review-data/review_polarity.tar.gz
Он состоит из 1000 негативных и 1000 позитивных отзывов.
Как с помощьюбуханки черного хлеба архиватора xz и линейного классификатора получить точность, сравнимую со сверточной нейронной сетью, word2vec или прочими чудесами совеременных технологий?
Очень просто.
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 метрике автоэнкодер натренировать скорее всего не получится.
Одно из таких решений я и опишу в этой статье.
Не пытайтесь повторить эти эксперименты дома.
А если попытаетесь — то претензии по сгоревшим процессорам не принимаются.
Итак, есть датасет 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 метрике автоэнкодер натренировать скорее всего не получится.
