Common Lispが機械学習に向いていると考えるこれだけの理由

LISP 機械学習

Lisp Advent Calendar 2016参加記事

ここ数年ディープラーニングの出現をきっかけにAIが再び盛り上がっているので、いよいよLispの復権があるかと思いきや、ないので（泣）、多少なりともLispに興味を持ってもらえるように、LispとAIの関係について私見を述べておこうと思う。Lispといっても色々あるが、この記事では主にCommon Lispの話になる。

Lispというとどうしても過去の記号処理的AIと結びつけられてしまい、機械学習を駆使するような現代のAIでは役に立たないように思われがちなのだが、これは大体誤解である。少なくともCommon Lispは現代的なAI開発に適した特徴を備えている。まず、AI実装のためのプログラミング言語に必要とされる特徴は何なのかを明らかにするために、AIの歴史から考えてみたい。

AIの歴史

初期の記号処理的AI(以降は記号AIと呼ぶ)ではLispやPrologが実装言語として広く採用されてきた歴史がある。記号処理とはその名の通り記号を操作対象とする処理のことで、具体的には、エキスパートシステム、数式処理、プログラミング言語のコンパイラなど、論理的な推論や構造の変換を伴うものが多い。それらの記号ベースのデータ構造はリストで表現されることが多かったので、リストの取り扱いを得意とするLispが採用されてきたわけだ。*1 記号AIは一定の成功をおさめたが、現実世界の複雑な問題に適用しようとするとフレーム問題や記号接地問題の壁にぶち当たった。結局、古典的な記号AIでは事物の特徴をどのように取り出し、抽象化し、関連付ければいいのか、それをどこまでやったらいいのかといったことを解決できなかったのだ。
現実世界でも適用可能な妥当なルールベースを作りこむことが難しいことが分かってきたので、その後は大量のデータからボトムアップ的に学習して自動的に知識表現を獲得してやろうという流れになり、ニューラルネットなどの機械学習手法が発達した。最近のディープラーニングなどはその延長線上にある。

機械学習は数値計算

ほとんどの機械学習のアルゴリズムは何らかの目的関数を最適化することによって学習を実現している。例えばニューラルネットの学習であれば、モデルからの予測値と実測値の誤差を目的関数として、その勾配(微分)を取り、誤差を最小化させる方向にモデルパラメータを少し動かすことを繰り返す。このことからも分かるように、記号AIのプログラミングはリスト処理が中心だったのに対して、機械学習AIのプログラミングは数値計算が中心となる。従って、複雑な数値計算をいかに簡潔に記述でき、いかに効率的に計算できるかがキモになる。

より高水準に。より低水準に。

コンピュータの性能向上にともない、最終的な実行速度よりも開発効率を重視するというトレンドが生まれた。研究者は短時間でアルゴリズムを実装して実験する必要があり、自然とAI分野ではRやMATLAB、Pythonなどの動的で高水準な言語に人気が集まった。これらは基本的には逐次実行のスクリプト言語であり、実行速度は遅い。
これに対する戦略として、これらの言語では外部の数値計算ライブラリを呼び出す何らかの方法を持っている。具体的には、計算処理をある程度まとまった単位にまとめて、Cなどの低水準言語で書かれた数値計算ライブラリにまるごと送り出す。例えば、ループでやるような処理をベクトルに対するマップ操作として記述するとか、ベクトルの計算ならば、小単位のバッチ処理にまとめて行列の演算に置き換えてから外部ライブラリに渡すなどのテクニックを用いることになる。
しかしいつでもこれができるとは限らない。例えばリアルタイムのオンライン処理には向かないし、そもそも逐次処理を必要とする学習アルゴリズムでは使えない。そういう場合は結局Cなどで書いてコンパイルしたものを呼び出す必要がある。*2 こうなってくると、実行速度を出すためにアルゴリズムの選択やプログラミングスタイルに制約がかかることになり、本末転倒ということになりかねない。

実はCommon Lispは数値計算に向いている

もともとLispの特徴として、柔軟で強力な抽象化機構を持ち、時としてプログラマ自身が構文すら自由に拡張できる高水準言語だということがあった。それに加えてCommon LispにはSBCLなどのオープンソースの高品質なネイティブコンパイラがあり、Cで書かれたライブラリに簡単にアクセスできる仕組みCFFIがある。さらに最近ではインターネットからライブラリをダウンロード、インストール、ロードまでを一貫してこなすライブラリ管理システムQuicklispや、処理系のバージョンを管理したりデプロイを行なえるツールRoswellなども出てきて、いよいよ便利になりつつある。

