Watset

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

Суть

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

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

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

Алгоритм

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

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

Вход: граф $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'$
   
       for $u \in \text{ctx}(s)$
       
           $\hat{u} \gets\!\! \underset{u' \in\, \text{senses}(u)}{\arg\max} \text{sim}(\text{ctx}(s), \text{ctx}(u'))$
       
       $\widehat{\text{ctx}}(s) \gets \{\hat{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}$.

Цитирование

• Ustalov, D., Panchenko, A., Biemann, C.: Watset: Automatic Induction of Synsets from a Graph of Synonyms. In: Proceedings of the 55th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), Vancouver, Canada, Association for Computational Linguistics (2017) Accepted for publication.

@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},
  address   = {Vancouver, Canada},
  publisher = {Association for Computational Linguistics},
  language  = {english},
  note      = {Accepted for publication.}
}

См. также

• Chinese Whispers
• MaxMax
• Watlink