Watset

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 с заголовком, всего двенадцать колонок: путь к оцениваемому файлу, количество отношений в нём, количество верных отрицательных ответов, количество ложных положительных ответов, количество ложных отрицательных ответов, количество верных положительных ответов, точность, полнота, F₁-мера, ноль или позиция по точности при оценке значимости, ноль или позиция по полноте при оценке значимости, ноль или позиция по F₁-мере при оценке значимости.

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

Цитирование

Ustalov, D., Panchenko, A., Biemann, C., Ponzetto, S.P.: Watset: Local-Global Graph Clustering with Applications in Sense and Frame Induction. Computational Linguistics 45(3), 423–479 (2019)

@article{Ustalov:19:cl,
  author    = {Ustalov, Dmitry and Panchenko, Alexander and Biemann, Chris and Ponzetto, Simone Paolo},
  title     = {{Watset: Local-Global Graph Clustering with Applications in Sense and Frame Induction}},
  journal   = {Computational Linguistics},
  year      = {2019},
  volume    = {45},
  number    = {3},
  pages     = {423--479},
  doi       = {10.1162/COLI_a_00354},
  publisher = {MIT Press},
  issn      = {0891-2017},
  language  = {english},
}

Ссылки

См. также

Примечания

↑ Ustalov D., Panchenko A., Biemann C., Ponzetto S.P. (2019), Watset: Local-Global Graph Clustering with Applications in Sense and Frame Induction
↑ Dorow B., Widdows D. (2003), Discovering Corpus-Specific Word Senses
↑ Gfeller D., Chappelier J.-C., De Los Rios P. (2005), Synonym Dictionary Improvement through Markov Clustering and Clustering Stability
↑ Gonçalo Oliveira H., Gomes P. (2014), ECO and Onto.PT: a flexible approach for creating a Portuguese wordnet automatically
↑ Riedl M., Biemann C. (2016), Unsupervised Compound Splitting With Distributional Semantics Rivals Supervised Methods

[1] Ustalov D., Panchenko A., Biemann C., Ponzetto S.P. (2019), Watset: Local-Global Graph Clustering with Applications in Sense and Frame Induction

[Dorow03-2] Dorow B., Widdows D. (2003), Discovering Corpus-Specific Word Senses

[Gfeller05-3] Gfeller D., Chappelier J.-C., De Los Rios P. (2005), Synonym Dictionary Improvement through Markov Clustering and Clustering Stability

[GoncaloOliveira14-4] Gonçalo Oliveira H., Gomes P. (2014), ECO and Onto.PT: a flexible approach for creating a Portuguese wordnet automatically

[Riedl16-5] Riedl M., Biemann C. (2016), Unsupervised Compound Splitting With Distributional Semantics Rivals Supervised Methods

[1]

[2]

[3]

[4]

[5]