Это не текстовые данные, как я писал — это не NLP задача.
Ну и данные мне не принадлежат — их собирали много лет, это бинарники разных вирусов и не только вирусов.
Интересно что эти самые тупейшие n-граммы ловили ряд полиморфов — что теоретически не должно было иметь места.
Эмоционалкой не занимался, а по NLP вообще могу посоветовать.
Собственно первое что я использую для NLP — дамп википедии, например только англоязычных страниц, относящихся к людям — более миллиона.
Причем часто требуемые метки можно получать сразу из инфобокса, ну или дальше из онтологий поверх википедии.
А n-граммы на тексте получаются сразу двух уровней — посимвольные и как списки слов.
Соответственно атрибутов в два раза больше.
Если надо просто большой сет — то files.grouplens.org/datasets/movielens/ml-10m-README.html
Был еще старый 100M NetFlix Prize, но доступ вроде как закрыли, у меня где-то должна была остаться копия, если надо — пишите в личку, могу поискать.
PS
Имхо n-граммы должны хорошо работать когда требуется классификация всего текста, а не его части, причем текст должен быть достаточно объемный.
Если тексты короткие как твиты — то смысла применять нет.
У меня очень похоже, зеркало всегда отражало какой-то перманентный морфинг, часто жутковатый.
Именно ощущения от чтения и зеркала во сне на меня производили наибольшее впечатление своей чужеродностью.
Программист, специализируюсь на machine learning и тем, что иногда называют AI. :-)
Я прочел весь цикл статей, правда многие поверхностно.
Модель достаточно интересна и интуитивно понятна тем, кто не испорчен фон Неймановской архитектурой.
Волновые вычисления меня кстати интересовали давно (я физик-теоретик по основному образованию), но давно про их и забыл, т.к. никакого коммерческого интереса не видел. На обычный компьютер они ложаться плохо.
По той же причине кстати стараюсь не использовать в работе нейронки.
Вообще исхожу из «железа», поэтому не собо верю в эффективность волновой модели — у меня специфика нагруженные бэкенды.
Вы сами пишете, что все упирается в быстродействие.
Другое дело — если бы была новая аппаратная архитектура, оптимизированная под такую среду.
Тогда возможно все бы изменилось.
Мое мнение по использованию таких алгоритмов очень прагматично — если бы мы делали автомобили по образцу лошадей, на наших мерседесах были бы железные ноги, а не колеса. И стоили бы они в десятки раз больше.
Поэтому понимание процессов работы мозга очень важно — это ключ ко многим технологиям.
Но понимание и имплементация — разные вещи и любое прямое копирование будет столь же неэффективно, сколь установка ног на мерседес.
В истории техники очень мало успешных технологий, заимствованных у живой природы.
Conditional jump or move depends on uninitialised value(s) означает что инициализация в нашем коде прошла успешно
Это означает что переменная b содержит неопределенный мусор.
Если бы вы написали int b=42; то этого сообщения бы не было.
Valgrind совершенно правильно указал на ошибку в коде, не фатальную, но неприятную.
Ну я как бы и указываю, что в конкретных задачах можно обойтись без голосования вообще.
Я бы разделил возможности использования голосования на следующие юзкейсы.
1. Найти решение проблемы. Самый редкий случай.
Так ведь нахождение решения — это достаточно формальная процедура, которую можно сделать вообще без голосовалки.
Мы что голосуем о доказательстве теоремы Ферма?
Или о погоде через неделю?
Нет, мы либо смотрим доказательство, либо делаем расчет погодной модели.
Здесь вообще нет понятия выборов, разве что для психологического спокойствия.
Методы ad hoc будут лучше всегда — хотя бы по теореме о бесплатных ланчах.
И более того — решения, которые мы ищем обычно лежат в объективном мире. И, значит, привлекать субъективные мнения людей — гарантированно ухудшить решение.
Того же бухгалтера надо просто фильтровать по показателям, пока не останется один.
Смысл голосовать?
2. Найти или продемонстрировать консенсус.
Это как раз более частое применение.
Т.е. есть субъективные мнения.
Надо их агрегировать в коллективное субъективное мнение. Объективным от агрегации оно ведь не станет, правильно?
СМС-голосования за самую попсовую певицу — вот это оно.
Т.е. за самую большую грудь голосовать смысла нет — ее можно измерить.
А вот за субъективные показатели (т.е. существующие только в голове голосующих) — как раз что доктор прописал.
Здесь система работает.
Хотя имхо вхолостую — т.к. разницы между первым и вторым местом по попсовости особо нету.
Зато можно сделать шоу и поднять профитов.
Ну так вот тут открытая рутовая консоль только увеличит эти профиты!
:-)
3. Снять с себя ответственность.
Это уже больше в политике.
Президент плохой — ну сами же выбирали.
Т.е. чистая психология, отмазка.
И опять же грязные хаки здесь — это часть правил игры, как в случае с Дж. Бушем и голосованием во Флориде.
Получается что голосование нужно только как дурилово — в случаях 2 и 3.
А в этом случае — зачем заморачиваться?
Генератор случайных чисел сделает ту же самую работу.
PS
Накатаю ка я свою статейку по своему видению проблемы…
Там где речь идет о выборах с количеством в сотни участников или более — выборы выполняют всего лишь цель демонстрации консенсуса.
Но не нахождения решения.
Если можете привести контрпример — с удовольствием выслушаю.
И да, попробуйте представить себе мир, где вам делает операцию аппендицита хирург, выбранный голосованием.
Или где атомной станцией управляет оператор, получивший свое место в результате электорального процесса.
Или где в большой корпорации все работники выбирают главбуха.
Везде, где важен результат — используются профессионалы и никакой демократией не пахнет.
Везде профессионалов долго растят, долго учат, отсеивают и внедряют профессиональные системы этики на уровень подкорки.
Везде, кроме политики — и дело не исчерпывается одобрением местного фюрера.
Может в политике результат не настолько важен?
Или в ней результатом является нечто другое, а не то, чему учат в школе?
И да, я прочитал пост.
И привер контрпримеры, когда эти требования бессмысленны без понимания общего предназначения выборов.
Вы можете привести примеры, когда выборы бы оптимально решали свою задачу?
Там где участников >> 10^3?
Истина не определяется голосованием.
Для этого есть совсем другие процедуры.
Даже в системах типа ensemble learning, — метод majority voting является одним из самых слабых вариантов.
И предполагает независимость исходных моделей.
Голосование — это инструмент.
Ну как шестеренка в машине.
Говорить о требованиях к шестернеке, не понимая какую задачу решает машина можно долго и увлекательно.
Какие задачи решает голосование?
Зачем оно нужно вообще и почему оно встрено в сложные социальные машины, управляющие нашей жизнью?
Вот с этого надо начинать.
Т.к. может внезапно выясниться, что выборы — это шоу, а оставленная открытая рутовая консоль лишь добавляет вовлеченности участников и поднимает стоимость рекламы в СМИ.
Или может выясниться, что выборы — это средство перекладывания ответственности на абстрактный «народ». И грязные хаки просто необходимы, т.к. народ может много чего наворотить — как и любой другой субъект не обладающий ответственностью.
А если еще понять, что голосование, как метод принятия решений является одним из самых примитивных и худших, а при высокой коррелированности индивидуальных мнений — просто начинает давать обратные результаты, то возникает вопрос — нафига эти выборы нужны, когда есть более точные способы агрегации мнений.
А без таких уточнений мы приходим к банальностям — ну да, шестеренка должна быть металлической, ну да, она должна быть с зубцами…
Так потому что архиватор — это приближение.
В точности должна быть т.н. «Колмоговровская сложность».
А архиватор дает очень приблизительную оценку.
Длина архива с двумя идентичными текстами всегда будет хоть на один бит больше, чем длина архива с одним таким текстом.
Вот эта дельта и играет роль.
В теории чем длиннее тексты, тем меньше будет ошибка.
На практике архиваторы работают по блокам и за размером блока значения начинают плавать.
Хотя сильно зависит от архиватора.
И еще, на маленьких строках портит все заголовок архива.
Т.е. вот Hello world!\n
13 байт
А архив bzip2 — 53 байта — вот такая хреновая компрессия.
А двойной архив — 57 байт.
А с другой стороны — вот берем файл www.lib.ru/GIBSON/neuromancer.txt
485967 байт
Соответственно сжатый отдельно он — 152317
А сжатый с самим собой — 223390
Получаем дистанцию 0.467, что совершенно не похоже на ожидаемый 0.
Это уже артефакт блочной архивации.
Т.е. не все там так просто и не всякий архиватор пойдет.
А вот возьмем например архиватор xz
У него архивированный текст «Нейромантика» — 167532 байт (хуже чем у bzip2)
А архивированный сам с собой — 167680
Что дает дистанцию — 0.0008834
Ну, по ресурсоемкости хуже чем NCD наверное и не найти, компрессия — штука тяжелая, и чем она тяжелее, тем точнее результат.
Я с Bloom filter использовал самописную версию LSH, думал перейти на более хитрые извращения, но потом задачу решил по другому, вообще без BF и дедупликации, т.е. саму постановку задачи перекрутил.
Имхо по дефолту лучше не заморачиваться велосипедописательством и брать например FLANN — вполне приличная библиотека, и с хорошей лицензией.
И там уже выбирать внутри нее.
Для BF кстати лучше использовать Жаккардову метрику, не Хемминга — считается битовыми операциями и как-то «нативнее» для BF — показывает отношения в множестве.
Ну и она же и используется в известном MinHash — который тоже может быть применен для дедупликации.
Как я понимаю, ценность/полезность комментария — штука субъективная.
Т.е. для каждого читателя она своя.
И значит для каждого читателя нужен свой алгоритм.
Который можно научить например на его предыдущих плюсиках.
Или например методами коллаборативной фильтрации (что имхо хуже).
Насколько это можно сделать на клиенте — хз, но уж на сервере то точно не проблема.
Возможно правда придется добавлять еще один параметр комментария, не плюсик (понравился/не понравился), а интересен/неинтересен.
Многие вещи типа дедупликации или даже установления авторства можно сделать вот этим.
Собственно идея крайне проста, если слить два текста и упаковать, то коэффициент сжатия будет тем больше, чем больше одинаковых паттернов в обоих текстах.
Как ни странно — часто работает.
:-)
Правда при сколько-нибудь реальных объемах документов — процессор расплавится, т.к. расчет очень затратен, а для всей базы еще и квадратичен.
Я в похожих задачах вместо шинглов использовал bloom filter на случайных или на полных ngramm'ах.
Как-то работало, в сочетании с aNN методами, чтобы уйти от квадратичности.
У BF есть преимущество — все магические константы (типа 84) достаточно просто считаются под задачу и обоснованы теорвером и прочим матаном.
Логично выглядит натренировать one-class систему на негативах, получить распределение вероятностей негативов и скомбинировать с стандартным бинарным классификатором.
Встречал такие советы.
И для undersampled positives в этом видна логика, полной информации не хватает для полноценного бинарного классификатора, и ее можно попытаться добрать из распределения негативов.
Но у меня такие штуки работали достаточно плохо, в первую очередь потому, что одноклассовые системы сами по себе дают ошибку побольше, чем бинарные классификаторы.
И редко добавляют ту информацию, которую планировалось добрать.
Но вообще надо пробовать, данные всегда разные и что не работает на одних сетах — работает на других.
Иногда очень странные закономерности выскакивают, предвидеть которые достаточно сложно.
А негативных классов получается 50М — 200М?
Серьезная задача.
Я не скажу, что на таких моделях всегда весело выходит.
И там кстати еще сильно зависит от того, что надо минимизировать — FP, FN или симметричную ошибку.
Один из самых простых методов вот какой.
При тренировке Random Forest как известно для тренировки каждого дерева делается подвыборка с повторениями.
У Бреймана, в оригинальной трактовке, надо брать размер выборки идентичный исходному сету, а так как после выборки с повторениями останется примерно 1/3, то на ней и ошибку дерева считают.
Но никто не запрещает сделать выборку по другому.
Например набрать одинаковое количество позитивных и негативных семплов.
Причем именно выборкой с повторениями, т.е. имея например 5К позитивов и 100К негативов — можно вполне работать с выборкой 10к позитивов + 10к негативов, — для каждого дерева естественно уникальной.
Правда надо забыть о мере оценки на оставшихся сэмплах, их может просто не остаться.
Этот подход не всегда решает проблему, но бывает помогает.
Есть еще способ — нестандартная асимметричная Impurity function (полином со смещенной модой обычно), ну или сплит-критерий доработанный напильником.
Не скажу, что мне понравились результаты, но я пробовал всего пару раз, наскоком.
Так что мог чего-то не заметить.
Т.е. общего решения так не скажу.
Если возникает такая задача — то первым делом я применяю метод, описанный в начале коммента.
А там уже копаю глубже.
Но вот 1 к 10К так даже не могу вспомнить, пожалуй не было в моей практике.
У меня чуть другой подход, достаточно отличающийся от общепринятого.
Дело в том, что я пишу высоконагруженные бэкенды, и там каждая оптимизация дает отдачу, а делать в таких условиях PCA на матрицах порядка 10^6 x 10^6 — это имхо из репертуара маркиза де Сада. :-)
Ну и опять же линейный метод, значит кучу всего оставит за кадром.
Я двигаюсь обычно так:
1. Атрибуты должны быть дискретными, лучше бинарными.
Т.е. дискретизация на самых ранных стадиях.
Пример — работа с изображениями. Можно построить дескрипторы на плавающей точке, в 128-мерном пространстве.
А потом искать по ближайшим соседям (высосав из пальца, что метрика евклидова).
А можно взять например случайный набор пар точек в области. И для каждой пары установить в соответствие бит — интенсивность выше у первого пикселя в паре или у второго.
И получаем сразу битовуюю строку бинарных атрибутов, которую можно использовать как напрямую, так и опять же через ближайших соседей (Bag of Words), но уже с Хемминговской метрикой.
Соответственно на таких атрибутах в задачах классификации естественная мера качества — взаимная информация, или ее нормированный аналог symmetrical uncertainty.
И FCBF или mRMR методы показывают себя достаточно неплохо, ну и проклятие размерности там не столь важно.
Опять же — единая мера качества атрибута (т.е. взаимная информация) убирает необходимость кластеризации атрибутов — вместо поиска групп в большом пространстве мы просто располагаем их на одномерной линии.
Я одно время, когда еще не пользовался своей схемой тоже ковырял кластеризацию признаков — спектральную кластеризацию делал.
Ушел оттуда, результаты хорошими не назвать, а задачу расплавить процессор заказчик обычно не оплачивает.
Реализацию FCBF видел в Weka.
В Python не встречал, но вполне может быть.
Я иногда конструирую атрибуты генетическим программированием — задаю грамматику, и потом фильтрую результат, который и определяет fitness function.
А иногда и монте-карло хватает, чтобы обрисовать картину — главное потом фильтровать атрибуты.
Очень просто найти черную кошку в темной комнате — надо лишь кидаться тяжелыми предметами в случайных направлениях и ждать где мяукнет.
:-)
2. Random Forest (или Extremely Random Forest или др. варианты) — наше все.
Не знаю других методов, сравнимых по скорости сканирования (не обучения) с ним при том же качестве. SVM в топку или только на предварительный анализ данных.
Соответственно RF и становится рабочей лошадкой.
GPU в датацентрах конечно появляется, и может что изменится, но пока так.
Ну вот сейчас Semantic Role Labeling на коленке делал — 2-10 документов в секунду (это пока). В то время, как крутые аналоги — один абзац в минуту иногда показывают.
Ну да, качество чуть похуже (пока).
Но когда надо терабайты через мясорубку пропустить — самое оно.
Ну и сам по себе RF — тоже неплохой фильтр атрибутов, то что он не использовал, можно удалять с пути вычислений, а это тоже такты процессора.
Плюс на RF можно делать простенькую кластеризацию (на одноклассовых деревьях например или тренируя против случайного набора), не ахти, но опять же поворот/редукцию координат из произвольного пространства атрибутов в номинальные признаки оно проводит.
И у RF есть неплохое, но незаметное достоинство.
Каждая нода каждого дерева хранит условное распределение вероятностей атрибутов. А из этого очень многое можно вытащить, если уметь готовить.
:-)
Минусы RF общеизветны, из необщеизвестных — при нестандартных методах отбора или создания атрибутов RF падает в оверфит моментально.
FCBF это кстати лечит.
Последние пару лет думаю переползать на Very Fast Decision Trees.
Надо пробовать, для потоковых данных — самое то, плюс concept drift прикручивается проще.
3. У меня правило — чтобы разобраться в алгоритме я его имплементирую.
:-)
А поскольку страдаю наслаждаюсь мазохизмом, то имплементирую на С.
Ну заодно и нет проблем с производительностью.
Поэтому наличие алгоритмов в других пакетах особо не отслеживаю.
С другой стороны для быстро попробовать — большинство мейнстримовых вещей есть в Weka/RapidMiner, формат простой, можно экспериментировать сколько угодно.
Ну а если приспичит — свой прототип всегда можно написать.
Как-то так.
NCA покопаю кстати, спасибо за линк.
В статье выглядит гламурно.
Но в статьях все выглядит гламурно, все надо пробовать самому на живых данных.
PS
Не совсем понял почему атрибуты ищутся после построения модели.
В задаче по DataFusion я тоже не совсем понял проблемы.
Есть ~1к сенсоров (т.е. ~1к ординальных переменных) и ~1к бинарных (онтологии).
Это как бы очень немного и уже на этом можно дерево строить сразу, а если данных мало, то и SVM на одном ядре все решит.
А если сэмплов много — то надо делать выборку и ансамбль.
Тут можно вообще без фильтрации обойтись.
Т.е. для PCA подобных методов — да, проблемы.
Но неясно насколько тут нужны такие методы.
И опять же — выход сенсора гауссианой будет только в спецификации сенсора, а что в реальности надо на реальных данных смотреть.
Ну и данные мне не принадлежат — их собирали много лет, это бинарники разных вирусов и не только вирусов.
Интересно что эти самые тупейшие n-граммы ловили ряд полиморфов — что теоретически не должно было иметь места.
Эмоционалкой не занимался, а по NLP вообще могу посоветовать.
Собственно первое что я использую для NLP — дамп википедии, например только англоязычных страниц, относящихся к людям — более миллиона.
Причем часто требуемые метки можно получать сразу из инфобокса, ну или дальше из онтологий поверх википедии.
А n-граммы на тексте получаются сразу двух уровней — посимвольные и как списки слов.
Соответственно атрибутов в два раза больше.
На Kaggle можно много найти.
Еще вот такая свалка archive.ics.uci.edu/ml/datasets.html
Вот для NLP есть некоторые
www.clips.ua.ac.be/conll2003/ner/ — прямо сейчас открыто у меня.
Вообще гуглим CoNLL dataset
Ну и www.americannationalcorpus.org/OANC/index.html
Но тут разметка врет как дышит — я отказался от него, там даже разбивка по предложениям кривая.
Если надо просто большой сет — то files.grouplens.org/datasets/movielens/ml-10m-README.html
Был еще старый 100M NetFlix Prize, но доступ вроде как закрыли, у меня где-то должна была остаться копия, если надо — пишите в личку, могу поискать.
PS
Имхо n-граммы должны хорошо работать когда требуется классификация всего текста, а не его части, причем текст должен быть достаточно объемный.
Если тексты короткие как твиты — то смысла применять нет.
Именно ощущения от чтения и зеркала во сне на меня производили наибольшее впечатление своей чужеродностью.
1. Удавалось ли кому-либо во сне прочитать связный текст?
2. Удавалось ли кому-то во сне посмотреть в зеркало и увидеть там что-то разумное?
Чисто из интереса, я на этих двух точках остановился и похоже навсегда.
Я прочел весь цикл статей, правда многие поверхностно.
Модель достаточно интересна и интуитивно понятна тем, кто не испорчен фон Неймановской архитектурой.
Волновые вычисления меня кстати интересовали давно (я физик-теоретик по основному образованию), но давно про их и забыл, т.к. никакого коммерческого интереса не видел. На обычный компьютер они ложаться плохо.
По той же причине кстати стараюсь не использовать в работе нейронки.
Вообще исхожу из «железа», поэтому не собо верю в эффективность волновой модели — у меня специфика нагруженные бэкенды.
Вы сами пишете, что все упирается в быстродействие.
Другое дело — если бы была новая аппаратная архитектура, оптимизированная под такую среду.
Тогда возможно все бы изменилось.
Мое мнение по использованию таких алгоритмов очень прагматично — если бы мы делали автомобили по образцу лошадей, на наших мерседесах были бы железные ноги, а не колеса. И стоили бы они в десятки раз больше.
Поэтому понимание процессов работы мозга очень важно — это ключ ко многим технологиям.
Но понимание и имплементация — разные вещи и любое прямое копирование будет столь же неэффективно, сколь установка ног на мерседес.
В истории техники очень мало успешных технологий, заимствованных у живой природы.
Это означает что переменная b содержит неопределенный мусор.
Если бы вы написали int b=42; то этого сообщения бы не было.
Valgrind совершенно правильно указал на ошибку в коде, не фатальную, но неприятную.
Я бы разделил возможности использования голосования на следующие юзкейсы.
1. Найти решение проблемы. Самый редкий случай.
Так ведь нахождение решения — это достаточно формальная процедура, которую можно сделать вообще без голосовалки.
Мы что голосуем о доказательстве теоремы Ферма?
Или о погоде через неделю?
Нет, мы либо смотрим доказательство, либо делаем расчет погодной модели.
Здесь вообще нет понятия выборов, разве что для психологического спокойствия.
Методы ad hoc будут лучше всегда — хотя бы по теореме о бесплатных ланчах.
И более того — решения, которые мы ищем обычно лежат в объективном мире. И, значит, привлекать субъективные мнения людей — гарантированно ухудшить решение.
Того же бухгалтера надо просто фильтровать по показателям, пока не останется один.
Смысл голосовать?
2. Найти или продемонстрировать консенсус.
Это как раз более частое применение.
Т.е. есть субъективные мнения.
Надо их агрегировать в коллективное субъективное мнение. Объективным от агрегации оно ведь не станет, правильно?
СМС-голосования за самую попсовую певицу — вот это оно.
Т.е. за самую большую грудь голосовать смысла нет — ее можно измерить.
А вот за субъективные показатели (т.е. существующие только в голове голосующих) — как раз что доктор прописал.
Здесь система работает.
Хотя имхо вхолостую — т.к. разницы между первым и вторым местом по попсовости особо нету.
Зато можно сделать шоу и поднять профитов.
Ну так вот тут открытая рутовая консоль только увеличит эти профиты!
:-)
3. Снять с себя ответственность.
Это уже больше в политике.
Президент плохой — ну сами же выбирали.
Т.е. чистая психология, отмазка.
И опять же грязные хаки здесь — это часть правил игры, как в случае с Дж. Бушем и голосованием во Флориде.
Получается что голосование нужно только как дурилово — в случаях 2 и 3.
А в этом случае — зачем заморачиваться?
Генератор случайных чисел сделает ту же самую работу.
PS
Накатаю ка я свою статейку по своему видению проблемы…
Т.е. уже не проходит.
Но не нахождения решения.
Если можете привести контрпример — с удовольствием выслушаю.
И да, попробуйте представить себе мир, где вам делает операцию аппендицита хирург, выбранный голосованием.
Или где атомной станцией управляет оператор, получивший свое место в результате электорального процесса.
Или где в большой корпорации все работники выбирают главбуха.
Везде, где важен результат — используются профессионалы и никакой демократией не пахнет.
Везде профессионалов долго растят, долго учат, отсеивают и внедряют профессиональные системы этики на уровень подкорки.
Везде, кроме политики — и дело не исчерпывается одобрением местного фюрера.
Может в политике результат не настолько важен?
Или в ней результатом является нечто другое, а не то, чему учат в школе?
И да, я прочитал пост.
И привер контрпримеры, когда эти требования бессмысленны без понимания общего предназначения выборов.
Вы можете привести примеры, когда выборы бы оптимально решали свою задачу?
Там где участников >> 10^3?
Истина не определяется голосованием.
Для этого есть совсем другие процедуры.
Даже в системах типа ensemble learning, — метод majority voting является одним из самых слабых вариантов.
И предполагает независимость исходных моделей.
Ну как шестеренка в машине.
Говорить о требованиях к шестернеке, не понимая какую задачу решает машина можно долго и увлекательно.
Какие задачи решает голосование?
Зачем оно нужно вообще и почему оно встрено в сложные социальные машины, управляющие нашей жизнью?
Вот с этого надо начинать.
Т.к. может внезапно выясниться, что выборы — это шоу, а оставленная открытая рутовая консоль лишь добавляет вовлеченности участников и поднимает стоимость рекламы в СМИ.
Или может выясниться, что выборы — это средство перекладывания ответственности на абстрактный «народ». И грязные хаки просто необходимы, т.к. народ может много чего наворотить — как и любой другой субъект не обладающий ответственностью.
А если еще понять, что голосование, как метод принятия решений является одним из самых примитивных и худших, а при высокой коррелированности индивидуальных мнений — просто начинает давать обратные результаты, то возникает вопрос — нафига эти выборы нужны, когда есть более точные способы агрегации мнений.
А без таких уточнений мы приходим к банальностям — ну да, шестеренка должна быть металлической, ну да, она должна быть с зубцами…
Как-то так.
С тех пор многое изменилось…
Как сейчас поступает домохозяйка, когда ей нужен красивый аватар в социалочку?
Идет к подружке, которая владеет фотошопом.
Так же и тут будет.
Как блондинки используют 3д принтер.
В точности должна быть т.н. «Колмоговровская сложность».
А архиватор дает очень приблизительную оценку.
Длина архива с двумя идентичными текстами всегда будет хоть на один бит больше, чем длина архива с одним таким текстом.
Вот эта дельта и играет роль.
В теории чем длиннее тексты, тем меньше будет ошибка.
На практике архиваторы работают по блокам и за размером блока значения начинают плавать.
Хотя сильно зависит от архиватора.
И еще, на маленьких строках портит все заголовок архива.
Т.е. вот Hello world!\n
13 байт
А архив bzip2 — 53 байта — вот такая хреновая компрессия.
А двойной архив — 57 байт.
А с другой стороны — вот берем файл www.lib.ru/GIBSON/neuromancer.txt
485967 байт
Соответственно сжатый отдельно он — 152317
А сжатый с самим собой — 223390
Получаем дистанцию 0.467, что совершенно не похоже на ожидаемый 0.
Это уже артефакт блочной архивации.
Т.е. не все там так просто и не всякий архиватор пойдет.
А вот возьмем например архиватор xz
У него архивированный текст «Нейромантика» — 167532 байт (хуже чем у bzip2)
А архивированный сам с собой — 167680
Что дает дистанцию — 0.0008834
Совсем другое дело.
Я с Bloom filter использовал самописную версию LSH, думал перейти на более хитрые извращения, но потом задачу решил по другому, вообще без BF и дедупликации, т.е. саму постановку задачи перекрутил.
Имхо по дефолту лучше не заморачиваться велосипедописательством и брать например FLANN — вполне приличная библиотека, и с хорошей лицензией.
И там уже выбирать внутри нее.
Для BF кстати лучше использовать Жаккардову метрику, не Хемминга — считается битовыми операциями и как-то «нативнее» для BF — показывает отношения в множестве.
Ну и она же и используется в известном MinHash — который тоже может быть применен для дедупликации.
Т.е. для каждого читателя она своя.
И значит для каждого читателя нужен свой алгоритм.
Который можно научить например на его предыдущих плюсиках.
Или например методами коллаборативной фильтрации (что имхо хуже).
Насколько это можно сделать на клиенте — хз, но уж на сервере то точно не проблема.
Возможно правда придется добавлять еще один параметр комментария, не плюсик (понравился/не понравился), а интересен/неинтересен.
Собственно идея крайне проста, если слить два текста и упаковать, то коэффициент сжатия будет тем больше, чем больше одинаковых паттернов в обоих текстах.
Как ни странно — часто работает.
:-)
Правда при сколько-нибудь реальных объемах документов — процессор расплавится, т.к. расчет очень затратен, а для всей базы еще и квадратичен.
Я в похожих задачах вместо шинглов использовал bloom filter на случайных или на полных ngramm'ах.
Как-то работало, в сочетании с aNN методами, чтобы уйти от квадратичности.
У BF есть преимущество — все магические константы (типа 84) достаточно просто считаются под задачу и обоснованы теорвером и прочим матаном.
Встречал такие советы.
И для undersampled positives в этом видна логика, полной информации не хватает для полноценного бинарного классификатора, и ее можно попытаться добрать из распределения негативов.
Но у меня такие штуки работали достаточно плохо, в первую очередь потому, что одноклассовые системы сами по себе дают ошибку побольше, чем бинарные классификаторы.
И редко добавляют ту информацию, которую планировалось добрать.
Но вообще надо пробовать, данные всегда разные и что не работает на одних сетах — работает на других.
Иногда очень странные закономерности выскакивают, предвидеть которые достаточно сложно.
Серьезная задача.
Я не скажу, что на таких моделях всегда весело выходит.
И там кстати еще сильно зависит от того, что надо минимизировать — FP, FN или симметричную ошибку.
Один из самых простых методов вот какой.
При тренировке Random Forest как известно для тренировки каждого дерева делается подвыборка с повторениями.
У Бреймана, в оригинальной трактовке, надо брать размер выборки идентичный исходному сету, а так как после выборки с повторениями останется примерно 1/3, то на ней и ошибку дерева считают.
Но никто не запрещает сделать выборку по другому.
Например набрать одинаковое количество позитивных и негативных семплов.
Причем именно выборкой с повторениями, т.е. имея например 5К позитивов и 100К негативов — можно вполне работать с выборкой 10к позитивов + 10к негативов, — для каждого дерева естественно уникальной.
Правда надо забыть о мере оценки на оставшихся сэмплах, их может просто не остаться.
Этот подход не всегда решает проблему, но бывает помогает.
Есть еще способ — нестандартная асимметричная Impurity function (полином со смещенной модой обычно), ну или сплит-критерий доработанный напильником.
Не скажу, что мне понравились результаты, но я пробовал всего пару раз, наскоком.
Так что мог чего-то не заметить.
Т.е. общего решения так не скажу.
Если возникает такая задача — то первым делом я применяю метод, описанный в начале коммента.
А там уже копаю глубже.
Но вот 1 к 10К так даже не могу вспомнить, пожалуй не было в моей практике.
Дело в том, что я пишу высоконагруженные бэкенды, и там каждая оптимизация дает отдачу, а делать в таких условиях PCA на матрицах порядка 10^6 x 10^6 — это имхо из репертуара маркиза де Сада. :-)
Ну и опять же линейный метод, значит кучу всего оставит за кадром.
Я двигаюсь обычно так:
1. Атрибуты должны быть дискретными, лучше бинарными.
Т.е. дискретизация на самых ранных стадиях.
Пример — работа с изображениями. Можно построить дескрипторы на плавающей точке, в 128-мерном пространстве.
А потом искать по ближайшим соседям (высосав из пальца, что метрика евклидова).
А можно взять например случайный набор пар точек в области. И для каждой пары установить в соответствие бит — интенсивность выше у первого пикселя в паре или у второго.
И получаем сразу битовуюю строку бинарных атрибутов, которую можно использовать как напрямую, так и опять же через ближайших соседей (Bag of Words), но уже с Хемминговской метрикой.
Соответственно на таких атрибутах в задачах классификации естественная мера качества — взаимная информация, или ее нормированный аналог symmetrical uncertainty.
И FCBF или mRMR методы показывают себя достаточно неплохо, ну и проклятие размерности там не столь важно.
Опять же — единая мера качества атрибута (т.е. взаимная информация) убирает необходимость кластеризации атрибутов — вместо поиска групп в большом пространстве мы просто располагаем их на одномерной линии.
Я одно время, когда еще не пользовался своей схемой тоже ковырял кластеризацию признаков — спектральную кластеризацию делал.
Ушел оттуда, результаты хорошими не назвать, а задачу расплавить процессор заказчик обычно не оплачивает.
Реализацию FCBF видел в Weka.
В Python не встречал, но вполне может быть.
Я иногда конструирую атрибуты генетическим программированием — задаю грамматику, и потом фильтрую результат, который и определяет fitness function.
А иногда и монте-карло хватает, чтобы обрисовать картину — главное потом фильтровать атрибуты.
Очень просто найти черную кошку в темной комнате — надо лишь кидаться тяжелыми предметами в случайных направлениях и ждать где мяукнет.
:-)
2. Random Forest (или Extremely Random Forest или др. варианты) — наше все.
Не знаю других методов, сравнимых по скорости сканирования (не обучения) с ним при том же качестве. SVM в топку или только на предварительный анализ данных.
Соответственно RF и становится рабочей лошадкой.
GPU в датацентрах конечно появляется, и может что изменится, но пока так.
Ну вот сейчас Semantic Role Labeling на коленке делал — 2-10 документов в секунду (это пока). В то время, как крутые аналоги — один абзац в минуту иногда показывают.
Ну да, качество чуть похуже (пока).
Но когда надо терабайты через мясорубку пропустить — самое оно.
Ну и сам по себе RF — тоже неплохой фильтр атрибутов, то что он не использовал, можно удалять с пути вычислений, а это тоже такты процессора.
Плюс на RF можно делать простенькую кластеризацию (на одноклассовых деревьях например или тренируя против случайного набора), не ахти, но опять же поворот/редукцию координат из произвольного пространства атрибутов в номинальные признаки оно проводит.
И у RF есть неплохое, но незаметное достоинство.
Каждая нода каждого дерева хранит условное распределение вероятностей атрибутов. А из этого очень многое можно вытащить, если уметь готовить.
:-)
Минусы RF общеизветны, из необщеизвестных — при нестандартных методах отбора или создания атрибутов RF падает в оверфит моментально.
FCBF это кстати лечит.
Последние пару лет думаю переползать на Very Fast Decision Trees.
Надо пробовать, для потоковых данных — самое то, плюс concept drift прикручивается проще.
3. У меня правило — чтобы разобраться в алгоритме я его имплементирую.
:-)
А поскольку
страдаюнаслаждаюсь мазохизмом, то имплементирую на С.Ну заодно и нет проблем с производительностью.
Поэтому наличие алгоритмов в других пакетах особо не отслеживаю.
С другой стороны для быстро попробовать — большинство мейнстримовых вещей есть в Weka/RapidMiner, формат простой, можно экспериментировать сколько угодно.
Ну а если приспичит — свой прототип всегда можно написать.
Как-то так.
NCA покопаю кстати, спасибо за линк.
В статье выглядит гламурно.
Но в статьях все выглядит гламурно, все надо пробовать самому на живых данных.
PS
Не совсем понял почему атрибуты ищутся после построения модели.
В задаче по DataFusion я тоже не совсем понял проблемы.
Есть ~1к сенсоров (т.е. ~1к ординальных переменных) и ~1к бинарных (онтологии).
Это как бы очень немного и уже на этом можно дерево строить сразу, а если данных мало, то и SVM на одном ядре все решит.
А если сэмплов много — то надо делать выборку и ансамбль.
Тут можно вообще без фильтрации обойтись.
Т.е. для PCA подобных методов — да, проблемы.
Но неясно насколько тут нужны такие методы.
И опять же — выход сенсора гауссианой будет только в спецификации сенсора, а что в реальности надо на реальных данных смотреть.
А чем старый добрый FCBF не подходит?
У меня на 800к атрибутах работал, больше не гонял, не надо было.
Хотя есть недостатки, но достаточно быстренький, особенно если атрибуты слабенькие, он их отсеивает моментально.