\documentclass[japanese,other]{jnlp_3.5}
\usepackage{jnlpbbl_2.2}
\usepackage[dvipdfmx]{graphicx}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{url}
\usepackage{hangcaption_jnlp}
%%%%\usepackage{udline}
%%%%\setulminsep{1.2ex}{0.2ex}
%%%%\let\underline=\ul
\allowdisplaybreaks


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%% author's definition
%%%%\usepackage{mathtools}
%%%%\usepackage{amsthm}
\usepackage{booktabs}
%%%%\input{mathdef}
\newcommand{\boldx}{{\boldsymbol{x}}}
\newcommand{\boldX}{{\boldsymbol{X}}}
\newcommand{\boldd}{{\boldsymbol{d}}}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\Volume{29}
\Number{4}
\Month{December}
\Year{2022}
%%%%\Issuetitle{「　　　　」特集号}


\setcounter{page}{1297}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\jsubject{学会記事}
\jtitle{Word Tour: One-dimensional Word Embeddings via the Traveling Salesman Problem}
\jauthor{佐藤　竜馬\affiref{Author_1}\affiref{Author_2}}
\etitle{Word Tour: One-dimensional Word Embeddings via the Traveling Salesman Problem}
\eauthor{Ryoma Sato\affiref{Author_1}} 

\headauthor{佐藤}
\headtitle{Word Tour: One-dimensional Word Embeddings via the Traveling Salesman Problem}

\affilabel{Author_1}{京都大学}{Kyoto University}
\affilabel{Author_2}{RIKEN AIP}{RIKEN AIP}



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{document}
\maketitle


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{はじめに}

本解説記事では NAACL 2022 に採択された論文 ``Word Tour: One-dimensional Word Embeddings via the Traveling Salesman Problem'' \cite{sato2022word} について解説します．この論文では一次元の教師なし単語埋め込みを提案しました．これは従来の埋め込みよりも軽量かつ解釈可能であることが利点です．


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{背景}

従来の単語埋め込みは 50 次元から 300 次元程度のベクトルで表現されます．この高次元性は様々な問題を引き起こします．

第一の問題はデータ容量です．例えば 40 万語彙 300 次元の埋め込みは約 1~GB のメモリを消費します．計算サーバー上で処理を行うのであればこれは許容範囲内ですが，スマートフォンやノートパソコンに展開する場合には問題となります．単語埋め込みを用いて文書を曖昧検索するスマートフォンのアプリを想像してみてください．1~GB の容量のアプリをダウンロードすると多くの通信容量を消費し，時間も多くかかります．また，アプリを起動すると 1~GB のメモリを消費します．検索のためだけにこれだけの容量を消費するのはユーザーは好ましく思わないでしょう．また，筆者が研究しているユーザーサイドの検索システム\cite{sato2022retrieving}では，ユーザーがデバイス上でクエリ拡張を行い検索システムを強化します．\cite{sato2022retrieving} におけるオフライン実験では単語埋め込みを用いてクエリ拡張を行っていましたが，デモを作る際にはこれでは問題なことに気が付きました．1~GB の埋め込みをダウンロードするのはユーザーにとっても負担ですし，ユーザーがウェブサービスにアクセスするたびに 1~GB のファイルを配信するのはサービス側のネットワークの負荷も甚大です．最終的に，デモプログラムでは単語埋め込みを用いない方法を採用することにしました \cite{sato2022clear}．このような事情により，単語埋め込みのスマートフォンアプリやユーザーサイドシステムへの活用が妨げられています．

