Watset

Материал из NLPub
Перейти к: навигация, поиск

Watset — метод обнаружения понятий в графе синонимов, основанный на кластеризации графа значений слов.[1]

Суть

Пусть имеется неориентированный граф G = (V, E), множество вершин V которого образуется множеством известных слов, а множество рёбер E сформировано так, что (v, u) \in E \iff слова v \in V и u \in V являются синонимами. Необходимо построить такое множество понятий S, что составляющие его элементы, именуемые понятиями, содержат близкие по лексическому значению слова.

В основе метода Watset лежит предположение о структуре графов многозначных слов[2] и допущение о кликах в графах синонимов.[3] Метод Watset предназначен для выделения значений слов в графе G и объединения близких по значению слов во множество понятий S. Данный метод включает в себя четыре этапа, в том числе предварительный этап построения графа синонимов на основе исходных словарей синонимов. В таком графе осуществляется вывод значений каждого слова. После этого производится связывание значений слов друг с другом и формирование графа значений слов. Кластеризация графа значений слов группирует близкие значения слов в понятия и является финальным этапом работы метода.

Концептуально, метод Watset близок к двум первым этапам подхода ECO[4], но на этапе кластеризации явным образом осуществляется вывод значений слов.

Алгоритм

Кластеризация эго-сети слова.
Кластеризация графа значений слов.

Вход: граф G=(V, E), алгоритмы жесткой кластеризации \text{Cluster}_\text{Local} и \text{Cluster}_\text{Global}.

Алгоритм:

   for u \in V
   
       C \gets \text{Cluster}_\text{Local}(\text{Ego}(u))
       
       for i \gets 1\dots|C|
       
           \text{ctx}(u^i) \gets C_i
           
           \text{senses}(u) \gets \text{senses}(u) \cup \{u^i\}
   
   V' \gets \bigcup_{u \in V} \text{senses}(u)
   
   for s \in V'
       
       \widehat{\text{ctx}}(s) \gets \{{\arg\max}_{u' \in\, \text{senses}(u)} \text{sim}(\text{ctx}(s), \text{ctx}(u')): u \in \text{ctx}(s)\}
   
   E' \gets \bigcup_{s \in V'} \{s\} \times \widehat{\text{ctx}}(s)
   
   \mathcal{S} \gets \text{Cluster}_\text{Global}(V', E')

Выход: граф значений слов (V', E') и множество кластеров \mathcal{S}.

Использование

Из-за особенностей работы локалей, рекомендуется выполнять все команды в окружении с установленными переменными окружения LANG=en_US.UTF-8 и LC_COLLATE=C. Это сэкономит много времени и нервов.

Установка зависимостей

Watset требует несколько внешних библиотек и утилит для работы. Их загрузка и сборка осуществляется автоматически при помощи специальной команды. Утилиты устанавливаются локально.

$ make deps

Загрузка исходных данных

Пример исходных данных может быть получен путём выполнения команды make в корневой директории Watlink.

$ make data-ru data-en

При загрузке части русскоязычных данных может возникнуть ошибка, связанная с отсутствием в свободном доступе тезаурусов РуТез и RuWordNet. Возникновение этих ошибок не препятствует выполнению команд в Makefile.

Выполнение алгоритма Watset

$ EDGES=edges.txt ./impl/watset.sh

Оценка качества

Метод оценки качества на основе сопоставления пар синонимов с золотым стандартом представлен в программе eval/pairwise.py. Программа работает в режиме командной строки и принимает следующие аргументы:

  • --gold — путь к файлу с парами значений слов в золотом стандарте;
  • --significance — определение статистической значимости результатов (выключено по умолчанию);
  • --alpha — уровень значимости при определении статистической значимости результатов (по умолчанию 0.01);
  • path — путь к файлу с результатами, можно указать несколько разных файлов.

Определение статистической значимости основано на вычислении меры качества для каждого слова и проверке критерия Уилкоксона для связных выборок.[5] Не рекомендуется включать опцию --significance без особой надобности: это существенно удлиняет процесс вычислений.

$ eval/pathwise.py --gold=data/ru/rwn-pairs.txt impl/maxmax-pairs.txt impl/watset-cw-nolog-mcl-pairs.txt >pairwise-rwn.tsv

В программе использован параллелизм независимых задач с обработкой в нескольких процессах. Программа использует все доступные ядра ЦПУ для ускорения вычислений.

Формат файла с результатами оценки — TSV с заголовком, всего двенадцать колонок: путь к оцениваемому файлу, количество отношений в нём, количество верных отрицательных ответов, количество ложных положительных ответов, количество ложных отрицательных ответов, количество верных положительных ответов, точность, полнота, F1-мера, ноль или позиция по точности при оценке значимости, ноль или позиция по полноте при оценке значимости, ноль или позиция по F1-мере при оценке значимости.

При работе с результатами удобно использовать сортировку и разбиение по колонкам в терминале: sort -t $'\t' -g -k9r pairwise-rwn.tsv | column -t | less.

Цитирование

@inproceedings{Ustalov:17:acl,
  author    = {Ustalov, D. and Panchenko, A. and Biemann, C.},
  title     = {{Watset: Automatic Induction of Synsets from a Graph of Synonyms}},
  booktitle = {Proceedings of the 55th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers)},
  year      = {2017},
  pages     = {1579--1590},
  doi       = {10.18653/v1/P17-1145},
  address   = {Vancouver, Canada},
  publisher = {Association for Computational Linguistics},
  language  = {english},
}

Ссылки

См. также

Примечания