?

Log in

No account? Create an account

Компьютерная лингвистика

Новостная лента www.solarix.ru

Previous Entry Share Next Entry
Взаимная информация и алгоритм Леска для отбора ассоциаций: граф Бозон де Валуа
kelijah
Что там с бозоном?

У обычного человека, более-менее интересующегося околонаучными новостями, для слова "бозон" скорее всего ассоциируются "Хиггс",  "коллайдер" и прочее. А что можно сказать по поводу следующего фрагмента:

"Происхождение Бозона неизвестно. Он родился не позже 800 года. Известно о нём не очень много. Его владения находились в Италии."

Звучит странно? Странно. Тем не менее, это достоверный факт, насколько можно верить википедии - см. викистатью Бозон Древний. Вообще, со словом "бозон" связано множество викистатей, что делает вторую часть рассказа про взаимную информацию немного более интригующей.

Взаимная информация и Википедия

Как собрать информацию о том, с какими словами ассоциируется заданное слово?

Скачаем дамп Википедии. Я обычно беру в XML формате, благо он очень просто парсится потоковым XML парсером или даже врукопашную через функционал стандартных строковых операций поиск-вырезание. В августе этого года распаковый файл ruwiki-latest-pages-articles.xml имел размер около 20 Гб, то есть вкусной информации там много.

Каждая страница начинается тегом page. Заголовок статьи, который мы видим в википедии, оформлен тегом title. Содержимое статьи сидит внутри тега text, его тоже нетрудно вытащить чисто строковыми операциями.

Теперь берем слова заголовка и слова тела статьи (теги и вики-разметку вычищаем, конечно). Перебираем пары слов - первое слово из заголовка, второе из тела статьи. Для русской википедии желательно лемматизировать. Накапливаем частоты самих слов и частоты пар. Эта статистика нужна, чтобы вычислить потом
взаимную информацию для каждой пары слов. Взаимная информация для пары слов показывает, насколько они связаны. Если отсортировать все 2-граммы при фиксированном первом слове по убыванию величины взаимной информации, то получим для слова "бозон" что-то вроде такого списка:

бозон    взаимодействие    3,97367061825484E-06    110
бозон    частица    3,54734380896466E-06    99
бозон    флорида    2,00675274053238E-06    57
бозон    калибровочный    1,88544077616527E-06    39
бозон    амвросий    1,6800332438542E-06    40
бозон    хиггсовский    1,66107235059345E-06    29
бозон    каролина    1,61707258939835E-06    48
бозон    элементарный    1,55780812360871E-06    43
бозон    миссисипи    1,39087314664506E-06    36
бозон    масса    1,25770570109081E-06    50
бозон    стандартный    1,22869540247916E-06    41
бозон    модель    1,16914628660164E-06    48
бозон    квантовый    9,80003261048578E-07    31
бозон    алабама    9,22132459849188E-07    24
бозон    физик    9,17935188871866E-07    37
бозон    физика    8,91582333008874E-07    36
бозон    электронвольт    8,80786530663711E-07    18
бозон    заряд    8,26044452842102E-07    26
бозон    митрополит    8,01929214751853E-07    29
бозон    спин    7,97482386605151E-07    26
бозон    распад    7,96299593900728E-07    27
бозон    электромагнитный    7,66984165817137E-07    23
бозон    виргиния    7,12947024614312E-07    21
бозон    лептон    7,10239621974779E-07    15
бозон    кварк    7,08601349091444E-07    18
бозон    электрослабый    6,83616481760744E-07    14
бозон    слабый    6,73619857370767E-07    25
бозон    фундаментальный    6,59329938209836E-07    21
бозон    поле    6,2740136887719E-07    26
бозон    теория    6,26134436073209E-07    27
бозон    поля    6,25046725542973E-07    25
бозон    луизиана    6,2419057784623E-07    17


Третье поле как раз дает расчетную величину взаимной информации. Вроде бы неплохо, но из-за многозначности термина "бозон" в списке видна сильная ассоциация со словами типа "флорида". Это может мешать в некоторых случаях, например при генерации текста.

Артефакты многозначности в Википедии

