本稿はアドベントカレンダー「言語学な人々 Annex Advent Calendar 2024」の3日目(12/3)の記事として書かれました。
目次のプラグインが上手く動かないので書いときます。
0.プロローグ
1. はじめに
2. 前提となる知識
2.1. 単語埋め込み
2.2. 巡回セールスマン問題
3. Word Tour (Sato, NAACL 2022)
4. 提案手法：Form Tour?
4.1. 語形埋め込み
4.2. 1次元埋め込みの結果
4.3. 応用①：連続的な色相の言語地図
4.4. 応用②：語形の多様さの指標
目次
プロローグ
ある日のこと。何か面白いことないかなぁとXを見ていたら、下に掲げるめちゃくちゃ面白い論文を見つけました。
Ryoma Sato. 2022. Word Tour: One-dimensional Word Embeddings via the Traveling Salesman Problem. In Proceedings of the 2022 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, pages 2166–2172, Seattle, United States. Association for Computational Linguistics.
Word Tourというネーミング、巡回セールスマン問題という意外性、一次元埋め込みという浪漫、すべて筆者のどストライクです。内容もと驚きと納得の連続で、予想どおりめちゃくちゃ面白い。
それから漠然と自分も巡回セールスマン問題を使って何かやりたいなぁと思っていたのですが、なかなか見つかりません。形容詞？敬語？もっと広く分割表？いろいろ思案して停滞していたのですが、答えは2年前のアドベントカレンダーにありました。
あ、そうだ。語形にも埋め込み表現があるんだった。
はじめに
というわけで、今回は巡回セールスマン問題を解くことで、語形の一次元埋め込みを得る手法について紹介します。
お忙しい方のために、こんなことして何が嬉しいのかをはじめに書いておきます。語形の一次元埋め込みは、大量の語形を似たもの同士が近くになるように並べたものです。これだけでも個人的には感動ですが、この並びを使えば色んな応用が考えられます。例えば埋め込みと色を対応させれば、語形の類似度によってアイコンの色を連続的に変える言語地図を作ることができます。また埋め込みの合計を用いて、語形の豊かさを評価することもできるかもしれません。とにかく、アイデア次第で色んなことに使える！はず……
図０）日本言語地図の分類を語形の一次元埋め込みで再現する
執筆にあたっては厳密な定式化はさておいて、何をやろうとしているのかが分かるということを優先します。というか筆者自身、自然言語処理エアプ民なので細かい部分は知らなかったり、勘違いしている部分が多分にあります。以上、2つの制約に由来する不正確な表現/語弊を予めお詫びいたします。
前提となる知識
この記事を読まれる方は言語処理に興味のある方ばかりというわけではないでしょうから、まず初めにWord Tour (Sato, NAACL 2022)の前提になっている「単語埋め込み」と「巡回セールスマン問題」について説明します。そんなの知ってるよ～ということは飛ばしちゃってください。
また「説明」とはいいましたが、筆者自身もこの方面に明るいというわけではないので、あくまで実用的な説明ということでご容赦ください。
単語埋め込み（Word embedding）
単語埋め込みは単語の意味や関係性を数値で表現する技術の一つです。意味の近い単語は似たような単語埋め込みを持ちます。余談ですが、このように表現された数値のことも単語埋め込みと呼びます。区別のために後者を埋め込み表現とか、埋め込みベクトルとかともいいますが、本稿では特に厳密に使い分けていません（読みにくてごめんなさい）。
さて、そんな都合のいい「意味の数量化」はどのように達成できるのでしょうか。ここでは、ごく簡単な例と方略で単語埋め込みを作ってみましょう。まずあるコーパスで「りんご」「ぶどう」「犬」の共起語を調べると下のような結果になったと考えます。
| 甘い | 食べる | 飼う | 買う | かわいい | 吠える | |
| りんご | 34 | 45 | 2 | 45 | 21 | 0 |
| ぶどう | 32 | 55 | 1 | 39 | 10 | 2 |
| 犬 | 2 | 23 | 45 | 18 | 56 | 35 |
1列目をラベルとみれば、各行は6次元のベクトルとして表現できます。
りんご：[34, 45, 2, 45, 21,0]
ぶどう：[32, 55, 1, 39, 10, 2]
犬 ：[2, 23, 45, 18, 56, 35]
実はこれが既に単語埋め込みになっています。もちろん、このベクトルは当該単語の周辺の単語の分布の状況を表しているだけですが、すぐに予想できるようにこれが近い単語同士は意味が似ていると考えられます。実際「りんご」と「ぶどう」のベクトルはよく似ていますが、「犬」のベクトルはそれらとは大きく異なっています。今回は3語を対象として、共起後も6つだけでしたが、もっと大きなコーパスでもっと多くの共起語について見れば更に精度があがります。実際には最新の単語埋め込みはもっとずっと頭の良い方法でこれを行っていますが、根本のアイデアはここで示した周辺の単語の頻度を数えるというものです。
ちなみにこのような単語の意味はその周辺の状況によって特徴づけられるというような考え方を意味の分布仮説といい、このような態度に立つ意味論を分布意味論といいます。初期の論文としては(Firth, 1957)も有名ですが、元祖は（Harris,1954）だそうです[1]。
とっても分かりやすい動画がYouTubeにありましたので紹介しておきます。
[1]HarrisはChomskyの先生です。
巡回セールスマン問題
続いて巡回セールスマン問題です。
巡回セールスマン問題 (Traveling Salesman Problem: TSP) とは、都市を巡回しながら訪問コスト（距離や時間など）が最小になる経路を求めるという古典的な最適化問題です。
これはかなりの難問でして、経由する都市や考慮すべきコストが少なければなんとか解けますがそれが増えると、TSPを解くのは途端に難しくなり高速な計算機を使っても膨大な時間がかかります。こういうのを計算複雑性理論では「NP困難」と言います。（正確には解くのがめっちゃムズイというだけでなく、もしかするとその解が合ってるかどうか確かめるのもめっちゃムズイかもしれないという条件もあります。）
え、そんなに難しいなら分析手法に使えないんじゃない？っていう話になりますが、巡回セールスマン問題は非常に有名で重要な問題なので様々な人がいろんな対処法を考えています。特にLin-Kernighan-Helsgaun法(LKH法)と呼ばれる手法はとても高速で、なんと10万個の都市を経由する問題でも高い精度で解を求めることができます。(Sato, NAACL 2022)もこの方法でTSPを解いています。
余談ですがTSPはNP困難な問題としてあまりに有名なのでスリラー映画「Travelling Salesman」にもなっています。あらすじやトレーラーを見る限り、とっても面白そうな映画なんですが手元のサブスクになくて見られずにいます。どなたか視聴できる方法をご存知でしたら教えてください。
Word Tour (Sato, NAACL 2022)
Word Tour (Sato, NAACL 2022)とは巡回セールスマン問題を応用した単語の一次元埋め込み手法です。上で述べたように単語埋め込みは多次元ベクトルとして表現されます。これを巡回セールスマン問題における都市だととらえ、都市間の移動距離を最小にするようなルート（順序）を考えます。そうすれば、同様の意味を持つ単語が順序的に近い位置に埋め込まれることが期待されるというわけです。
もちろん、単語の意味のすべての側面を1次元に埋め込むことはできません。このためWord Tour は埋め込みの満たしていて欲しい性質のうち、完全性を捨てて、健全性だけを保つという方針をとっています。単語埋め込みを信じて埋め込みが近い単語を取れば、それらは全て意味の似た単語であるが、ひょっとするとそれ以外にも意味の似た単語があるかもしれない、というような埋め込みです。これでも単語検索や文書検索には有用なんだそうです。また、何より高速で省メモリだというのは凄まじいメリットですね。
著者ご本人による大変分かりやすいプレゼンテーションがYouTubeにございますので、更に詳しく知りたい方はこちらをご覧ください。
提案手法：Form Tour?
さて、Word Tourによって巡回セールスマン問題は健全な一次元埋め込みを得る方法として有用であることが分かりました。ではこれを単語ではなく、語形に適用してみるのはどうでしょうか？似たような語形が近い位置に埋め込まれると期待されますが、これはかなり便利じゃないでしょうか？
では、早速やってみましょう。
語形埋め込み
まず、単語埋め込みのように語形の埋め込み表現を得ましょう。単語埋め込みでは意味の類似性を表現するために周辺の語の頻度を数えましたが、今回は形の類似性を表現するために、別の方法を考えます。いろんな方法がありますが、今回は語形に含まれる音韻素性の頻度を数えて多次元ベクトルを得ることにします。Bag of Featuresとでも呼びましょう。
それぞれの音韻素性については詳述しませんが、今回は取り急ぎ語形に含まれる下の12個の音韻素性の頻度を数え上げることで12次元のベクトルを得まることにします。
[±cons],[±son],[±voice],[±nas],[±cont],[±constr],[±strident],[±high],[±low],[±palatal],[±grave],[±labial]
こうすることで単純な編集距離や、アルファベットの頻度だけでは捉えられない音形の類似性を捉えることができます。
例えば「tokake」の音韻素性ベクトルは次のようになります。
TOKAKE：[ 3,3,3,0,3,3,0,2,1,1,4,1 ]
これは2年前のアドベントカレンダー企画にて近藤先生がお書きになっていた方法に、筆者が若干の拡張を加えたもので詳しくはこちらの記事に書いています。
可視化の方法
さて元となる語形埋め込みができたので後はTSPを解くだけですが、せっかくなので結果の表示方法も色々と工夫してみましょう。
TSPの結果は最適な経路（とそのコスト）です。いま、経由地点たる語形は多次元空間上の点なのでそれを想像するのは簡単ではありません。しかしここで大事なのは経路だけですから、解釈しやすいように同相な直線や円に写像してしまいましょう。
これは路線図を単純なグラフで表すことと似ています。大阪環状線の各駅は実際には図１）のように割とバラバラな位置にあります。しかし、電車に乗っている人からすれば、その順番とそれが繋がっているという情報だけあればいいので、好きなだけ伸び縮みさせて綺麗な円にしてしまえばいいのです。そういうわけで路線図は図２）のように極めて単純な円環グラフで表されます。
後は容易に想像される課題としては語形が多すぎるとラベル同士が重なってとっても見にくくなるということが考えられます。これは取り急ぎ、頻度などの何らかの情報で重み付けして透明度などを調節すれば、少しは見やすくなるでしょう。
Word Tour (Sato, NAACL 2022)は軽量化のために(?)、順序だけを保存しているので図２）の路線図のように地点の間隔に違いはありませんが、今回は距離（コスト）に応じて地点の間隔も変えるということにしておきます。
埋め込みの結果
さて、やっと準備ができました。それでは埋め込みをやってみましょう。
今回、使用したデータは『日本言語地図』（LAJDB）データベースです。データの公開・管理、ほんとにいつもありがとうございます。
「かまきり」「かたつむり」「なめくじ」「とかげ」「おたまじゃくし」「かえる」の語形について一次元埋め込みを得ると下のようになりました。上述のとおり、すべての語形を表示するとラベルが重なって訳が分かんないので頻度によって透明度を調整しています。
図３）一次元埋め込みの結果
さて、どうでしょう。頻度の高い語形が少ないものは比較的綺麗なクラスターに分かれてるような気もします。例えばなめくじの図では頻度の多いものとしてはNAMEKUZIRI類、MEMEKUZI類、HADAKANAMETO類、NAMEKUSI類、MAMEKUZIRI類、NAMEKUZI類、NAMETO類があるようです。まずまずの結果ではないでしょうか。
しかし、MEMEKUZI類とNAMEKUZI類はもっと近くにあってもいいかなと思いますし、NAMEKUZIRI類とMAMEKUZIRI類ももっと近くにあってほしいです。
(Sato, NAACL 2022)が整理しているように、これはTSPを解くという一次元埋め込みが、健全ではあるが完全ではないという性質に由来していると思います。上にも書きましたが、これは単語埋め込みが近い単語は似た意味の単語であるが、その逆が成り立つとは限らないということで、ひょっとするとそれ以外の場所にも意味の似た単語があるかもしれないということを意味しています。
佐藤さんご自身が使われていた色相のメタファーが非常に分かりやすかったので、それをお借りします。確かに単語埋め込みが近い単語は似た意味の単語ですが、似た意味の単語が全て近くに集まるというわけではなく図のように複数のクラスターに分かれて分布しています。
もっとも、語形を分類したいのなら語形ベクトルをPCRなんかで次元圧縮して観察したり、k-平均法でクラスター分析した方がいいと思います。とはいえ、完全ではなくても語形の特徴を表す一次元の量というのはかなり便利です。次節以降はこれを使ったいろんな応用を考えてみます。
応用：連続的な色相の言語地図
なんでもメタファーとして出していますが、1次元埋め込みは色相に対応させることができます。上で示した「とかげ」円環グラフに色をつけると図５のようになります。
これを使えば言語地図のよりよい可視化ができるかもしれません。（ただし埋め込みが完全でないことに注意は必要です。）
言語地図とはどのような語形や発音がどこに現れるかを項目ごとにアイコンを付したり、等語線を引くなどして表した地図のことですが、語形の分布を見やすくするために似た語形に似たアイコンを与えるという工夫が施されています。今回得た一次元埋め込みを使って語形の特徴に応じてラベルの色を変化させると更に分布を把握しやすくなるかもしれません。
今回目指すのは連続的な色の変化ですが、語形の分類を自動化してアイコンを割り当てるという方法は2年前のアドベントカレンダー企画の記事に詳しく書かれています。気になる方はぜひそちらをご参照ください。
本当はGoogle Maps APIで動的な地図を作ろうとしてたんですけど、なんだかうまく行かなかったので取り急ぎ、matplotlib+cartopyで静的な地図を作りました。
どうでしょうか、まあまあ分布が見やすくなってるんじゃないでしょうか。繰り返しになりますが、埋め込みは完全ではないので、近い色の語形は似ていますが、似ているからといって必ずしも近い色が割り当てられるとは限りません。
確認のために本家の日本言語地図と比べてみましょう。
見比べてみると、本家の日本地図の色分けをざっくりと再現できていそうです。完璧に再現できるわけではありませんが、語形を分類し、似たようなアイコン、色を考えて配置するというこの一連のプロセスが自動でできるというのはかなり大きな魅力ではないでしょうか。
応用：語形の多様さの指標
語形の多様さを表す単純な指標としては異なり数を数えるということが考えられます。しかし、全く形の異なる語形が10個あるような語ととても似ている語形のグループが二つあって、異なり数は15であるというような場合はどうでしょう。異なり数では語形同士の類似を考慮できないので、後者の方が語形が多様だということになりますが、語形の類似を考慮して前者の方を多様だとする方がよいこともあるでしょう。そういう場合に語形埋め込みの最適輸送経路（総コスト）はよい指標になるかもしれません。
語形埋め込みの最適輸送経路（総コスト）は、経由地点が色んな所にあると大きくなります。大雑把に言って総コストが大きいということは語形埋め込みが埋め込み空間においてどれだけバラバラに配置されているかということです。
今回調べた6語だと、かたつむりが最も語形が多様で、なめくじが最も一様ですね。（多様の対義語って一様なんですかね？ムズイ……）
終わりに
以上、巡回セールスマン問題を解くことで語形の一次元埋め込みを得る方法について述べました。Word Tour (Sato, NAACL 2022)に触発されて「自分もTSP使って何かやりたい！！！」ということだけでやってみました。定式化や検証は全く十分ではありませんが、楽しんでいただけましたら幸いです。
もっと良い埋め込みを得るにはどうしたらいいか、TSPによる埋め込みは他にはどんな応用の可能性があるのか、今後も考えていきたいと思います。
参考文献
Sato(NAACL 2022)以外は言及しただけですが……
Harris, Z. (1954). Distributional structure. Word, 10(23): 146-162.
Firth, J.R. (1957) A Synopsis of Linguistic Theory, 1930-1955. In: Firth, J.R., Ed., Studies in Linguistic Analysis, Blackwell, Oxford, 1-32.
Sato, R. (2022). Word Tour: One-dimensional Word Embeddings via the Traveling Salesman Problem. In Proceedings of the 2022 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, pages 2166–2172, Seattle, United States. Association for Computational Linguistics.
使用したデータ
『日本言語地図』（LAJDB）データベースのデータを利用しました。データの管理・公開に感謝いたします。