Shibuya.lisp 2018年振り返り

Lisp Advent Calendar 2018参加記事

去る2018年12月10日に港区芝はポケットチェンジにてShibuya.lisp運営で集まって今年の振り返りと来年の活動方針について相談したのでまとめます。

今年やったこと、達成できたこと

がんばらない

これは昨年1月に「Shibuya.lispの今後を考える会」で前運営からの引き継ぎにあたって基本方針として出てきたものなんですが、月例のLispmeetupはあくまで場を提供し続けることが重要であって、運営の負担は極力少なくして、とにかく続けられるようにしようというものがありました。

その辺の方針については以下の記事に詳しく触れられています。

ここにも書かれていますが、会場を安定的に確保できたことは定期開催する上で非常に助かりました。最近ではほとんど五反田にあるサイボウズスタートアップスさんに会場を提供して頂いています。会場でそのまま懇親会を開くことができ、しかも軽食（ピザor寿司！）も出るという素晴しい会場です（感謝！）。ここはClojureの会社なので、懇親会中にClojureエンジニア募集のための会社紹介が入ります。

そんなこんなでLispmeetupも70回を越え、Shibuya.lisp自体も今年で10周年に当たるそうです。今後もゆるい感じで続けていければと思います。

ポジションペーパーをやり始めた

Lispmeetupでは毎回最初に簡単な自己紹介の時間を取っています。しかし口頭での自己紹介だけだと顔とID（アイコン）がなかなか一致しないという声があり、自己紹介スライド（ポジションペーパー）を一人一枚書いてもらい、それを映しながら話してもらうという試みを始めました。

ここでネタを仕込んでもらうと発表の前に場が暖まってやりやすくなるなどと一部で好評です。これは続けていこうという話になりました。

Lispもくもく会をやり始めた

週末の午後などに多めに時間を取ってLisp関係の作業をするもくもく回を開催しています。既に5回ほど開催しており、今後は隔月開催で第二土曜に固定しようという話が出ています。まだまだ参加者が少ないので周知が足りない気がする。

リモート参加も可ですが、こちらはまだまだやり方など試行錯誤している状態のようです。もくもく会でもポジションペーパーを書いてもらってはどうか、など。

Youtubeチャンネルを作った

毎月のLispmeetupの模様は発表者の同意が得られれば録画しています。

今までUstreamで配信していたのですが、このほどYoutubeに移行しました。生配信よりは録画に残すことに重点を置いています。音声がちゃんと録れていなかったりと試行錯誤しながらも徐々にちゃんと録画できるようになってきました。

www.youtube.com

チャンネル登録お願いします！

来年やっていくこと

ひきつづき、がんばらない

がんばらないを、がんばる。

開催日の固定と告知

開催日は毎月最終週木曜で固定した方が告知を早めに出しやすいし、発表者が予定を立てやすい。ネタを持っていそうな人にはTwitterで声かけしていく （Shibuya.lispアカウントに限らず）。

実際よく発表している人はTwitterなどでせっつかれている印象です。また発表者が固定してきた感があるので、新たな人を呼び込む策を講じる必要があるという話になりました。

そのためには、軽くて短い発表をするLT枠を作るなどして、気軽に発表できる雰囲気を作っていかないといけないのでは？とか、会場を変えてみることで参加者層が変わるのでは？などといった意見が出ました。

このうちのいくつかは実行に移していきたいと思っています。

お知らせ

Slackを作りました

これまでも運営用の連絡チャットはありましたが、プログラミング言語コミュニティではSlackなどを用意しているところも多く、Shibuya.lispでもSlackを公開することにしました。Lispに興味のある方であれば以下のリンクからどなたでも参加できます。

Shibuya.lisp Slack参加登録

はてなダイアリーからGithub pagesに引越します

引越し先