第二の問題は解釈性です．300 次元の埋め込みは目で見ることができません．t-SNE などの手法を用いると可視化をすること自体は可能ですが，何が可視化されているかが判然としない場合が多くあります．高次元の埋め込みの中身を完全に把握することはできないので，こういう振る舞いをするだろうということを想像で補いながら埋め込みを使用することになります．しかし，高次元の埋め込みは低次元の埋め込みと異なる振る舞いをし，直感が裏切られる場合がしばしばあります \cite{sato2022reevaluating}．このときシステムは意図しない動作を引き起こすことになるため危険です．また，埋め込みに摂動を加える手法がありますが，埋め込みに摂動を加えた結果のベクトルが何を表しているかも明らかではありません．例えば，``cat'' という単語の埋め込み $\boldx_{cat} \in \mathbb{R}^d$ に対して小さな摂動 $\varepsilon \in \mathbb{R}^d$ を加えたベクトル $\boldx_{cat} + \varepsilon$ は cat に近いということは分かりますが，対応する単語はなく，具体的に何を表しているかは分かりません．これによりモデルや手法の解釈性が妨げられます．


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{提案手法}

以上の問題を解決するため，一次元の単語埋め込みを開発することを目指します．しかし，単語のあらゆる側面を保存するような一次元の単語埋め込みは存在しそうもありません．主成分分析を用いて単語埋め込みの次元を削減する研究 \cite{jurgovsky2016evaluating} では，次元を 30 次元にまで落とすと誤差が大幅に増大することが報告されています．非ユークリッド埋め込み\cite{nickel2017poincare}では 5 次元の埋め込みを得るのに成功していますが，うまく動作するのは階層構造をモデリングする特定のタスクのみであり，いずれにしても一次元まで圧縮することまではできません．

そこで，全ての側面を保存することは諦めて，多くのタスクで活用できるような特定の側面を保存する埋め込みを得ることを目指します．まず，単語埋め込みの側面を以下のように分解することを提案します．
\begin{description}
\item[健全性] 埋め込みが近い単語どうしの意味が近いような埋め込みを健全な埋め込みという．
\item[完全性] 意味が近い単語の埋め込みどうしが近くなるような埋め込みを完全な埋め込みという．
\end{description}
埋め込みを信じて近傍の単語を取ってきたとき，健全な埋め込みであれば正解だけが取ってこられます．ただし，取り残しの可能性は残ります．完全な埋め込みであれば，正解が全て取ってこられます．ただし，不正解の単語まで取ってきてしまうかもしれません．本研究では完全性は諦めて，健全な埋め込みを作ることを目指します．完全性はなくとも，健全性さえあれば単語検索や文書検索に用いることができます．

また，本研究では単なる健全な一次元埋め込みではなく，単語と $\{1, \ldots, n\}$ が一対一で対応する一次元埋め込み $\sigma \in S_n$ を得ることを目指します．ここで $n$ は語彙数であり，$S_n$ は $n$ 要素の順列全体からなる集合です．座標を実数値で表さずに順序で表わすことで，さらに解釈性が増し，計算機上で扱いやすく，かつ容量を削減することができます．これは，画像のピクセルが $\{0, 1, \ldots, 255\}$ の 256 値を取ることとの類推で考えると理解しやすいかもしれません．

健全な一次元埋め込み $\sigma \in S_n$ を得るにあたり，埋め込み $\sigma$ の中で隣同士に位置する単語の意味が近くなるように定式化します．ここで，単語の意味の遠近を測るにあたり，単語の意味を表わす高次元の単語埋め込み $\boldX = [\boldx_1, \cdots, \boldx_n]^\top \in \mathbb{R}^{n \times d}$ は既に手元にあると仮定します．高次元なものでよければ，完全かつ健全な埋め込みは Skipgram や GloVe といった既存手法を用いて得ることができます．これを用いて隣同士の位置する単語の意味の差を最小化する問題は以下のように定式化できます．
\begin{equation} \label{eq: opt}
    \underset{\sigma \in S_n}{\text{minimize}} \sum_{i = 1}^n \|\boldx_{\sigma(i)} - \boldx_{\sigma(i+1)}\|_2.
\end{equation}
$\boldX$ は事前に与えられた固定値であり，最適化変数は $\sigma$ であることに注意してください．コーパスが手元にある場合は $\|\boldx_{\sigma(i)} - \boldx_{\sigma(i+1)}\|_2$ の代わりに単語 $\sigma(i)$ と $\sigma(i+1)$ の共起数を基に意味の近さを定義しても問題ありません．