Судя по всему, последовательность выгрузки статей Википедии соответствует последовательности ID этих статей в БД. Для многозначных терминов типа "бозон", когда есть превалирующее значение и множество более редких, это проявляется в том, что статья для "Бозон Хиггса" написана и выгружается в дамп намного раньше, чем другие статьи для бозона. Видимо, сначала викиавторы создали статью для самого ожидаемого значения, а потом, через значительное время, нашлись знатоки и других значений.

На практике при сборке mutual information это может проявляться необычным образом при отладке. Представьте себе, что вы отлаживаете код. Разумеется, сначала вы ограничите количество викистатей, которые обрабатывает сборщик, какой-то небольшой величиной, например 100,000. Проверяете результаты. Для слова "бозон" они содержат только ожидаемые ассоциации типа "физика", "взаимодействие", "коллайдер" и т.д. Отладка закончена, вы снимаете ограничение на число статей, ждете 3 часа, получаете таблицу ассоциаций по полной Википедии и наблюдаете много странного мусора в разных статьях. Снова отлаживаете, и так до тех пор, пока не возникает подозрение, что мусор появляется, если повышать ограничение на число статей.

Это не 100% достоверный факт, так что я не стал бы полагаться на него, но иметь в виду стоит.

Отбор правильных ассоциаций и алгоритм Леска

Итак, ассоциации у нас есть, но для многозначных слов они представляют из себя пересечение соответствующих ассоциативных облаков. Если у нас на вход пришла фраза, например "Бозон в коллайдере", возникает желание отсеять побочные смыслы слова "бозон" и оставить у него основное ассоциативное облако, полагаясь на контекст входной фразы. В данном случае контекстом будет слово "коллайдер".
Такую задачу решает очень старый, и в какой-то степени самоочевидный алгоритм Леска. Мы берем ассоциативные облака для слов входной фразы и оставляем те варианты, которые встречаются минимум в двух словах фразы (или дисконтируем вес неподтвержденных ассоциаций). Для слова "коллайдер" ассоциативное облако имеет вид примерно такой:

коллайдер    протон    4,88508886544732E-06    100
коллайдер    пучок    4,34556205387541E-06    93
коллайдер    столкновение    3,98019142057503E-06    96
коллайдер    частица    3,883858943155E-06    97
коллайдер    адронный    3,7787451861958E-06    66
коллайдер    энергия    3,60533084038241E-06    100
коллайдер    ускоритель    2,92787951289753E-06    61
коллайдер    детектор    2,8502328317765E-06    59
коллайдер    бак    2,58382073438321E-06    73
коллайдер    протонный    2,37991425311809E-06    45
коллайдер    бозон    2,37441636150546E-06    48
коллайдер    элемент    2,36604600862001E-06    76
коллайдер    кварк    2,3581617306672E-06    48
коллайдер    эксперимент    1,74617760420082E-06    48
коллайдер    светимость    1,70743535275565E-06    37
коллайдер    физик    1,46755247187626E-06    48
коллайдер    глюонный    1,4615422841239E-06    25
коллайдер    физика    1,32882079043766E-06    44
коллайдер    большой    1,30949283016725E-06    52
коллайдер    сгусток    1,20316511171473E-06    23
коллайдер    ядерный    1,02551826305267E-06    32
коллайдер    магнит    1,01266575332571E-06    23
коллайдер    ядро    1,00129041617246E-06    31
коллайдер    новость    9,47266853291297E-07    32
коллайдер    свинец    9,45576987061381E-07    23
коллайдер    коллаборация    9,06797304056402E-07    17


Итогом пересечения облаков имеем, что для фразы "бозон в коллайдере" остаются следующие ассоциации:

бозон ==> бозон взаимодействие частица элементарный физик физика кварк теория коллайдер адронный фотон
в ==> в
коллайдер ==> коллайдер частица адронный бозон кварк физик физика взаимодействие элементарный теория фотон


А для фразы "Бозон во Флориде" получаем:

бозон ==> бозон флорида каролина
во ==> во
флорида ==> флорида каролина


А исходники?

Исходные тексты сборщика mutial information на C#, а также прочие исходники для этого проекта (Python) тоже, видимо, выложу через какое время, в репозитории https://github.com/Koziev/NLP_Comp.