yasuokaの日記： Universal DependenciesにおけるNP困難と計算不能

ネットサーフィンしていたところ、John Ballの『Universal Dependencies are Fundamentally Flawed』(Medium, 2022年4月28日)というワケのわからない記事に出くわした。以下の文を読む限り、「NP-Hard」(NP困難)と「unsolvable」(計算不能)をゴチャ混ぜに議論してしまっているようだ。

Stanford University and Google continue to pursue the 1950s model of language using parts-of-speech in their Universal Dependencies (UD) project. This is the model shown to be NP-Hard (“unsolvable”) in the late 1980s but continues anyway— with humans manually annotating documents using their design.

品詞付与や係り受け解析の問題は、一般にNP困難だが、計算不能ではない。NPすなわちNondeterministic Polynomialの名の通り、非決定性チューリングマシンを使えば、多項式時間で解ける。実際、Joakim Nivreの『An Efficient Algorithm for Projective Dependency Parsing』は、確率オートマトン上の線形時間アルゴリズムであり、係り受けのリンクに交差が無い場合には、非常に有効なアルゴリズムだ。これがうまくいったので、Universal Dependenciesというプロジェクトを、Nivre自身、始める気になったのだろう。

あるいは、Timothy Dozatはスタンフォード大学にいた頃、『Deep Biaffine Attention for Neural Dependency Parsing』を発表している。このアルゴリズムは、交差を含む係り受けをO(n²)で解くスグレモノで、端的には、隣接確率行列上でChu-Liu-Edmondsへ落とすことができる。スタンフォード大学のStanzaも、私(安岡孝一)のesuparも、お世話になっているアルゴリズムだったりする。

確かにUniversal Dependenciesは、実際のところ「万能」ではないのだが、それは「NP困難」であることとは何の関係も無い。というか、この記事にはJoakim NivreもTimothy Dozatも出てこないのだけど、このJohn Ballとかいう人物、一度でも係り受け解析プログラムを書いたことあるのかしら？