最適化問題 \eqref{eq: opt} は巡回セールスマン問題です．巡回セールスマン問題は NP-困難なので，一般には効率よく解くことができません．しかし，巡回セールスマン問題は有名な問題であり，非常に効率的なソルバーが整備されています．本研究では，近似は行わず，効率的なソルバーを用いて巡回セールスマン問題を直接解くアプローチを採用します．具体的には LKH\footnote{\url{http://webhotel4.ruc.dk/~keld/research/LKH/}}というソルバーを使用します．このソルバーは $n = 109399$ 都市の巡回セールスマン問題を厳密に解くことができます．提案アルゴリズムは式 \eqref{eq: opt} に従い巡回セールスマン問題の例を生成し，LKH ソルバに入力し，得られた順列を一次元埋め込み $\sigma \in S_n$ として出力します．この得られた一次元埋め込みのことを \textsc{WordTour} と命名しました．


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{実験}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%% table 1
\begin{table}[t]
\resizebox{\textwidth}{!}{%
\begin{tabular}{lc|ccccccccccc} \toprule
 & 手法 & \multicolumn{11}{c}{順列の区間} \\ \midrule
(a) & \textsc{WordTour} & sniff & sniffing & sniffer & dogs & dog & cat & cats & pets & pet & stray & errant \\
(b) & RandProj & loire & sayings & nn & trooper & referendum & cat & exceeded & traces & freestyle & mirrored & bloomberg \\
(c) & PCA1 & mm & asylum & kohl & presents & expressed & cat & sichuan & denmark & counted & corporations & hewitt \\
(d) & PCA4 & 1.46 & puzzles & 940 & coexist & locations & cat & att & winners & perth & colgate & sohail \\ \midrule
(e) & \textsc{WordTour} & assumption & assumptions & notions & notion & idea & concept & concepts & ideas & thoughts & feelings & emotions \\
(f) & RandProj & entertaining & 42,000 & kursk & embarrassment & ingrained & concept & berezovsky & cg & guillen & excerpts & roofs \\
(g) & PCA1 & neighboring & branches & argued & manhattan & 1998 & concept & share & pending & response & airlines & fort \\
(h) & PCA4 & 2:00 & hksar & hashim & provider & straining & concept & inducing & fightback & unsettled & bavaria & sign \\ \midrule
(i) & \textsc{WordTour} & wireless & broadband & 3g & cdma & gsm & handset & handsets & smartphones & smartphone & blackberry & tablet \\
(j) & \textsc{WordTour} & gun & weapon & weapons & arms & arm & leg & legs & limbs & limb & prosthetic & make-up \\
(k) & \textsc{WordTour} & federalist & libertarian & progressive & liberal & conservative & conservatives & liberals & democrats & republicans & gop & republican \\
(l) & \textsc{WordTour} & cordial & amicable & agreeable & mutually & beneficial & detrimental & harmful & destructive & disruptive & behaviour & behavior \\
(m) & \textsc{WordTour} & 15th & 14th & 13th & 12th & 10th & 11th & 9th & 8th & 7th & 6th & 5th \\
(n) & \textsc{WordTour} & suspicions & doubts & doubt & doubted & doubting & doubters & skeptics & skeptic & believer & believers & adherents \\
(o) & \textsc{WordTour} & molten & magma & lava & basalt & sandstone & limestone & granite & marble & slab & slabs & prefabricated \\\bottomrule
\end{tabular}
}
\hangcaption{一次元単語埋め込みの例．各行は順列の区間を切り取ったものである．(a--d) ``cat'' の周りの区間．(e--h) ``concept'' の周りの区間．(i--o) \textsc{WordTour} からランダムに切り取った区間．\textsc{WordTour} は自然な並びになっている．}
\label{tab: example}
\end{table}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

まず，GloVe の 4 万語彙 300 次元埋め込みを用いて \textsc{WordTour} を計算しました．得られた埋め込みの経路長は $236882.314$ であり，双対問題を解いて得られた最適値の下限は $236300.947$ でした．LKH がほぼ最適な埋め込みを計算できていることが分かります．得られた埋め込みは \url{https://github.com/joisino/wordtour} にて公開しています．埋め込みファイルは $312$ KB と非常に軽量です．この容量であれば，モバイル端末やユーザーサイドシステムにも問題なく組み込むことができます．また，一次元埋め込みは単語を順番に記録したリストとして保存されています．数値の羅列で表現される従来の埋め込みと比べて，格段に解釈がしやすいのが利点です．

表 \ref{tab: example} に得られた一次元単語埋め込みから一部を切り取ったものを掲載します．RandProj はランダムな方向 $\boldd \in \mathbb{R}^d$ に対して高次元埋め込み $\boldX$ を射影したもの，PCA1, PCA4 はそれぞれ高次元埋め込み $\boldX$ の第一主成分と第四主成分です．この表から，RandProj, PCA1, PCA4 はでたらめな順序になるのに対し，提案法 \textsc{WordTour} は似た単語が近くにくる健全な埋め込みとなっていることが見てとれます．例えば，行 (m) では序数詞がほぼ順序通りに取り出せています．提案手法は教師なし手法であり，目的関数にもこのような構造を保つことは明示的に入れていないにもかかわらず，このような構造が取り出せていることは驚きです．行 (j) では weapons, arms, arm, leg と並んでおり arm の意味が武器から腕に急激に変化しています．このように，多義語においては提案法は健全性を保つの失敗する場合があります．一方で，高次元埋め込みにおいて多義語がこのように並んでいるということが判明した点は提案手法の解釈性の利点だと考えています．多義語においてうまく健全性をモデリングする方法については今後の課題とします．

文書分類を用いた定量的な方法によっても提案法を評価しました．提案法を文書分類に用いる際には，まず文書中の各単語 $w$ について，\textsc{WordTour} 上で $w$ の近傍にある単語を用いてクエリ拡張を行い，拡張した bag of words ベクトルを得ます．このベクトルを L1 正規化したものどうしの L1 距離で文書の距離を定義します．分類はk-近傍法により行いました．提案法によるクエリ拡張は bag of words の精度を一貫して向上させることができました．また，高次元単語埋め込みを使った代表的な文書分類手法である Word Mover's Distance \cite{kusner2015from} と比較すると，精度は僅かに劣りましたが，速度の面では提案法の方が数千倍高速でした．


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{おわりに}

本研究では一次元の単語埋め込みを提案しました．一次元の埋め込みというと実現できなさそうに思えますが，切り口次第では有用なものが得られることを示せたのは非自明な貢献になったと考えています．また，NP-困難な巡回セールスマン問題を用いた定式化は自然言語処理や機械学習では珍しいアプローチかと思います．この方面を開拓できたことも一つの貢献だと考えています．本研究をうけて，Kaggle のコンペティションでもこのテクニックが使用されました\footnote{\url{https://www.kaggle.com/competitions/foursquare-location-matching/discussion/335800}}．そこでは，カテゴリ埋め込みに対して巡回セールスマン問題を適用し，カテゴリを一列に並べて一次元変数にして決定木に入力しています．このように，似た項目が隣接するように項目を一列に並べるという考え方は広い汎用性を持っています．他にも様々な活用方法があると思うので，ぜひ皆さんも考えてみてください．


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\bibliographystyle{jnlpbbl_1.6}
\bibliography{25refs}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{biography}
\bioauthor{佐藤　竜馬}{%
2021年3月京都大学情報学研究科修士課程卒業．2021年4月京都大学情報学研究科博士課程入学．専門分野はグラフニューラルネットワーク，最適輸送，および情報検索・推薦システム．
}

\end{biography}



\end{document}


