クロスワードパズルとは、おなじみの上のようなものですね。
これをコンピュータに自動で解かせることができるでしょうか？？
え？「そんなことをして何になる？」って？？
「クロスワードなんか、その解く過程が楽しいんやから、コンピュータに解かせても面白くないやん！」
「大学の研究でそんな遊びみたいなことしてていいの？」
そんな声が聞こえてきそうですが…
はい、もちろんこれはちゃんとした研究なんです。
僕たち人間がクロスワードを解くとき、まずカギから答えを推測して、 次にグリッド（クロスワードのマス目のこと）にうまく入るように
答えを選んで埋めていくよね。
これを図に描くと上の図のようになるんだけど、実はこれはそれぞれテキストからの推測っていう自然言語処理と探索っていう人工知能の問題のひとつなんです。
だからこの研究はクロスワードっていうなじみ深いパズルを題材にして、自然言語処理や人工知能の研究を進めていこう！って主旨なんです。なお、ここは言語の研究室ですから、この自然言語処理の部分に特に注目していきます。
ちなみにこういったパズルやゲームを題材にして研究するってのはよくあることなんだけど…やっぱ研究は楽しくやらなくちゃ！ってことだね！
上の例を見てみよう。僕らが答えを推測するとき、まずカギが何を言ってるか考えて、それから、その表す言葉を考えるよね。だからコンピュータにも、この二つのことをやってもらおう！
ちなみに、上の図に書いてる「言語構造」と「連想関係」っていうのはこの二つを表しています。
この二つを直感的にいうと、
「言語構造」っていうのは、たとえば、
「私は走る」という文を「ワタシハハシル」ではなくて「私」は「走る」という風にちゃんと分かること。
人間は当たり前のようにできるけど、コンピュータにやらせると…？？
「連想構造」っていうのは、まさしく、
「まだ結婚していない」の言語構造が分かったときに「未婚」や「乙女」といった言葉を出すこと。
人間でも難しい場合があるけど、コンピュータにはどうやらせる…？？
ちょっともったいぶって書いたけど、実は「言語構造」についてはかなり研究がされていて、JUMAN・KNPといったそこそこ使えるソフトがすでにあるんです。だから今回はそれを使うことにします。（JUMANやKNPについての説明はここでは省略します。興味のある人はJUMAN・KNP）
もうひとつの「連想構造」についてはほとんど分かってないので、今回はここを重点的に考えていきます。
んじゃ、もう少し具体的にどういうことをやるのか考えてみよう。
クロスワードの場合、「連想構造」のヒントはカギの中に含まれています。たとえば上の例のように、「…のこと」とあれば「同義語」、「…の反対」とあれば「反義語」と分かります。これが分かれば、あとは辞書から見つけるだけ（詳しい辞書には「無料」で引くと「同義語：タダ、ロハ」などと載っている）ですから、検索でできそうですよね！実際のコンピュータでの実行例を下に挙げます。色が変わっているものが正解となる語です。このように正解の候補となる語を列挙することができます。なお、ここで挙げた例はすべて正解となる語を含んでいますが、常に正解の語を含むとは限りません。
今回の研究では、実際のクロスワードから「連想構造」のヒントを１９種類に分類して考えました。そしてまずは、そのうちで比較的プログラム可能なもの１２種類を選んで実際にプログラムし、クロスワードを解いてみました。
上で述べたような言語構造と連想構造を用いて、また、うまくグリッドに入るように答えを選ぶこと（グリッドフィリングと言います）についてはProvarb（過去に研究・製作された英語版クロスワードを解くプログラム）で使われたものを用いて解きました。
結果は４４％（クロスワードに１００個のカギがあったら、そのうち４４個のカギは正解の語がグリッドに埋まっている）でした。
この結果は意外だったでしょうか？
「そんなに解けるんだ！？」「それだけしか解けないんだ！？」意見はいろいろだと思います。
問題としては、
・プログラムしたのは１９種類の分類のうち１２種類のみ
・難しいカギが存在する
・「常識」は辞書にはない
１つ目に対しては、もう少し時間をかけて種類を増やしていくこと、システムの質をお高めることで対応可能です。また、これと辞書を増やすことで、１０％程度の向上ができる概算です。
２つ目というのは、たとえば
・「近所の家事でおじさんが使うもの」
です。答えは「消火器」なのですが、人間が解いても難しいと思います。こういったものをコンピュータに解かせるにはどうしたらいいのか、よく分かりません。
３つ目というのは、たとえば、
・「洋食はフォーク。和食は？」
です。答えが「箸」なのは人間にはすぐ分かりますが、こういった「常識」的なものは辞書に載っているわけではありません。これもコンピュータに解かせるにはどうしたらいいのかよく分かりません。
今後こういった問題点が解決されれば、１００％に近い性能でクロスワードが解けるでしょう。
また、もしかしたら人間の推論能力も明らかになるかもしれません。
スタートはクロスワードを解くというゲームみたいなところからですが、ゴールはもしかしたら人間の知能の根本に触れる深いところかもしれません。
参考文献