引越しの理由: Chromeで激遅問題

  • Chromeでの表示が遅すぎる。ひどいときには20秒くらいかかる
  • ChromeのDeveloper toolsで読み込み時間を測定してみると、HatenaStar.jsで異常に時間がかかっている
    • はてなスターを非表示にしても代わりにTen.jsが読み込まれ同じ箇所で止まる

  • 該当部分のソースを見ると、webkitでアクセスしたときに、DOMの読み込みが完了しているかどうかの判定が、doScrollを使う古いIE向けの方法でやられている
    • ところがChromeにはこのdoScrollメソッドが無いので、この判定は常に失敗し、タイムアウトするまで延々待ち続けている

移行先の選定

  • そもそもブログは静的なコンテンツのはずなので、Javascript満載のゴテゴテ状態だとすれば何かが間違っていると考えるべき
  • というわけで静的サイトジェネレータで生成することにした
    • 生成したサイトのホスティングにはGithub pagesが使える
      • しかも無料で使える。スゴイ。はてなよりGithubにお金を払いたいと思わせる
    • 静的サイトジェネレータも色々あるのだが、Github pagesで公式サポートされているというjekyll-bootstrapを使う
      • 最近だとHugoというより生成が高速なGo製のツールもあるらしい
      • 記事はmarkdownで書く。org-modeで書きたい

まとめ

  • 読み込みが長いと途中でタブを閉じてしまうユーザは多い。そういうユーザにとっては、そのページは無いのと同じなのだ
  • 今もはてなダイアリーを使っている人は結構多いと思うのだが、Chromeというメジャーなブラウザのユーザをごっそり取りこぼしているかもしれないということには注意が必要だ
    • 確認してないが、Safariなどの他のWebkitブラウザでも同じことが起こっている可能性が高い
  • Github pagesに引っ越してChromeでの読み込み時間は0.5秒になった。実に約40倍の高速化である
  • さようならはてなダイアリー、ありがとうはてなダイアリー

CLMLのランダムフォレストを試してみる

Lisp 機械学習

ランダムフォレストは決定木ベースの分類/回帰モデルで、ニューラルネットやSVMなどと同様に非線形モデルなので線形分離不可能な問題にも使える。SVMはデータ数に対して指数的に計算時間がかかる一方、ランダムフォレストはデータ数をnとしてn*log(n)のオーダであり、軽い。また、SVMは基本的に二値分類器なので複数の学習器を組み合わせてマルチクラス分類することが多いが、ランダムフォレストは元からマルチクラスに対応していて追加のコストがかからない。さらに並列化も簡単にできるなど、扱いやすい性質をたくさん備えているので現実世界でよく使われている。

参考にしたランダムフォレストについての記事いろいろ

CLMLにランダムフォレストの実装があったので試してみる。

CLMLはCommon Lisp用の機械学習パッケージ集であり、Quicklispからインストールできる。ただし、あらかじめ処理系のdynamic-space-sizeを2560以上にして起動しておく必要があることに注意する。

先に必要ライブラリを読み込んでおく。

(ql:quickload :clml)
(ql:quickload :cl-online-learning)
(ql:quickload :alexandria)

データの読み込み

まずはデータの読み込みの例。サンプルデータをネットからダウンロードしてきて読み込む。

