# Computing word senses by semantic mirroring and spectral graph partitioning

Conference paper (help)
Computing word senses by semantic mirroring and spectral graph partitioning
Authors: Martin Fagerlund, Magnus Merkel, Lars Eldén, Lars Ahrenberg
Citation: Proceedings of the 2010 Workshop on Graph-based Methods for Natural Language Processing  : 103-107. 2010
Editors:
Publisher: Association for Computational Linguistics, Stroudsburg, PA, USA
Meeting: 2010 Workshop on Graph-based Methods for Natural Language Processing
DOI: Define doi.
Search
Restricted: DTU Digital Library
Services
Format: BibTeX

Computing word senses by semantic mirroring and spectral graph partitioning analyze the bipartite graph among words in a English-Swedish lexicon using the H. Dyvik concept of semantic mirroring. Representing the translation of words by a translation matrix and translating back and forth several times the apply graph partitioning on the resulting graph.

##  Data

A English-Swedish lexicon of 14850 words represented in a translation matrix B, i.e., a binary matrix where the columns correspond to words in one language and rows words in the other language and a one indicating where a word is translated to another.

A word is represented in a vector with one for the row element corresponding to the word e.

##  Method

###  Construction of an adjacency matrix

A translation is a matrix-vector multiplication $\mathbf{B}' \mathbf{e}$

A "mirror operation" is $\mathbf{B}\mathbf{B}' \mathbf{e}$, e.g., translating from English to Swedish and back to English

They use a modification for the second matrix as they leave out the element corresponding to the word translated.

The modified mirroring operation is repeated one more time to obtain a symmetric adjacency matrix A.

###  Graph partitioning

They construct the graph Laplacian

$L = D - A = diag(diag(A)) - A$

The then look at the Fiedler vector, cutting it it two and compute the conductance between the two sets of words, choosing the cut with the smallest conductance. The procedure is repeated until the conductance reaches a human decided tolerance.

##  Evaluation

They made a small evaluation with two evaluators judged the results independently and coordinated.