Хабр Курсы для всех
РЕКЛАМА
Большая витрина: от крупнейших школ до частных авторов. Сравнивайте по цене, длительности, формату и выбирайте самый подходящий курс!
Хабр доступен 24/7 благодаря поддержке друзей
Комментарии 107
Это всё конечно хорошо, но будет ли разобран/открыт алгоритм/код?
У меня большие сомнения в целесообразности этого.
Классификация текстов на основе HMM — это, в принципе, хорошо. Но
1) посимвольная (!), причем используются модули глубокого анализа текста с АОТ
2) со скоростью 300 байт/с, с 4 SQL (!!)- запросами на символ (!!!)
— это уже даже не плохо. Это никак.
HMM работают со скоростью сотен тысяч правил в секунду. SQL здесь вообще непонятно, каким боком, работать нужно даже не с внешним key-value хранилищем, а прямо в памяти процесса.
И, совет, не нужно думать, что вы написали личинку универсального алгоритма, который и поиск, и искусственный интеллект, и автоматический брокер, а то, что он пока не работает — так это просто текстов мало. Это всего лишь крайне неэффективная реализация задачи классификации документов. Вот ниже Вам советуют съездить на РОМИП — не поедете, так хоть труды почитайте, дорожка классификации там есть уже много лет.
Классификация текстов на основе HMM — это, в принципе, хорошо. Но
1) посимвольная (!), причем используются модули глубокого анализа текста с АОТ
2) со скоростью 300 байт/с, с 4 SQL (!!)- запросами на символ (!!!)
— это уже даже не плохо. Это никак.
HMM работают со скоростью сотен тысяч правил в секунду. SQL здесь вообще непонятно, каким боком, работать нужно даже не с внешним key-value хранилищем, а прямо в памяти процесса.
И, совет, не нужно думать, что вы написали личинку универсального алгоритма, который и поиск, и искусственный интеллект, и автоматический брокер, а то, что он пока не работает — так это просто текстов мало. Это всего лишь крайне неэффективная реализация задачи классификации документов. Вот ниже Вам советуют съездить на РОМИП — не поедете, так хоть труды почитайте, дорожка классификации там есть уже много лет.
В принципе можно выбрать любой размер блока для анализа. Я выбрал блок размером в символ, так как при этом можно извлекать достаточно большое количество ассоциаций из памяти. А чем больше статистической информации, тем уверенней можно принимать решения. Если у кого-то есть предпочтение на другой размер блока, то это, скорее всего, тоже будет резонно.
Я думаю, что лучший результат можно будет получить, если предварительно сделать преобразование Фурье. Возможно, это даже сократит необходимое количество запросов к БД на обработку одного символа и улучшит ассоциативность.
Оперативная память не подходит, так как, например, уже сейчас накопилось 1,8Гб информации и это далеко не предел. А учитывая, что программа крутится на достаточно тормозном виртуальном сервере, то скорость в 300 байт/с мне кажется не такой уж и низкой.
Спасибо за ссылку на РОМИП, почитаю. Вы тоже меня поймите, я не так давно занимаюсь этим делом и еще не успел найти свободные/доступные продукты, которые дали бы мне хотя бы тот функционал, который я получил со своим ПО. Не подумайте, что я возомнил о себе что-то сверхъестественное, количество уникальных идей в алгоритме, по сути, исчезающе мало. Но дорогу осилит идущий и я, конечно же, хочу использовать передовой опыт других людей.
Я думаю, что лучший результат можно будет получить, если предварительно сделать преобразование Фурье. Возможно, это даже сократит необходимое количество запросов к БД на обработку одного символа и улучшит ассоциативность.
Оперативная память не подходит, так как, например, уже сейчас накопилось 1,8Гб информации и это далеко не предел. А учитывая, что программа крутится на достаточно тормозном виртуальном сервере, то скорость в 300 байт/с мне кажется не такой уж и низкой.
Спасибо за ссылку на РОМИП, почитаю. Вы тоже меня поймите, я не так давно занимаюсь этим делом и еще не успел найти свободные/доступные продукты, которые дали бы мне хотя бы тот функционал, который я получил со своим ПО. Не подумайте, что я возомнил о себе что-то сверхъестественное, количество уникальных идей в алгоритме, по сути, исчезающе мало. Но дорогу осилит идущий и я, конечно же, хочу использовать передовой опыт других людей.
Просто замечательно, что у Вас есть желание глубже разобраться в задаче. :)
Возможно, я был излишне резок, просто мне кажется, что количество туманных анонсов о возможностях алгоритма пока что плохо соотносятся с его качеством.
Дорожки классификации РОМИПа со списками литературы, в принципе, должно быть достаточно. Также настоятельно советую взять тот же набор данных и прогнать свой алгоритм на них, чтобы объективно оценить его качество по сравнению с остальными.
Если РОМИП перерастете, вот тут есть совсем фундаментальная теория. Ваша задача — из области классификации, или обучения с учителем.
Возможно, я был излишне резок, просто мне кажется, что количество туманных анонсов о возможностях алгоритма пока что плохо соотносятся с его качеством.
Дорожки классификации РОМИПа со списками литературы, в принципе, должно быть достаточно. Также настоятельно советую взять тот же набор данных и прогнать свой алгоритм на них, чтобы объективно оценить его качество по сравнению с остальными.
Если РОМИП перерастете, вот тут есть совсем фундаментальная теория. Ваша задача — из области классификации, или обучения с учителем.
Алгоритм обязательно будет открыт. Только я здесь новичок и могу публиковаться, как выяснилось, только в песочнице, что, конечно, комично и вовсе не вдохновляет.
Если кратко, то идея такая: текст — это последовательность символов. Эта последовательность можно принять как причину и следствие. Например, в тексте «абв» за «а» следует «б», за «б» следует «в».
То есть: а->б->в. Эта последовательность так и запоминается: а->б и б->в.
Если вдруг возникнет противоречие, то оно будет разрешаться. Например, допустим, что алгоритму дадут проанализировать «обг». Соответственно будут цепочки: о->б и б->г. А в сумме:
а->б
о->б
б->в
б->г
Здесь за «б» следуют и «в» и «г». Чтобы решить проблему алгоритм аннулирует зависимости б->в и б->г и запоминает новые:
аб->в
об->г
Ну вот, в общем, основная идея. Дальше остается организовать поиск цепочек и анализировать насколько они противоречат/не противоречат друг другу.
Если кратко, то идея такая: текст — это последовательность символов. Эта последовательность можно принять как причину и следствие. Например, в тексте «абв» за «а» следует «б», за «б» следует «в».
То есть: а->б->в. Эта последовательность так и запоминается: а->б и б->в.
Если вдруг возникнет противоречие, то оно будет разрешаться. Например, допустим, что алгоритму дадут проанализировать «обг». Соответственно будут цепочки: о->б и б->г. А в сумме:
а->б
о->б
б->в
б->г
Здесь за «б» следуют и «в» и «г». Чтобы решить проблему алгоритм аннулирует зависимости б->в и б->г и запоминает новые:
аб->в
об->г
Ну вот, в общем, основная идея. Дальше остается организовать поиск цепочек и анализировать насколько они противоречат/не противоречат друг другу.
А как быстро работает алгоритм? Можно ли его использовать для форумов?
На текст ~300 байт уходит ~1 сек. Это на FirstVDS-Разгон, где дают максимум 5% процессора при заявленных 400Мгц.
Насчет форумов — не понятно с какой целью его использовать. Чтобы составлять ленту на главной странице? Может быть вы скажете что бы вы хотели получить в результате?
Насчет форумов — не понятно с какой целью его использовать. Чтобы составлять ленту на главной странице? Может быть вы скажете что бы вы хотели получить в результате?
Секунда на 300 байт — это что, полный перебор что ли?
да, полный анализ текста. При этом производится около 1-2 тыс SQL-запросов.
на 300 байт!!!???
Вас что-то смущает?
Основное время уходит на обращение к БД. 3-4 SQL-запроса на обработку одного символа — я бы сказал немного. Учитывая, что нужно искать максимальную цепочку по каждому символу, а цепочки доходят до 500 символов и более.
Кстати, вы, наверное, думаете, что FirstVDS — это быстрый хостинг?
Основное время уходит на обращение к БД. 3-4 SQL-запроса на обработку одного символа — я бы сказал немного. Учитывая, что нужно искать максимальную цепочку по каждому символу, а цепочки доходят до 500 символов и более.
Кстати, вы, наверное, думаете, что FirstVDS — это быстрый хостинг?
А какого плана там SQL запросы? может лучше key-value заменить? (redis например)
Может лучше вообще в память всасывать всю базу? Какой размер?
В принципе, именно key-values данные там и хранятся. Заменить можно, но я лично сомневаюсь, что прирост в скорости будет. По крайней мере не на этом хостинге.
Хороший алгоритм. Производители и продавцы железа будут довольны.
Последовательность символов или слов?
Я беру последовательность символов. Для ускорения и облегчения анализа я текст несколько готовлю (strtolower, выбрасываю символы) и ввел некоторые легкие ограничения. Например, я анализирую не полную последовательность, а беру текст по предложениям. Для новостного ресурса этого оказывается достаточно.
Мммм… а если символы заменить целыми словами (приведенными к неопределенной форме) и анализировать соответственно большие тексты. Будет работать?
А как работает категоризация (отнесение текста к какой либо теме)? Я так понимаю алгоритм обучается на подготовленном наборе текстов генерируя для цепочки?
А как работает категоризация (отнесение текста к какой либо теме)? Я так понимаю алгоритм обучается на подготовленном наборе текстов генерируя для цепочки?
Думаю работать будет. Но при этом увеличивается количество вариантов на каждый последующий элемент. А это значит, что цепочки будут взаимодействовать друг с другом слабее, а это значит, из памяти будет извлекаться значительно меньше «ассоциаций», необходимых для анализа.
Я думаю, что в идеале количество вариантов на последовательность не должна превышать 2. 256-65536 (в случае utf-8) все еще не так много. В качестве костыля ваша идея пойдет, но мне кажется, что надо стремиться к идеалу, как вы думаете?
А категоризация как раз работает на принципе запоминания категории при запоминании цепочки и при вспоминании ее при поиске максимально запомненной цепочки. Дело в том, что каждый источник я помечаю темой, но если вспомненные цепочки говорят, что полученный из источника текст соответствует другой категории, то я его перепомечаю.
Я думаю, что в идеале количество вариантов на последовательность не должна превышать 2. 256-65536 (в случае utf-8) все еще не так много. В качестве костыля ваша идея пойдет, но мне кажется, что надо стремиться к идеалу, как вы думаете?
А категоризация как раз работает на принципе запоминания категории при запоминании цепочки и при вспоминании ее при поиске максимально запомненной цепочки. Дело в том, что каждый источник я помечаю темой, но если вспомненные цепочки говорят, что полученный из источника текст соответствует другой категории, то я его перепомечаю.
Что такое «специальный маркер»?
У вас уже почти достаточно кармы для написания поста… Тема интересная, будем ждать подробное описание алгоритма )
Посмотрел сайт. Много новостей не в своей категории находятся. Например в Экономике про отключение света и.т.д.
Работа со словарём мне кажется надёжнее. Слова приводятся в начальную ворму и сверяются со словарём категорий, составленным либо вручную либо автоматически на основе статистических данных прогоном например по Ленте.ру.
Работа со словарём мне кажется надёжнее. Слова приводятся в начальную ворму и сверяются со словарём категорий, составленным либо вручную либо автоматически на основе статистических данных прогоном например по Ленте.ру.
Вы не поверите, новостные ресурсы помещают информацию об отключении света именно в раздел «Экономика». Именно поэтому ваш метод вряд ли покажет лучший результат, но уж точно будет требовать больше трудозатрат, если вы захотите составлять словарь вручную.
Несомненно со словарём сложнее. Но не обязательно его составлять вручную, можно просто на основе статистики по избранным ресурсам. Некоторые ресурсы не правильно определяют категорию, другие напротив.
Просто словарь можно загрузить полностью в оперативную память и вести поиск мгновенно.
По поводу определения схожести текстов — тут поможет алгоритм Шинглов. Быстрый и простой алгоритм.
Просто словарь можно загрузить полностью в оперативную память и вести поиск мгновенно.
По поводу определения схожести текстов — тут поможет алгоритм Шинглов. Быстрый и простой алгоритм.
Ну сложность думаю одинаковая, что обучатся на последовательностях слов длинной, что на последовательностях символов. Точность заранее предсказать сложно, но как правило на шумах как раз со словарями работает система хуже.
О этих языковых моделях можно почитать здесь alias-i.com/lingpipe/demos/tutorial/classify/read-me.html.
О этих языковых моделях можно почитать здесь alias-i.com/lingpipe/demos/tutorial/classify/read-me.html.
Корректно ли будет вот такое обобщение: по факту вы формируете некоторое множество (нечеткое?) символьных цепочек которые встречаются во всех обучающих текстах для каждой категории?
Что значит нечеткое? В некотором роде да.
Тогда следующий вопрос: результаты рубрикации поступающих данных дополняют потом обучающее множество? Т.е. если вы разобрали новую новость и определили ее в категорию «экономика», то скорректированные цепочки этой новости будут определять принадлежность следующих за ней новостей к этой рубрике? Или же используется только ядро цепочек, построенное на обучающей выборке?
Детектированная категория не запоминается. Это для того, чтобы алгоритм не стал «самоуверенным». Если какая-то цепочка засветилась в нескольких категориях, то ее категория аннулируется, так как становится недостоверной.
Можно, конечно, выстраивать вероятности появления цепочки в категориях, но я посчитал, что это затратно. А на практике оказалось, что этого и не требуется.
Можно, конечно, выстраивать вероятности появления цепочки в категориях, но я посчитал, что это затратно. А на практике оказалось, что этого и не требуется.
Все таки, последовательность символов является строгой и составляет причину->следствие.
Ну иногда вводят понятие вероятности. Т.е. после последовательности аб->г c вероятностью 0.4 аб->c с вероятностью 0.6. У вас получается все цепочки имеют вероятность 1.
Да, получается так. Алгоритм ищет постоянную структуру анализируемых данных. Но если сохранять статистику частоты выбираемых цепочек, то можно будет вычислять и вероятности. Но требования к вычислительным ресурсам при этом значительно ужесточатся.
Впрочем, алгоритм прекрасно распараллеливается и если он будет выполняться на множестве маломощных ядер (синапсов?) то можно будет сохранять и статистику.
Впрочем, алгоритм прекрасно распараллеливается и если он будет выполняться на множестве маломощных ядер (синапсов?) то можно будет сохранять и статистику.
Не очень понятна схема разрешения конфликтов. Если у вы видите что у вас две последовательности символов ведут к разным предложениям вы расширяете(левую часть) их до тех пор пока конфликт не решится? Можно подробнее как вы это делаете?
Не так. Если я вижу, что одна предпосылка ведет к разным следствиям, то я помечаю, что она не достоверна, расширяю левую часть предпосылки и запоминаю ее следствие. На этом конфликт и разрешается.
по идее ваш алгоритм не будет работать на темах в которых разное соотношение одних и тех же слов. Т.е. вы удаляете все неоднозначности и оставляете только уникальные стопроцентные свойства последовательности — это конечно сильно экономит память. Но таким образом категория c текстами B A A A A B и A B B B B A не будут отличатся так как у них одинаковые последовательности — отличие только в их вероятностях.
к его алгоритму сложно прикрутить вероятность, так как если будет аб->c и аб->г, он сделает (Symbol1)аб->c и (Symbol2)аб->г
Можно ли сказать так что вы храните для каждого текста его непротиворечивые(удаляя конфликты по вышеописанному алгоритму) цепочки и маркеры(в которых хранится категория). И видя новый текст вы понимаете его категорию и дубликат ли он по ближайшему тексту из базы?
Вашему марковскому методу не хватает сравнения с уже существующими.
Методов анализа текста, в т.ч. автоматической кластеризации и классификации много, о части из них можно почитать в книге Д.Ландэ «Интернетика»: webground.su/services.php?param=book&part=internetica_content.htm#content.
А для сравнения результатов разных методик есть семинар РОМИП: romip.ru.
Сейчас там идет запись в школу RUSSIR, очень рекомендую съездить (август, Питер).
Методов анализа текста, в т.ч. автоматической кластеризации и классификации много, о части из них можно почитать в книге Д.Ландэ «Интернетика»: webground.su/services.php?param=book&part=internetica_content.htm#content.
А для сравнения результатов разных методик есть семинар РОМИП: romip.ru.
Сейчас там идет запись в школу RUSSIR, очень рекомендую съездить (август, Питер).
Хорошо бы, конечно, купить Маннинга «Введение в информационный поиск», но, боюсь, до будущего переиздания эта задача маловыполнимая.
С августа 2011 года в продаже доступна допечатка книги Маннинга и др. «Введение в информационный поиск»
Увы, но почти весь первый тираж выкупил Яндекс для своих целей
Увы, но почти весь первый тираж выкупил Яндекс для своих целей
К сожалению, съездить не смогу, так как у меня в это намечается важное событие, да и кроме того я ограничен в возможностях.
По поводу своего алгоритма хочу сказать, что его возможности не ограничиваются кластеризацией, так как он выстраивает причинно-следственные связи. А это значит, что его можно использовать для предугадывания событий. Мне даже кажется, что он сгодится и для построения искусственного интеллекта уровня человека. Поэтому я и стараюсь его развить.
Речь о творческой составляющей. До понимания процесса поиска идей я уже дошел, дальше надо понять то, как этими идеями пользоваться.
По поводу своего алгоритма хочу сказать, что его возможности не ограничиваются кластеризацией, так как он выстраивает причинно-следственные связи. А это значит, что его можно использовать для предугадывания событий. Мне даже кажется, что он сгодится и для построения искусственного интеллекта уровня человека. Поэтому я и стараюсь его развить.
Речь о творческой составляющей. До понимания процесса поиска идей я уже дошел, дальше надо понять то, как этими идеями пользоваться.
Ээээээ… нахождение общих подпоследовательностей сложно назвать выстраиванием причинно-следственных связей. А уж про искусственный интеллект лучше вообще не говорить всуе.
Ну я бы конечно сказал что весь искусственный интеллект на данный момент, это сложение и умножение над числами. И самая простая вещь такая как сбор статистики слов дает поразительные результаты классификации — предсказания! (я о Наивном баесе). Но скептицизм конечно есть относительно этого алгоритма, так как по той же статистике новое придумывают очень редко.
А чем же это не причинно-следственные связи?
Тогда любой биграммный анализ — причинно-следственный. Не говоря уж о трех-, четырех- и т.д. n-граммном.
Кстати, Гугл продает статистику пентаграмм для английского языка. Не интересует?
Ваш алгоритм — подвид обычных марковских цепей, где вероятности принимают только 2 значения (0 и 1). Так же точно Вы собираете статистику, только оставляете одну цепочку, а не несколько с разными весами. Критерий разделения цепочек между категориями — тоже известная вещь.
А что до творчества — машина обыгрывает чемпиона в шахматы, сочиняет неплохие с виду стихи (кстати, тоже марковскими методами), оптимально торгует на бирже, и… что? Это интеллект и творчество?
Кстати, Гугл продает статистику пентаграмм для английского языка. Не интересует?
Ваш алгоритм — подвид обычных марковских цепей, где вероятности принимают только 2 значения (0 и 1). Так же точно Вы собираете статистику, только оставляете одну цепочку, а не несколько с разными весами. Критерий разделения цепочек между категориями — тоже известная вещь.
А что до творчества — машина обыгрывает чемпиона в шахматы, сочиняет неплохие с виду стихи (кстати, тоже марковскими методами), оптимально торгует на бирже, и… что? Это интеллект и творчество?
Насколько я понимаю, биграммный шифр — это метод преобразования. Я же рассматриваю текст как последовательность символов. Если есть последовательность, то из нее легко выделить предпосылки и следствия.
Насчет статистики пентаграмм спасибо, я подумаю об их покупке. И насчет ссылки на Маркова тоже спасибо, думаю это будет полезно освежить это в памяти.
По поводу творчества могу сказать следующее, машина далеко не самостоятельна. Она делает то, что ей говорят. А если не делает — то «глючит» и ее надо «починить». Впрочем, я считаю, что заложенные алгоритмы составляют интеллект, ведь с помощью их она принимает решение. Но творчество появится тогда, когда появится самостоятельность. Вы посмотрите что происходит сейчас — если сейчас машине не надо производить вычисления, то в halt ее в halt! Концлагерь какой-то…
Насчет статистики пентаграмм спасибо, я подумаю об их покупке. И насчет ссылки на Маркова тоже спасибо, думаю это будет полезно освежить это в памяти.
По поводу творчества могу сказать следующее, машина далеко не самостоятельна. Она делает то, что ей говорят. А если не делает — то «глючит» и ее надо «починить». Впрочем, я считаю, что заложенные алгоритмы составляют интеллект, ведь с помощью их она принимает решение. Но творчество появится тогда, когда появится самостоятельность. Вы посмотрите что происходит сейчас — если сейчас машине не надо производить вычисления, то в halt ее в halt! Концлагерь какой-то…
Биграмма — последовательность из 2-х символов в тексте.
N-грамма — последовательность из n символов в тексте.
Из них набирается словарь и считается статистика.
На мой взгляд, Вы делаете РОВНО то же самое.
Дальше по этой статистике Вы делаете и классификацию и кластеризацию (последнее Вы называете мэйнстримом). То, что не укладывается (прочее) можно считать «новыми идеями».
Однако относительная доля мусора в этом остатке, естественно, возрастает. Копаться в этом "..." ради редких жемчужин вряд ли кто-то захочет.
N-грамма — последовательность из n символов в тексте.
Из них набирается словарь и считается статистика.
На мой взгляд, Вы делаете РОВНО то же самое.
Дальше по этой статистике Вы делаете и классификацию и кластеризацию (последнее Вы называете мэйнстримом). То, что не укладывается (прочее) можно считать «новыми идеями».
Однако относительная доля мусора в этом остатке, естественно, возрастает. Копаться в этом "..." ради редких жемчужин вряд ли кто-то захочет.
вообще-то «новые идеи» являются новыми для самого алгоритма, который лопатит информацию не так уж и долго по времени. Взрослого человека конечно же не особо будет интересовать то, что является откровением для ребенка. Я считаю, что тут вопрос лишь во времени.
Но важно не это. Я считаю, что можно продвинуться дальше и сделать так, чтобы система смогла извлекать выгоду от тех идей, которые найдет.
Но важно не это. Я считаю, что можно продвинуться дальше и сделать так, чтобы система смогла извлекать выгоду от тех идей, которые найдет.
Алгоритму-то наплевать, что это: «новые идеи» или нестандартные комбинации n-грамм.
Эффект будет ровно один и тот же.
Вот еще трудность: с ростом словаря n-грамм будет расти время обработки входного потока. Причем при широких границах n разнообразие n-грамм, а, следовательно, и объем словаря неограничен.
Эффект будет ровно один и тот же.
Вот еще трудность: с ростом словаря n-грамм будет расти время обработки входного потока. Причем при широких границах n разнообразие n-грамм, а, следовательно, и объем словаря неограничен.
Нестандартные дестабилизирующие комбинации n-грамм — это юмор. А вот неожиданно всплывающая стабильная комбинация n-грамм — это уже идея. Вы так не думаете?
Кстати, у юмора тоже есть своя теоретическая основа. Тот же Петросян, составляя свои выступления, тоже действует по системе. Я об этом как-то читал.
Пока я еще не пришел к пониманию того, как можно пользоваться идеями, но я попытаюсь это понять. А как пойму, так и эффект будет.
По поводу трудности скажу, что сложность алгоритма n*log(n), где n — длинна текста. Мне кажется, что это не так уж и плохо. Например, у алгоритма быстрой сортировки сложность такого же уровня.
Кстати, у юмора тоже есть своя теоретическая основа. Тот же Петросян, составляя свои выступления, тоже действует по системе. Я об этом как-то читал.
Пока я еще не пришел к пониманию того, как можно пользоваться идеями, но я попытаюсь это понять. А как пойму, так и эффект будет.
По поводу трудности скажу, что сложность алгоритма n*log(n), где n — длинна текста. Мне кажется, что это не так уж и плохо. Например, у алгоритма быстрой сортировки сложность такого же уровня.
А, понял, нестандарт — юмор. Давайте сначала напомню анекдот про стандартные комбинации:
«Комиссия входит в сумасшедший дом, все пациенты собрались в кружок.
Один из пациентов говорит: „18“ — все смеются, другой: „24“ — снова смех.
Комиссии поясняют: все анекдоты пронумерованы, чтобы не терять время на рассказ.
Вдруг кто-то говорит: „44“ — молчание, а затем возглас: „Как не стыдно, здесь дамы!“
Так что, вряд ли. Поясню.
Нестандарта при ограниченном наборе n-грамм просто не будет.
А при неограниченном — его будет все больше и больше (закон Ципфа пока никто оспорить не смог). В этом случае Ваши нынешние 2Гб — так, семечки. И Вы считаете, что основная часть — юмор?
А что до сложности, неограниченность роста этого самого n гарантирует неограниченную сложность.
Попробуйте отсортировать массив хотя бы из триллиона элементов.
«Комиссия входит в сумасшедший дом, все пациенты собрались в кружок.
Один из пациентов говорит: „18“ — все смеются, другой: „24“ — снова смех.
Комиссии поясняют: все анекдоты пронумерованы, чтобы не терять время на рассказ.
Вдруг кто-то говорит: „44“ — молчание, а затем возглас: „Как не стыдно, здесь дамы!“
Так что, вряд ли. Поясню.
Нестандарта при ограниченном наборе n-грамм просто не будет.
А при неограниченном — его будет все больше и больше (закон Ципфа пока никто оспорить не смог). В этом случае Ваши нынешние 2Гб — так, семечки. И Вы считаете, что основная часть — юмор?
А что до сложности, неограниченность роста этого самого n гарантирует неограниченную сложность.
Попробуйте отсортировать массив хотя бы из триллиона элементов.
Все таки, при n=512 нестандартные комбинации будут встречаться еще очень и очень долго. А если пустот, все таки, станет маловато, то n можно будет увеличить.
Кстати, говоря о сложности я имел ввиду, что n — это длина обрабатываемого текста вне зависимости от длин хранящихся в памяти цепочек. Впрочем, максимальную длину цепочки я все-таки ограничил. Поэтому, сложность алгоритма на больших объемах информации становится почти линейной.
По сути, рассказанная в анекдоте история не имеет права на жизнь, так как анекдот интересен своей неожиданностью. Ну, а раз так то история сама становится анекдотичной.
С другой стороны, даже при неограниченном n могут образовываться места скопления n-грамм. Если текст специальным образом подготовить (например, сделать преобразования Фурье), то места скопления будут более или менее систематическими и можно будет выявлять закономерности.
Дальше уже вопрос будет не в величине n, а в количестве действующих закономерностей. Размер базы данных, конечно будет достаточно большим, но:
1. От размера базы будет зависеть подготовленность алгоритма к распознанию новизны. А знание — это сила. Если же будет сила, то будет и возможность подбавить вычислительной мощности.
2. При необходимости, слишком редко встречающиеся или малозначимые комбинации можно удалять. И тогда количество юмора в хранилище уменьшится, а количество информации о закономерностях, соответственно, увеличится.
Но зря вы так скептически относитесь к юмору. В известном афоризме говорится, что добрым словом и пистолетом можно добиться значительно большего, чем одним только добрым словом. Так же и с юмором: знанием и юмором можно добиться значительно большего, чем одним только знанием. Так как юмор может помочь там, где знаний нет.
Кстати, говоря о сложности я имел ввиду, что n — это длина обрабатываемого текста вне зависимости от длин хранящихся в памяти цепочек. Впрочем, максимальную длину цепочки я все-таки ограничил. Поэтому, сложность алгоритма на больших объемах информации становится почти линейной.
По сути, рассказанная в анекдоте история не имеет права на жизнь, так как анекдот интересен своей неожиданностью. Ну, а раз так то история сама становится анекдотичной.
С другой стороны, даже при неограниченном n могут образовываться места скопления n-грамм. Если текст специальным образом подготовить (например, сделать преобразования Фурье), то места скопления будут более или менее систематическими и можно будет выявлять закономерности.
Дальше уже вопрос будет не в величине n, а в количестве действующих закономерностей. Размер базы данных, конечно будет достаточно большим, но:
1. От размера базы будет зависеть подготовленность алгоритма к распознанию новизны. А знание — это сила. Если же будет сила, то будет и возможность подбавить вычислительной мощности.
2. При необходимости, слишком редко встречающиеся или малозначимые комбинации можно удалять. И тогда количество юмора в хранилище уменьшится, а количество информации о закономерностях, соответственно, увеличится.
Но зря вы так скептически относитесь к юмору. В известном афоризме говорится, что добрым словом и пистолетом можно добиться значительно большего, чем одним только добрым словом. Так же и с юмором: знанием и юмором можно добиться значительно большего, чем одним только знанием. Так как юмор может помочь там, где знаний нет.
извините, я правильно понимаю, что вы утверждаете, что сделали семантическую классификацию текста с помощью синтаксического разбора, при чём не какого-то особенного, а просто нахождения редакционного расстояния?
извините, но хоть какие-нибудь наглядные результаты есть, кроме странного сайта, на котором просто куча спарсенного RSS?
извините, но хоть какие-нибудь наглядные результаты есть, кроме странного сайта, на котором просто куча спарсенного RSS?
вы не подумайте ничего плохого. просто мы сами некоторое время уже раздумываем об алгоритмах семантического анализа новостей, и если ваш алгоритм настолько действеннен, как вы его описываете, то мы бы его может даже купили.
однако у меня огромный скептицизм на этот счёт. мы работали некоторое время с журналистами, и знаем специфику создания текстов ими. часто бывает, что статья в какое-нибудь СМИ создаётся журналистом методом «накопируй разных предложений из разных источников, отсортируй, чтоб схожее по смыслу было рядом». из-за этого часто поиск в гугле по выдранному из текста предложению выдаёт десяток-другой точных совпадений в разных, казалось бы, статьях. это может оказаться и единственной причиной кажущейся эффективности вашего алгоритма.
а абзац про
> Я так думаю, что алгоритм сгодится не только для анализа текстов, но и для
ещё больше подливает масла в огонь. как бы это не оказалось просто вашим максимализмом.
однако у меня огромный скептицизм на этот счёт. мы работали некоторое время с журналистами, и знаем специфику создания текстов ими. часто бывает, что статья в какое-нибудь СМИ создаётся журналистом методом «накопируй разных предложений из разных источников, отсортируй, чтоб схожее по смыслу было рядом». из-за этого часто поиск в гугле по выдранному из текста предложению выдаёт десяток-другой точных совпадений в разных, казалось бы, статьях. это может оказаться и единственной причиной кажущейся эффективности вашего алгоритма.
а абзац про
> Я так думаю, что алгоритм сгодится не только для анализа текстов, но и для
ещё больше подливает масла в огонь. как бы это не оказалось просто вашим максимализмом.
Может быть в моих словах и можно учуять запах максимализма, но говоря я стараюсь опираться на то, что видел, то есть, на результат работы алгоритма. При некоторых настройках он действительно не очень хорошо работает. Но как мне кажется, мне удалось его сбалансировать.
Кстати, алгоритм можно использовать для поиска, так как он ориентируется не на ключевые слова и вообще не на слова, а на максимально близкие ассоциации по каждому символу в тексте. Что позволяет снизить влияние ошибок/опечаток.
Кстати, алгоритм можно использовать для поиска, так как он ориентируется не на ключевые слова и вообще не на слова, а на максимально близкие ассоциации по каждому символу в тексте. Что позволяет снизить влияние ошибок/опечаток.
> на максимально близкие ассоциации по каждому символу в тексте
максимально близкая ассоциация в тексте к символу «А» — символ «Б»? да вы шутите, либо рвёте мне шаблон. я склоняюсь к первому.
требую срочно предоставить описание алгоритма, иначе подумаю, что на хабре одним школьником больше.
максимально близкая ассоциация в тексте к символу «А» — символ «Б»? да вы шутите, либо рвёте мне шаблон. я склоняюсь к первому.
требую срочно предоставить описание алгоритма, иначе подумаю, что на хабре одним школьником больше.
Основная идея алгоритма описана во втором комментарии к этой статье. Благодаря Trept'у я теперь знаю, что это разновидность марковской цепи. Если нужны еще подробности, спрашивайте — отвечу.
Если что, прошу меня простить. Я не хотел рвать вам никакой шаблон.
Если что, прошу меня простить. Я не хотел рвать вам никакой шаблон.
Я этому тоже подивился, поэтому и спросил про возможность использования целых слов, а не символов. Если использовать слова, то можно построить матрицу расстояний и свести все к кластеризации термов по этой матрице.
В моем случае рассматриваются не слова, а символы, что позволяет набрать значительно больше статистики и снизить влияние шума/ошибок/опечаток. Вот если вы напишите слово с ошибкой, то Гугл его не найдет, а вы найдете в чем ошибка, и мой алгоритм с большой долей вероятности найдет к нему близкое верное слово.
Ну это и есть эффект редакционного расстояния. Я просто пытаюсь понять возможности и ограничения подобного «синтаксически-ориентированного» алгоритма.
вы гуглом пользовались давно? у них шикарная защита от опечаток в виде предположений «возможно, вы имели в виду». а у вас в русском языке будет огромное количество коллизий, к примеру «муха» и «меха» будут иметь одинаковое значение относительно опечатки «мха», даже если вы вводили «размножение мха». с большим успехом вместо вашего алгоритма можно было бы использовать diff. он хотя бы не имеет сложность O(n^n).
Классификация текста — это побочный продукт алгоритма. Я считаю, что алгоритм имеет значительно более широкие возможности, так как он выстраивает причинно-следственные связи. А это значит, что его можно использовать для предугадывания событий.
Если говорить о классификации, то, как мне кажется, мне удалось достигнуть оптимального уровня. Некоторые внутренности алгоритма можно увидеть здесь: creature.pishi.info/associate2/. По понятным причинам, я отключил запись, но в памяти уже достаточно, чтобы результат был интересен. Кое что там самопоясняющееся, а если что заинтересует конкретно — спрашивайте.
Если говорить о классификации, то, как мне кажется, мне удалось достигнуть оптимального уровня. Некоторые внутренности алгоритма можно увидеть здесь: creature.pishi.info/associate2/. По понятным причинам, я отключил запись, но в памяти уже достаточно, чтобы результат был интересен. Кое что там самопоясняющееся, а если что заинтересует конкретно — спрашивайте.
ввел туда одну старую новость из своей RSS ленты
правильно ли я понял что топик считается юмором? Сложно что-либо понять из внутренностей ибо все там меряется в попугаях…
Москву и Московскую область окутал едкий торфяной дым. Насколько он опасен для здоровья и как можно уменьшить неблагоприятное воздействие гари на организм? Читаем здесьВыдало вроде как:
[extremetopic] => Humor
[brothershiptopic] => Ideaправильно ли я понял что топик считается юмором? Сложно что-либо понять из внутренностей ибо все там меряется в попугаях…
с каждым новым комментарием вы всё больше мне напоминаете автора BolgenOS.
мне очень жалко прошлый хабрахабр, который теперь выдаёт инвайты таким, как вы.
мне очень жалко прошлый хабрахабр, который теперь выдаёт инвайты таким, как вы.
случайно нажал на отправку раньше, чем надо. по вашей ссылке из 10 самых первых и самых популярных новостей за неделю (а я знаю, что это так, т.к. мой бизнес сейчас основан на новостях) 10 попали в рубрику юмор.
я пас, и ничего не понимаю в этой жизни. 32 плюса в карму новичку за какую-то [censored].
я пас, и ничего не понимаю в этой жизни. 32 плюса в карму новичку за какую-то [censored].
Очевидно вы смотрели на переменную extremetopic, а надо было смотреть на topic2, так как детектированный раздел отображается там.
Впрочем, не смею больше отнимать у вас время.
Впрочем, не смею больше отнимать у вас время.
нет, ни в коем случае не на extremetopic.
topic и topic2 там по ссылке были патологически пусты, перепроверил сейчас снова. я смотрел по цифрам, выдаваемым в «topics», т.к. подумал, что это означает предположительный вес детектирования темы. странно, но кроме «Humour» ещё большие цифры выдавались на Sport и Top news. возможно я ошибся, и эти цифры ничего не означают, но тогда этот алгоритм мне вообще ничего не выдал ни на одну новость.
topic и topic2 там по ссылке были патологически пусты, перепроверил сейчас снова. я смотрел по цифрам, выдаваемым в «topics», т.к. подумал, что это означает предположительный вес детектирования темы. странно, но кроме «Humour» ещё большие цифры выдавались на Sport и Top news. возможно я ошибся, и эти цифры ничего не означают, но тогда этот алгоритм мне вообще ничего не выдал ни на одну новость.
topic пуст потому, что он используется для запоминания информации, а от вас эту информацию для запоминания я не запрашиваю.
topic2 пуст, очевидно, потому, что система не может для вашего текста однозначно определить категорию, а поэтому не принимает решения. В случае новостного ресурса система сохранит ту категорию, которая будет ей дана перед началом анализа.
Далее по выбранному/данному топику будет взято значение из loyaltopic и если оно будет слишком мало, то новость будет отсеяна как непопулярная. Если же новость важна, то о ней обязательно напишут еще раз и еще раз, и будут по разному оформлять. После нескольких повторов, во-первых, накопится ассоциативная информация по разделу для данной информации, что позволит точнее определить категорию, а, во-вторых, повысит популярность сообщения и вероятность его публикации.
Можно, конечно, модифицировать алгоритм для того, чтобы он точнее определял категорию с первого анализа, но тогда для анализа потребуется значительно больше вычислительных ресурсов. Но надо ли это, если информация с большой долей вероятности все равно будет отсеяна?
topic2 пуст, очевидно, потому, что система не может для вашего текста однозначно определить категорию, а поэтому не принимает решения. В случае новостного ресурса система сохранит ту категорию, которая будет ей дана перед началом анализа.
Далее по выбранному/данному топику будет взято значение из loyaltopic и если оно будет слишком мало, то новость будет отсеяна как непопулярная. Если же новость важна, то о ней обязательно напишут еще раз и еще раз, и будут по разному оформлять. После нескольких повторов, во-первых, накопится ассоциативная информация по разделу для данной информации, что позволит точнее определить категорию, а, во-вторых, повысит популярность сообщения и вероятность его публикации.
Можно, конечно, модифицировать алгоритм для того, чтобы он точнее определял категорию с первого анализа, но тогда для анализа потребуется значительно больше вычислительных ресурсов. Но надо ли это, если информация с большой долей вероятности все равно будет отсеяна?
Поскольку описания алгоритма в статье нет, не стоит ли ее поместить в раздел «Я пиарюсь»? Что она делает в профильном блоге, если технических подробностей никаких?
Относительно производительности в этом проекте рекомендую использовать TJ7
Пробовали на хабра-комментариях?
Совпадают ли выводы алгоритма с оценкой общественности, выраженной в плюсах?
Совпадают ли выводы алгоритма с оценкой общественности, выраженной в плюсах?
Ну вот на данный момент топ-комент по этой статье:
> Это всё конечно хорошо, но будет ли разобран/открыт алгоритм/код
Если выводы алгоритма будут совпадать с ним, вам это что-то скажет о его эффективности? :)
> Это всё конечно хорошо, но будет ли разобран/открыт алгоритм/код
Если выводы алгоритма будут совпадать с ним, вам это что-то скажет о его эффективности? :)
Только в некоторых из них, хотя они не всегда буду даже в рамках средних плюсиков…
Просто потому что специалистов всегда меньше чем людей, читающих наискось строчки 3-4 запроса к БД на символ, и коментирующих нечто вроде Хороший алгоритм. Производители и продавцы железа будут довольны. Или уточняющих в каком блоге правильно разместить вашу статью.
К сожалению.
Просто потому что специалистов всегда меньше чем людей, читающих наискось строчки 3-4 запроса к БД на символ, и коментирующих нечто вроде Хороший алгоритм. Производители и продавцы железа будут довольны. Или уточняющих в каком блоге правильно разместить вашу статью.
К сожалению.
И всё-таки! Ближайшее будущее за высокоэффективными технологиями эвристико-смысловой обработки текстов. Математико-статистические и линвистические методики не оправдали себя и более того, показали свою беспомощность.
А ровно так, как у человека.
Ведь мы, когда общаемся с помощью языковых коммуникаций, не вычисляем ни морфологию, ни синтаксис, ни семантику. Люди и мыслят и понимают друг друга с помощью Моделей Поведения Образов (Объектов). Они перманентно выстривают эти МПО в своём сознании всю жизнь и пользуются ими для декодирования естественно-язычных сообщений.
Процесс извлечения из памяти этих МПО протекает эвристически, а осмысление текста (речи) человек осуществляет с целью понимания (распознавания) мыслей, которые автор заложил в своё сообщение. (См. habrahabr.ru/post/142733/)
Ведь мы, когда общаемся с помощью языковых коммуникаций, не вычисляем ни морфологию, ни синтаксис, ни семантику. Люди и мыслят и понимают друг друга с помощью Моделей Поведения Образов (Объектов). Они перманентно выстривают эти МПО в своём сознании всю жизнь и пользуются ими для декодирования естественно-язычных сообщений.
Процесс извлечения из памяти этих МПО протекает эвристически, а осмысление текста (речи) человек осуществляет с целью понимания (распознавания) мыслей, которые автор заложил в своё сообщение. (См. habrahabr.ru/post/142733/)
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Автоматический анализ текста без модераторов