一部ではLispはスクリプト言語で遅くて数値計算には向かないというイメージがあるようだが、SBCLなどはJIT（AOTでした）コンパイラであるし、現在ではコンパイル型言語の中でもむしろ速い部類に入る。この話題の概要としては、Gauche作者のshiroさんのエントリがとても分かりやすかった。

速いコードを書くための具体的な方法論として参考になる情報源をいくつか挙げておくと、

Common Lispが速いのは、動的言語にも関わらず、最適化宣言と型宣言をオプションとして付けることができるためだ。動的言語が遅いと言われるのは、主にオブジェクトの型情報を実行時に判定する必要があるためで、極端な話、全ての変数に型宣言を付けて、最適化宣言で実行時の型チェックを切れば、Common LispコンパイラはCとほぼ同等のネイティブコードを吐き出す。さらに、これらの宣言はあらゆるレベルで付けることができるので、関数単位、ブロック単位で、本当に必要な部分にのみ集中して最適化することができる。

そして、往々にしてそのようなボトルネックはプログラム全体のごく一部にすぎない。大抵のCommon Lisp処理系には、プロファイラという、プログラムのどこの部分に計算時間が割かれているかを調べるツールが付いており、ボトルネックを探すのに役に立つ。また、コンパイルした関数を個別にディスアセンブルすることもできる。アセンブリコードを見ることによって、実行時の型変換がどこで起こっているかや、メモリアロケーションがどこで発生しているかなどが分かるので、これもチューニングの手掛かりになる。*3

以上をまとめると、Common Lispの開発サイクルは以下のようになる。

  1. 動的で高水準な言語機能を使って迅速にプロトタイピングする
  2. プロファイリングでボトルネックを探す
  3. 最適化宣言、型宣言を付けてコンパイル
  4. ディスアセンブルしてネイティブコードを見ながら最適化

これら全てが開発環境の中から出ることなく、対話的に行うことができる。これにより開発サイクルが短く、試行錯誤できる回数が多くなり、結果として最適なアルゴリズムを見つけ出すチャンスが増える。往々にして「Common LispでCよりも速いコードが書ける」というのは、最高速度のことというよりは、この開発サイクル自体の効率性が高いことを示している。

必要なら外部の数値計算ライブラリにもアクセスできる

Common Lispはそれ自体で速いとはいえ、巨大な行列同士の掛け算のように、マルチコアCPUやGPUの性能を極限まで引き出したいときには外部ライブラリに頼ることになる。CFFI経由で比較的簡単にCの共有ライブラリから関数を呼ぶことができるが、主な数値計算ライブラリにはラッパーライブラリが存在する。Intel MKLやOpenBLASのラッパーライブラリとしてはLLAがあり、CUDAによる行列計算のラッパーライブラリとしてはMGL-MATがある。

数値計算ライブラリに投げた後の処理はPythonのNumpyなどと同じなのでここでの速度差はあまりないが、FFIの部分でCommon Lispの方が若干速くなる。

素のCommon Lispの速さがあれば、機械学習で最も計算能力を必要とする学習時には外部の数値計算ライブラリを使い、予測時にはピュアCommon Lispのみを使うという選択肢も取れるようになる。そうすることでアプリケーションとして配布するときの外部の依存ライブラリを減らし移植性を増すことができる。

Common Lispの機械学習ライブラリ

Common Lispの機械学習ライブラリは数はあまり無いものの、重要なところは抑えているような気がする。とはいえまだまだ少ないので新規参入者求む！

まとめ

  • 機械学習AIに求められているのは迅速に開発できて、なおかつ実行速度も速いこと
  • Common Lispは基本的には高水準言語だが、ボトルネックになっているところを集中的に最適化することもできるので、低水準言語という側面も持つ
    • アルゴリズム選択の自由度が高く、ほとんどの処理をCommon Lisp内で完結できるので、実行速度と開発効率のバランスを取りやすい
    • 本当に重い処理は外部ライブラリに投げることもできる
  • 機械学習ライブラリも一応揃ってる
  • 新規参入しよう！

*1:Lispの由来はリスト処理(LISt Processing)から来ているという話がある

*2:一応、PythonであればCythonなどのネイティブコードにコンパイルする仕組みもある。

*3:例えば、新たにオブジェクトを生成して返すようなコードは、結果受取り用の変数を引数として与えてそれに代入させればメモリアロケーションは発生せず、ガベージコレクションの時間を削減できる。