(defparameter *syobu*
  (clml.hjs.read-data:read-data-from-file 
   (clml.utility.data:fetch "https://mmaul.github.io/clml.data/sample/syobu.csv")
   :type :csv :csv-type-spec '(string integer integer integer integer)))

;; CL-USER> *syobu*
;; #<CLML.HJS.READ-DATA:UNSPECIALIZED-DATASET >
;; DIMENSIONS: 種類 | がく長 | がく幅 | 花びら長 | 花びら幅
;; TYPES:      UNKNOWN | UNKNOWN | UNKNOWN | UNKNOWN | UNKNOWN
;; NUMBER OF DIMENSIONS: 5
;; DATA POINTS: 150 POINTS

;; CL-USER> (aref (clml.hjs.read-data:dataset-points *syobu*) 0)
;; #("Setosa" 51 35 14 2)

ここから分かるように、データセットは特徴量の各次元の名前のリストと、データ点を表すベクタのベクタを持っている。例えば以下のようにして新たにデータセットを作れる。

(defparameter dataset1
  (clml.hjs.read-data:make-unspecialized-dataset
   '("class" "feat1" "feat2")
   (vector (vector "posi" 1 2)
           (vector "nega" -1 -2)
           (vector "posi" 10 20))))

データ点のベクタにラベルの文字列と数値が混在しているのが遅そう。

LIBSVMデータセットのデータを読み込む

今読んでるランダムフォレストのオンライン版の論文に出てくるものと同じデータセットで比較したいので、LIBSVMのデータセット集からmushroomsデータを読み込む。

cl-online-learningのread-data関数で読み込んでCLMLの形式に変換する。予測したい特徴の名前が後で必要になってくるので、クラスラベルに"class"と名前を付けて、残りの特徴名には単に連番を振っておく。

(defparameter *mushrooms-dim* 112)
(defparameter *mushrooms-train* (clol.utils:read-data "/home/wiz/datasets/mushrooms-train" *mushrooms-dim*))
(defparameter *mushrooms-test* (clol.utils:read-data "/home/wiz/datasets/mushrooms-test" *mushrooms-dim*))

(defun clol.datum->clml.datum (datum)
  (let ((label (if (> (car datum) 0) "posi" "nega")))
    (coerce (cons label (coerce (cdr datum) 'list)) 'vector)))

(defun clol.dataset->clml.dataset (dataset)
  (let ((datum-dim (length (cdar dataset))))
    (clml.hjs.read-data:make-unspecialized-dataset
     (cons "class" (mapcar #'(lambda (x) (format nil "~A" x)) (alexandria:iota datum-dim)))
     (map 'vector #'clol.datum->clml.datum dataset))))

(defparameter *mushrooms-train.clml* (clol.dataset->clml.dataset *mushrooms-train*))
(defparameter *mushrooms-test.clml* (clol.dataset->clml.dataset *mushrooms-test*))

ランダムフォレストの学習

lparallelを使って並列化しているので、まずカーネルサイズの設定をしておく。

(setf lparallel:*kernel* (lparallel:make-kernel 4))

上で作った *mushrooms-train.clml* データセットから学習する。予測対象のクラスラベルの特徴名をここで指定する。

(defparameter *forest* (clml.decision-tree.random-forest:make-random-forest *mushrooms-train.clml* "class"))
;; Evaluation took:
;;   81.367 seconds of real time
;;   269.523032 seconds of total run time (265.196590 user, 4.326442 system)
;;   [ Run times consist of 9.140 seconds GC time, and 260.384 seconds non-GC time. ]
;;   331.24% CPU
;;   276,010,481,282 processor cycles
;;   120,282,960,608 bytes consed

4コアCPUで計算しているが、かなり時間がかかってしまっている。

予測は、予測したいデータ点のラベル部分を "?" に置き換えたものを学習済みのモデルとともにpredict-forest関数に与える。例えば、テストセットの最初のデータ点を予測するには、

(aref (clml.hjs.read-data:dataset-points *mushrooms-test.clml*) 0)
;; #("nega" 0.0d0 0.0d0 0.0d0 0.0d0 0.0d0 1.0d0 1.0d0 0.0d0 0.0d0 0.0d0 0.0d0
;;   0.0d0 1.0d0 0.0d0 0.0d0 0.0d0 0.0d0 0.0d0 0.0d0 0.0d0 0.0d0 1.0d0 0.0d0 0.0d0
;;   1.0d0 0.0d0 0.0d0 0.0d0 0.0d0 0.0d0 0.0d0 0.0d0 1.0d0 1.0d0 0.0d0 0.0d0 1.0d0
;;   1.0d0 0.0d0 0.0d0 0.0d0 0.0d0 0.0d0 0.0d0 0.0d0 0.0d0 0.0d0 0.0d0 0.0d0 0.0d0
;;   1.0d0 0.0d0 0.0d0 1.0d0 0.0d0 0.0d0 1.0d0 0.0d0 0.0d0 0.0d0 0.0d0 0.0d0 0.0d0
;;   0.0d0 0.0d0 1.0d0 0.0d0 0.0d0 0.0d0 0.0d0 0.0d0 0.0d0 0.0d0 0.0d0 1.0d0 0.0d0
;;   0.0d0 1.0d0 0.0d0 0.0d0 1.0d0 0.0d0 0.0d0 1.0d0 0.0d0 0.0d0 0.0d0 1.0d0 0.0d0
;;   0.0d0 0.0d0 0.0d0 0.0d0 0.0d0 0.0d0 0.0d0 0.0d0 1.0d0 0.0d0 0.0d0 0.0d0 0.0d0
;;   0.0d0 1.0d0 0.0d0 0.0d0 0.0d0 0.0d0 0.0d0 1.0d0 0.0d0 0.0d0)

(defparameter *query*
  #("?" 0.0d0 0.0d0 0.0d0 0.0d0 0.0d0 1.0d0 1.0d0 0.0d0 0.0d0 0.0d0 0.0d0
    0.0d0 1.0d0 0.0d0 0.0d0 0.0d0 0.0d0 0.0d0 0.0d0 0.0d0 0.0d0 1.0d0 0.0d0 0.0d0
    1.0d0 0.0d0 0.0d0 0.0d0 0.0d0 0.0d0 0.0d0 0.0d0 1.0d0 1.0d0 0.0d0 0.0d0 1.0d0
    1.0d0 0.0d0 0.0d0 0.0d0 0.0d0 0.0d0 0.0d0 0.0d0 0.0d0 0.0d0 0.0d0 0.0d0 0.0d0
    1.0d0 0.0d0 0.0d0 1.0d0 0.0d0 0.0d0 1.0d0 0.0d0 0.0d0 0.0d0 0.0d0 0.0d0 0.0d0
    0.0d0 0.0d0 1.0d0 0.0d0 0.0d0 0.0d0 0.0d0 0.0d0 0.0d0 0.0d0 0.0d0 1.0d0 0.0d0
    0.0d0 1.0d0 0.0d0 0.0d0 1.0d0 0.0d0 0.0d0 1.0d0 0.0d0 0.0d0 0.0d0 1.0d0 0.0d0
    0.0d0 0.0d0 0.0d0 0.0d0 0.0d0 0.0d0 0.0d0 0.0d0 1.0d0 0.0d0 0.0d0 0.0d0 0.0d0
    0.0d0 1.0d0 0.0d0 0.0d0 0.0d0 0.0d0 0.0d0 1.0d0 0.0d0 0.0d0))

(clml.decision-tree.random-forest:predict-forest *query* *mushrooms-train.clml* *forest*)
; => "nega"

テストセットをまとめて予測するには、forest-validation関数を使う。

(clml.decision-tree.random-forest:forest-validation *mushrooms-test.clml* "class" *forest*)

;; Evaluation took:
;;   12.064 seconds of real time
;;   12.075773 seconds of total run time (12.044405 user, 0.031368 system)
;;   [ Run times consist of 0.337 seconds GC time, and 11.739 seconds non-GC time. ]
;;   100.10% CPU
;;   40,922,800,082 processor cycles
;;   10,874,892,336 bytes consed

;; ((("nega" . "posi") . 100) (("posi" . "posi") . 428) (("nega" . "nega") . 1596))
;; => Error rate: 0.04708098

この返り値は、例えば"nega"のものを"posi"と判定したケースが100件あったということを意味する。残りは正解しているので正答率は95.3%程度となる。論文では99%くらい出るとあるのでちょっと低い。なんで。Hivemailでも99%くらい出る模様。

メタパラメータの指定

メタパラメータとして指定できるものは、

  • 決定木の数 (デフォルトは500)
  • 元のデータセットから重複を許してサンプリングしたものをデータセットとして各決定木を学習するのだが、その際のサンプルサイズ (デフォルトは元のデータセット全体のサイズ)
  • 元の特徴量からサンプリングしたものを各決定木の特徴量として使うのだが、その際のサンプリングする特徴の数 (デフォルトはフルの特徴量を使うが、よく使われるのは元の特徴量のサイズの平方根)

これらを調整してより小さなランダムフォレストを作ると、

(defparameter *small-forest*
  (clml.decision-tree.random-forest:make-random-forest
   *mushrooms-train.clml* "class"
   :tree-number 100
   :data-bag-size (floor (/ (length *mushrooms-train*) 10))
   :feature-bag-size (floor (sqrt *mushrooms-dim*))))

;; Evaluation took:
;;   1.217 seconds of real time
;;   4.279771 seconds of total run time (4.191569 user, 0.088202 system)
;;   [ Run times consist of 0.141 seconds GC time, and 4.139 seconds non-GC time. ]
;;   351.68% CPU
;;   4,125,539,396 processor cycles
;;   2,282,142,096 bytes consed

;; => Error rate: 0.041902073

となってかなり高速になり、精度も若干上がった。

番外編: cl-online-learningでもやってみる

(defparameter arow-learner (clol:make-arow *mushrooms-dim* 0.1d0))
(loop repeat 10 do
  (clol:train arow-learner *mushrooms-train*)
  (clol:test arow-learner *mushrooms-test*))

;; Accuracy: 91.99623%, Correct: 1954, Total: 2124
;; Accuracy: 94.3032%, Correct: 2003, Total: 2124
;; Accuracy: 93.92655%, Correct: 1995, Total: 2124
;; Accuracy: 93.87947%, Correct: 1994, Total: 2124
;; Accuracy: 93.83239%, Correct: 1993, Total: 2124
;; Accuracy: 93.87947%, Correct: 1994, Total: 2124
;; Accuracy: 93.83239%, Correct: 1993, Total: 2124
;; Accuracy: 93.83239%, Correct: 1993, Total: 2124
;; Accuracy: 93.83239%, Correct: 1993, Total: 2124
;; Accuracy: 93.83239%, Correct: 1993, Total: 2124

;; Evaluation took:
;; 0.018 seconds of real time
;; 0.018714 seconds of total run time (0.014723 user, 0.003991 system)
;; 105.56% CPU
;; 64,026,632 processor cycles
;; 786,432 bytes consed

(defparameter scw-learner (clol:make-scw *mushrooms-dim* 0.999d0 0.001d0))
(loop repeat 10 do
  (clol:train scw-learner *mushrooms-train*)
  (clol:test scw-learner *mushrooms-test*))

;; Accuracy: 38.93597%, Correct: 827, Total: 2124
;; Accuracy: 66.00753%, Correct: 1402, Total: 2124
;; Accuracy: 69.96233%, Correct: 1486, Total: 2124
;; Accuracy: 81.40301%, Correct: 1729, Total: 2124
;; Accuracy: 88.46516%, Correct: 1879, Total: 2124
;; Accuracy: 93.36158%, Correct: 1983, Total: 2124
;; Accuracy: 96.65725%, Correct: 2053, Total: 2124
;; Accuracy: 97.834274%, Correct: 2078, Total: 2124
;; Accuracy: 98.44633%, Correct: 2091, Total: 2124
;; Accuracy: 98.06968%, Correct: 2083, Total: 2124

;; Evaluation took:
;;   0.038 seconds of real time
;;   0.037766 seconds of total run time (0.037766 user, 0.000000 system)
;;   100.00% CPU
;;   128,015,604 processor cycles
;;   2,064,384 bytes consed

このデータセットではSCW-Iが比較的良い性能を出した。過学習しがちなので早めに止める必要がある。

まとめ/感想

  • CLMLのランダムフォレストを試してみた
  • データセットが型指定しないunspecialized-datasetであり、遅い
  • あまり最適化されていないのでまだまだ速くなりそう
  • 精度も何故か良くない
  • CLMLの実装を叩き台にしてオンラインランダムフォレストを実装してみるつもり

Common LispでかんたんWebスクレイピング

LISP

WebスクレイピングとはWebから情報を自動的に集めてくるクローラを実装するということである。これを実現するにはHTTPクライアントとHTMLパーサ、そしてパースされた木構造から必要な情報を探索、抽出するセレクタがあればいい。Common Lispにはそれぞれに複数のライブラリがあるが、今回はHTTPクライアントにDexador、HTML/XMLパーサにPlump、CSSセレクタにCLSSを使う。これらのライブラリは全てQuicklispから入る。

(ql:quickload :dexador)
(ql:quickload :plump)
(ql:quickload :clss)

例としてこのロイターの記事 堅調地合い、1万8000円へ戻りを試す展開に＝来週の東京株式市場 を分析してみる。

HTTPクライアント: Dexador

まずHTTPクライアントでHTMLを取ってくる。これにはdexadorのget関数を使う。

(defparameter article-html (dex:get "http://jp.reuters.com/article/idJPL3N0U325520141219"))

dex:getは取得したHTML文字列、ステータス、メタ情報のハッシュ表、URI、ストリームを多値で返す。

"<!doctype html><html><head>
<title>
            堅調地合い、1万8000円へ戻りを試す展開に＝来週の東京株式市場
|ロイター</title>|
... 中略 ...
</html>
"
200
#<HASH-TABLE :TEST EQUAL :COUNT 14 {1003F285C3}>
#<QURI.URI.URI-HTTP http://jp.reuters.com/article/idJPL3N0U325520141219>
#<SB-SYS:FD-STREAM for "socket 192.168.11.12:43208, peer: 52.222.193.218:80" {1003DD4B13}>

HTMLパーサ: Plump

次に、plumpのparse関数でHTML文字列をパースする。これは木構造のルートに相当するCLOSオブジェクトを返す。

(defparameter parse-tree (plump:parse article-html))

;; => #<PLUMP-DOM:ROOT {1006E77F53}>

このオブジェクトの子を表示してみると、

(plump:children parse-tree)

;; #(#<PLUMP-DOM:COMMENT {1005D8C563}> #<PLUMP-DOM:TEXT-NODE {1005D8C853}>
;;   #<PLUMP-DOM:COMMENT {1005D8CF53}> #<PLUMP-DOM:TEXT-NODE {1005D8D253}>
;;   #<PLUMP-DOM:COMMENT {1005D8DB73}> #<PLUMP-DOM:TEXT-NODE {1005D8DE93}>
;;   #<PLUMP-DOM:COMMENT {1005D8E4A3}> #<PLUMP-DOM:TEXT-NODE {1005D8E773}>
;;   #<PLUMP-DOM:COMMENT {1005D8ECF3}> #<PLUMP-DOM:TEXT-NODE {1005D8F053}>
;;   #<PLUMP-DOM:DOCTYPE html> #<PLUMP-DOM:ELEMENT html {1005D8FDC3}>
;;   #<PLUMP-DOM:TEXT-NODE {1006274133}>)

このうちtext-nodeオブジェクトが文字列を持っている。木構造を走査してtext-nodeの持つ文字列だけを連結する関数を定義してみるとこうなる。

(defun node-text (node)
  (let ((text-list nil))
    (plump:traverse node
                    (lambda (node) (push (plump:text node) text-list))
                    :test #'plump:text-node-p)
    (apply #'concatenate 'string (nreverse text-list))))

普通に再帰で書いても行数はあまり変わらないと思うが、せっかくtraverse関数が用意されていたので使ってみた。

CSSセレクタ: CLSS

jQueryのように木構造からCSS要素を指定して部分木を抜いてくることができる。例えば、Plumpでパースした木からarticleTextというIDを持つ最初のノードを取り出すには以下のようにする。

(defparameter sub-tree (aref (clss:select "#articleText" parse-tree) 0))

この部分木に対して先ほど定義したnode-textを使うと記事の本文が得られる。

(node-text sub-tree)

;; "
;; ［東京　１９日　ロイター］ - 来週の東京株式市場は堅調な地合いが続く見通しだ。 （以下略
;; "

同様に記事タイトルやジャンルなども取ってこられる。

(node-text (aref (clss:select ".article-headline" parse-tree) 0))
; => "堅調地合い、1万8000円へ戻りを試す展開に＝来週の東京株式市場"

(node-text (aref (clss:select ".article-section" parse-tree) 0))
; => "Markets"

まとめとか

実際のページのソースを見てみると本文の部分はdivやspanが入り乱れているので単純な文字列のパターンマッチだとめんどくさそうに思えるが、HTMLをパースして木構造とすることで一気に扱いやすくなる。

ブラウザのインスペクタでクラス/IDを調べてclss:selectで指定するだけなので簡単。

ロイターの場合、サイトマップのXMLファイルがあるので上と同様に分析してURLのリストを取り出すことができる。

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

Common Lispで書かれた形態素解析器cl-igo / cl-mecabを使ってみた

LISP

cl-igoはCommon Lispから使える形態素解析器で、辞書にはmecab互換の辞書が使える。
roswellから入るようにgithubにミラーを作ったので、

ros install masatoi/charseq masatoi/cl-igo

でインストールできる。SBCL推奨とのこと。

igoのバイナリ辞書を作る

mecab-ipadic-2.7.0-20070801.tgzとigo-0.4.5.jarが同じディレクトリに入っているとして、

tar xzvf mecab-ipadic-2.7.0-20070801.tar.gz
java -cp ./igo-0.4.5.jar net.reduls.igo.bin.BuildDic ipadic mecab-ipadic-2.7.0-20070801 EUC-JP

でipadicというディレクトリができている。~/igo/ipadicにでも置いておくとする。

使ってみる

(ql:quickload :igo)

;; 辞書を読み込む
(igo:load-tagger "/home/wiz/igo/ipadic/")

(igo:parse "庭には二羽にわとりがいる。")

(("庭" "名詞,一般,*,*,*,*,庭,ニワ,ニワ" 0) ("に" "助詞,格助詞,一般,*,*,*,に,ニ,ニ" 1)
 ("は" "助詞,係助詞,*,*,*,*,は,ハ,ワ" 2) ("二" "名詞,数,*,*,*,*,二,ニ,ニ" 3)
 ("羽" "名詞,接尾,助数詞,*,*,*,羽,ワ,ワ" 4) ("にわとり" "名詞,一般,*,*,*,*,にわとり,ニワトリ,ニワトリ" 5)
 ("が" "助詞,格助詞,一般,*,*,*,が,ガ,ガ" 9) ("いる" "動詞,自立,*,*,一段,基本形,いる,イル,イル" 10)
 ("。" "記号,句点,*,*,*,*,。,。,。" 12))
(igo:wakati "庭には二羽にわとりがいる。")

("庭" "に" "は" "二" "羽" "にわとり" "が" "いる" "。")

mecab-ipadic-neologdのインストール

mecab-ipadic-neologdは新語などを大幅に増やした辞書で、SNSのデータを分析したいようなときに重要になる。
Ubuntu14.04でのインストール例は、

# 必要パッケージをインストール
sudo apt-get install mecab libmecab-dev mecab-ipadic-utf8 git make curl xz-utils file

git clone --depth 1 https://github.com/neologd/mecab-ipadic-neologd.git
cd mecab-ipadic-neologd/

# 途中で確認が出るのでyesを入力
./bin/install-mecab-ipadic-neologd -n

# インストール先
echo `mecab-config --dicdir`"/mecab-ipadic-neologd"
# /usr/lib/x86_64-linux-gnu/mecab/dic/mecab-ipadic-neologd

# 動作確認
mecab -d /usr/lib/x86_64-linux-gnu/mecab/dic/mecab-ipadic-neologd

igoのバイナリ辞書を作る

mecab-ipadic-neologdはUTF-8のみ対応ということなので、文字コードにUTF-8を指定してバイナリ辞書を作る。

cd build/
java -cp ../../igo-0.4.5.jar net.reduls.igo.bin.BuildDic ipadic-neologd mecab-ipadic-2.7.0-20070801-neologd-20161201/ UTF-8

これでipadic-neologdというディレクトリができる。これはJava版のIgoからなら以下のようにして使える。

java -cp ../../igo-0.4.5.jar net.reduls.igo.bin.Igo ipadic-neologd


しかしCommon Lisp版はEUC-JPのみ対応のようで、igo:load-taggerで読み込もうとするとエラーになってしまう。うーむ。

cl-mecabを使ってみる

Quicklispから入るcl-mecabでneologdが使えるかどうか試してみる。
with-mecabマクロに上記のmecabのコマンドラインオプションを渡すことができる。

2019年末版 形態素解析器の比較 - Qiita にあるneko.txtで試してみる。

(time
 (with-open-file (f "~/Downloads/neko.txt")
   (labels ((iter ()
              (let ((text (read-line f nil nil)))
                (if text
                    (progn (igo:parse text)
                           (iter))))))
     (iter))))

Evaluation took:
  0.088 seconds of real time
  0.087601 seconds of total run time (0.087601 user, 0.000000 system)
  100.00% CPU
  332,963,144 processor cycles
  210,504,608 bytes consed

(time
 (cl-mecab:with-mecab ("-d /usr/lib/x86_64-linux-gnu/mecab/dic/mecab-ipadic-neologd")
   (with-open-file (f "~/Downloads/neko.txt")
     (labels ((iter ()
                (let ((text (read-line f nil nil)))
                  (if text
                      (progn (cl-mecab:parse* text)
                             (iter))))))
       (iter)))))

Evaluation took:
  0.376 seconds of real time
  0.376776 seconds of total run time (0.336570 user, 0.040206 system)
  100.27% CPU
  1,432,001,462 processor cycles
  207,520,864 bytes consed

やはりCommon Lispネイティブな分cl-igoの方が若干速い。

NumPy vs Common Lisp 実行時間のみの比較

Lisp Python

NumPyとCommon Lispの速度比較記事。処理系の起動時間も測ってしまっているので処理自体にかかっている時間を測って比較してみる。
環境は

Python 3.4.3 + Numpy

import numpy as np
import time

N = 100000

# Python版
def sumup(n):
    return sum(range(1, n + 1))

# NumPy版
def sumup(n):
    return np.arange(1, n + 1).sum()

def main():
    print("python with numpy start.")
    result = {}
    for count in range(1, N + 1):
        result[count - 1] = sumup(count)
    print("python with numpy end.")

start = time.time()
main()
elapsed_time = time.time() - start
print("elapsed_time:{0}".format(elapsed_time))

SBCL 1.3.11

(defparameter *n* 100000)

;; 1. 引数のみ型宣言
(defun sumup1 (n)
  (declare (type fixnum n))
  (let ((sum 0))
    (loop for i from 1 to n
          do (incf sum i))
    sum))

;; 2. 引数と局所変数で型宣言
(defun sumup2 (n)
  (declare (type fixnum n))
  (let ((sum 0))
    (declare (type fixnum sum))
    (loop for i from 1 to n
          do (incf sum i))
    sum))

;; 3. 引数と局所変数で型宣言 + 最適化宣言、実行時型チェック無効
(defun sumup3 (n)
  (declare (type fixnum n)
           (optimize (speed 3) (safety 0)))
  (let ((sum 0))
    (declare (type fixnum sum))
    (loop for i from 1 to n
          do (incf sum i))
    sum))

;; 4. 引数と局所変数で型宣言 + 最適化宣言、実行時型チェック無効、loop内で使う変数iも型宣言
(defun sumup4 (n)
  (declare (type fixnum n)
           (optimize (speed 3) (safety 0)))
  (let ((sum 0))
    (declare (type fixnum sum))
    (loop for i fixnum from 1 to n
          do (incf sum i))
    sum))

;; 5. 引数と局所変数で型宣言 + 最適化宣言、実行時型チェック無効、loop内で使う変数iも型宣言、引数と返値の型を宣言する
(declaim (ftype (function (fixnum) fixnum) sumup5))
(defun sumup5 (n)
  (declare (type fixnum n)
           (optimize (speed 3) (safety 0)))
  (let ((sum 0))
    (declare (type fixnum sum))
    (loop for i fixnum from 1 to n
          do (incf sum i))
    sum))

(defun main ()
  (print "common lisp start.")
  (loop for count from 1 to *n*
        collect (sumup5 count))
  (print "common lisp end."))

(time (main))

結果

結果はこのようになる。

ftypeの宣言があまり効いていないが、なんにせよCommon Lispに適切なチューニングを施すことによってNumPyを使ったときよりも3倍以上も速くなっていることが分かる。