読者です 読者をやめる 読者になる 読者になる

@uents blog

Code wins arguments.

CourseraのMachine Learningコースを修了した

機械学習 Python

SICPを読み終えてからやると決めていた機械学習の勉強について、 まずはAndrew Ng先生のCoursera Machine Learningのコースを修了しました。 コースの途中、Pokemon GOにハマって危なかったけれど何とかクリア!

www.coursera.org

コースの内容

全11週に渡って講義と課題がみっちりとあります。 僕の場合、2016年5月末から受講して8月15日に修了しました。

最終的なデッドラインはジャスト12週で設定されているので、 うまく時間を取って課題をこなさないと修了できないようになっています。

コンテンツ

  • Lecture Videos and Texts
  • Quiz & Programming Assignments
    • 課題が週ごとに1〜3つ出る
    • Quizはチェックシート形式。5問中4問正解でパス
    • ProgrammingはOctave/MATLABで実装。 基本的にはアルゴリズム部分の穴埋め問題。80%正解でパス
  • Course Wiki
    • 週ごとに要点がまとめてある。Octave Tutorialが便利
  • Discussion Forums
    • 質問するとMentorがフォローしてくれるみたい
    • 個人的にはOctaveのコードが動かない時にちょっと覗いたくらいであまり使わなかった

講義のビデオは日本語の字幕が付いているけど、 課題は英語オンリーなので、ビデオの内容はしっかりとノートにとりました。 (でないと課題の英語解読で相当辛くなる..)

それとCourseraのスマートフォンアプリがあって、 講義ビデオはアプリ内にダウンロードできるので、 通勤電車の中でビデオを消化して、 課題は週末に取り組むといったルーチンで進めました。

主な内容

前述の通り全11週に渡って行うだけあってボリュームたっぷりです。

初学者向けのコースのため古典的な手法が多いですが、 機械学習の基礎的な考え方がじっくり学べてとてもよかったと思います。

  • Introduction (week 1)
    • Supervised/Unsupervised LearningやRegression/Classificationの違いなど
  • Linear Algebra Review (week 1)
  • Linear Regression (week 1-2)
    • 1週目はー変量、2週目は多変量の線形回帰。勾配法と正規方程式について
  • Octave/MATLAB Tutorial (week 2)
  • Logistic Regression (week 3)
    • ロジスティック回帰による分類問題について
  • Neural Networks (week 4-5)
  • Evaluating a Learning Algorithm, Bias vs. Variance (week 6)
    • 学習アルゴリズムの評価やバイアス-バリアンス検定など。個人的にはいちばん勉強になった週
  • Support Vector Machines (week 7)
  • K-Means (week 8)
    • 教師なし学習の例としてK-Meansによる分類問題
  • Principal Component Analysis (week 8)
    • 特徴量の次元圧縮・復元やvisualizationへの応用
  • Anomaly Detection (week 9)
    • 一変量および多変量正規分布による異常検定
  • Collaborative Filtering (week 9)
  • Large Scale Machine Learning (week 10)
    • 確率的勾配法やオンライン学習、Map-Reduce的な分散システムについて
  • Photo OCR (week 11)
    • 画像中の文字認識を例に、 機械学習システムのパイプライン構築やリソース配分の考え方について

具体的な内容は以下が詳しいです。

qiita.com

修了証

image

$79でCourseraからデジタルのCertificateが発行されます。

少々値が張りますが、コースの内容がとてもよかったので Andrew先生やCourseraへの感謝の意味も込めて購入しました。
($79で書籍を買ってもこの内容を勉強しようと思ったら11週じゃ絶対無理!)

Pythonでの復習レーン

コースは修了したものの急ピッチかつプログラミング課題も穴埋めだったため、 消化不良というかスクラッチ機械学習の実装できそうな感がないです。

そこでPythonを使った復習レーンを進めていますが、 これがとても楽しくてハマってます!Pythonすばらしすぎる!

https://github.com/uents/coursera-ml

こちらもおいおいブログでまとめて行きたいと思います。

計算機プログラムの構造と解釈(SICP)を読み終えて

SICP Scheme

SICPようやく読み終わりました。

2014年5月から読み始めたので、 足かけ丸2年。愛娘も1才から3才に成長。

練習問題やブログの記事を上げていたGitHubのコミットグラフを見ると、 サボっていた期間も結構あり、実働は1年ちょっとくらいかな。

image

他のSICPブログを見ると、ほぼ全問解きながら3.5ヶ月や 6ヶ月で読み終えた方もいるようなので、決してペースは早くもないし、 練習問題も特に§5の後半は全然解けていないですが、 社会人で仕事・家事・育児をこなしつつ、通勤時間・深夜・たまの有休を 使っての活動だったので、結構頑張ったかなという感はあります。

SICPで学んだこと

過去の記事を見返しながら列挙してみました。◎,△は僕の理解度です。

  • ◎ 変数の束縛と代入の違い、環境との関係を理解した
  • ◎ 関数がファーストクラスである言語の実装の考え方を理解した
  • 再帰呼び出し高階関数が自然と使えるようになった。末尾再帰を意識するようになった
  • ◎ 関数適用や評価の順序を意識しながら実装できるようなった
  • ◎ データ主導やメッセージパッシングの戦略の違い理解した
  • ◎ 型変換の動機と過程を理解した
  • ◎ 局所状態とクロージャによる抽象化の構築を理解した
  • ◎ ストリームと遅延評価を理解した
  • △ 字句解析、構文解析を実装できるようになった (BNFコンバータまでは使ってないので△)
  • Schemeインタプリタフルスクラッチで実装した
  • ◎ 継続や非決定性計算の概念を理解できた
    • §4.3でcall/ccに出会い、§5.2のレジスタマシンのconitnueレジスタがまさに継続だと気づけた
  • レジスタマシンで動作するインタプリタコンパイラの構造を理解した (練習問題を解いていないので△)

さらに発展的なものとして、

  • 万能機械の概念を知り、ユーザープログラムであれ処理系であれ 解くことのできる問題もそうでない問題も同じ、というメタな視点が得られた
  • プログラムはある意味全て処理系、という考え方に至るようになった

副次的なものとして、

  • 社会人での継続学習、ブログを書く習慣が定着した
  • GitやGitHubが使えるようになった
  • わからなくても書いて動かせば道は開ける、と思えるようになった。 まずは手を動かすことが大事!

ざっとあげてこんなところかな。

読み始めの頃といまの比較

読み始めた頃の自分といまの自分を比較してみました。

読み始めたころの自分 いまの自分
関数型言語を習得したい SICP関数型言語を習得する本ではないが、
高階関数クロージャあたりは自然と使えるようになり、めちゃめちゃ楽しい!
情報工学へのコンプレックス インタプリタコンパイラの学習を通して、全く無くなりました!
単なる力試しがしたい 学生の頃の自分と今の自分は全く別。
自分自身でも成長が感じられた!
プロブラマーとしてもっと飛躍したい 2年前とは全く違う景色は見えている気がする
(これはこれからのお楽しみ!)

まとめ

image

長い時間はかかりましたが、間違えなくその価値はあったと断言できます。

やはりSICPは計算機科学の入門書でした。 こうして読み終えたいま、改めて学生時代に読んでおくべきだったと感じてます。 (大学時代のボスに言われたことは正しかった..)

それでも、得たものを大きさをこうやってまとめると、 社会人である程度のキャリアを積んだいまでも、読み切ることができて良かったです。

最後に、RacketやGaucheのような素晴らしい処理系、 ウェブで公開されている原文、和田先生やその他有志の方の翻訳版、 練習問題の回答など今ではとっかかりがたくさんあるし、 昔に比べてSICPの敷居はずいぶん下がったように思います。

これらが無ければ絶対に完走することはできなかったでしょう。 先人のみなさま方、ほんとうにありがとうございました。


※「SICP読書ノート」の目次はこちら

SICP 読書ノート#79 - 5.5 翻訳系(4) (pp.362-366)

SICP Scheme

いよいよ最後のセクション。練習問題はやってないです。

5.5.7 翻訳したコードと評価器のインターフェース

(compile)コンパイルしたコードを積極制御評価器で動作させる。

いつものように、まずはRacketで動かせるようにした。

https://github.com/uents/sicp/tree/master/ch5.5.7-interfacing-compiler-to-evaluator

評価器のトレースを有効にして、かんたんな手続きをコンパイルしてみる。

eceval-compiler.scm<feff>> (eceval 'trace-on)

eceval-compiler.scm<feff>> (compile-and-go '(define (add1 x) (+ x 1)))
'(label = controller)
'(inst = (assign compapp (label compound-apply)))
'(inst = (branch (label external-entry)))
'(label = external-entry)
'(inst = (perform (op initialize-stack)))
'(inst = (assign env (op get-global-environment)))
'(inst = (assign continue (label print-result)))
'(inst = (goto (reg val)))
'(inst = (assign val (op make-compiled-procedure) (label entry1) (reg env)))
'(inst = (goto (label after-lambda2)))
'(label = after-lambda2)
'(inst = (perform (op define-variable!) (const add1) (reg val) (reg env)))
'(inst = (assign val (const ok)))
'(inst = (goto (reg continue)))
'(label = print-result)
'(inst = (perform (op print-stack-statistics)))
'(total-pushes = 0 max-depth = 0 curr-depth = 0)
'(inst = (perform (op announce-output) (const ";;; EC-Eval value:")))

;;; EC-Eval value:
'(inst = (perform (op user-print) (reg val)))
ok

;; (snip ...)
  • (assign val (op make-compiled-procedure) (label entry1) (reg env)))で 戻り先はentry1となるよう手続きをコンパイルし、その実体をvalに格納
  • (perform (op define-variable!) (const add1) (reg val) (reg env)))コンパイル済みの手続きをadd1という変数に束縛
  • val'okを格納してREPLに戻る

といった流れ。

次に、コンパイル済みの手続きを実行してみる。 出だしの処理はこれまで見てきた内容と同じなので詳細は割愛するが、 ev-application以降の処理で procarglに手続きと引数が格納され、apply-dispatchへジャンプする

;;; EC-Eval input:
(add1 5)

'(inst = (assign env (op get-global-environment)))
'(inst = (assign continue (label print-result)))
'(inst = (goto (label eval-dispatch)))
'(label = eval-dispatch)

;; (snip ...)

'(label = ev-appl-accum-last-arg)
'(inst = (restore argl))
'(inst = (assign argl (op adjoin-arg) (reg val) (reg argl)))
'(inst = (restore proc))
'(inst = (goto (label apply-dispatch)))

apply-dispatchからこのセクションで追加したcompiled-applyへジャンプ。 さらに先程のentry1へとジャンプする。

'(label = apply-dispatch)
'(inst = (test (op primitive-procedure?) (reg proc)))
'(inst = (branch (label primitive-apply)))
'(inst = (test (op compound-procedure?) (reg proc)))
'(inst = (branch (label compound-apply)))
'(inst = (test (op compiled-procedure?) (reg proc)))
'(inst = (branch (label compiled-apply)))
'(label = compiled-apply)
'(inst = (restore continue))
'(inst = (assign val (op compiled-procedure-entry) (reg proc)))
'(inst = (goto (reg val))) ;;=> ここで`entry1`へジャンプ

すでにprocにはコンパイル済みの手続き (この場合はCompound Procedureのような複合手続き)が格納されているため、 それに対してarglの非演算子を適用する。

返り値はvalに格納され、REPLへと戻る。

'(label = entry1)
'(inst = (assign env (op compiled-procedure-env) (reg proc)))
'(inst = (assign env (op extend-environment) (const (x)) (reg argl) (reg env)))
'(inst = (assign proc (op lookup-variable-value) (const +) (reg env)))
'(inst = (assign val (const 1)))
'(inst = (assign argl (op list) (reg val)))
'(inst = (assign val (op lookup-variable-value) (const x) (reg env)))
'(inst = (assign argl (op cons) (reg val) (reg argl)))
'(inst = (test (op primitive-procedure?) (reg proc)))
'(inst = (branch (label primitive-branch3)))
'(label = primitive-branch3)
'(inst = (assign val (op apply-primitive-procedure) (reg proc) (reg argl)))
'(inst = (goto (reg continue)))
'(label = print-result)
'(inst = (perform (op print-stack-statistics)))
'(total-pushes = 5 max-depth = 3 curr-depth = 0)
'(inst = (perform (op announce-output) (const ";;; EC-Eval value:")))

;;; EC-Eval value:
'(inst = (perform (op user-print) (reg val)))
6

;; (snip ...)

細かくは理解できていないけど、targetlinkageをうまく使うことで、 積極制御評価器とコンパイル済みコードを繋ぐことができる。

解釈と翻訳

まとめるとこんな感じでしょうか。

  • 解釈系と翻訳系の利点の違い

    • 解釈系(インタプリタ)はプログラムの実行ステップが 抽象化によって構成されているので、 対話的なプログラミングやデバッグに優れている。(§4.1や§5.4で見た通り)
    • 翻訳系(コンパイラ)はプログラムの実行ステップが、 機械語によって構成されているので、ずっと高速に実行でき、 高レベルの抽象化の壁を超えた最適化も行える。(§5.5で見た通り)
  • 異なるマシンアーキテクチャへの言語の移植戦略

    • 大きくは2つの戦略に分かれる
      1. 積極制御評価器をベースにして、新しいマシン命令に置き換える
      2. 翻訳系をベースにして、新しいマシンコードを生成するよう ジェネレータを作り替える
    • 2つ目の戦略の場合、元のLispシステムで動くコンパイラコンパイルして それをコンパイル済みの実行時ライブラリとリンクすることで、 どんなLispプログラムでも実行できるようになる

§4の超循環評価器から§5かけて、処理系の中へ中へと入っていくと、 様々な観点でインタプリタコンパイラの本質が浮き彫りになって理解が深まる。

というわけで、やっと読み終わりました。最後にまとめたいと思います。


※「SICP読書ノート」の目次はこちら

SICP 読書ノート#78 - 5.5 翻訳系(3) (pp.360-362)

SICP Scheme

今回は「5.5.6 文面アドレス」から。

5.5.6 文面アドレス

「文面」とはlexicalの直訳のよう。

これまでの評価機は変数の値を探す際に、実行時にenvフレームを 都度探索していたので、それなりに計算コストがかかっていたはず。

Schemeはレキシカルスコープなので、コンパイル時にアドレッシングを済ませといて コンパイル時環境(compile-time environment)として管理できれば、 実行時の変数探索のための計算コストを省けて、最適化できるのでは? というお話だと思う。

で、練習問題を解こうと思ったけど、手元のソースコードでは 環境フレームを以下のようにRacketのHash Tableで作り変えていたため、 そのままではアドレッシングの実装ができない。

(define (make-frame vars vals)
  (let ((frame (make-hash)))
    (map (lambda (var val) (hash-set! frame var val))
         vars vals)
    frame))

(define (extend-environment vars vals env)
  (with-handlers
      ([exn:fail? (lambda (exn)
                    (error "extend-environment: arguments error:"
                           vars vals))])
    (cons (make-frame vars vals) env)))

;; ...

環境フレームの実装をSICPのテキスト通りに戻すと set-car!set-cdr!を使う必要が出てくるので、 R5RSモードに切り替えてmutable pairsを使えるようにしたが、 今度はレジスタ計算機シミュレータの方に影響が出てうまく動かない。

RacketでSICPをやるとやっぱここがいちばん辛いな、と改めて思う。 最初から全部 #lang r5rs でやれば良かったのかもしれない。

http://docs.racket-lang.org/r5rs/r5rs-mod.html

これ以上頑張って直す元気もないので、あきらめて次に進みます。残念..


※「SICP読書ノート」の目次はこちら

SICP 読書ノート#77 - 5.5 翻訳系(2) (pp.343-360)

SICP Scheme

前回に続き翻訳系のセクションを読み進めて行きました。

5.5.2 式の翻訳

defineset!などの特殊形式のコンパイルの話。ざっと読んだ。

5.5.3 組み合わせの翻訳

主に手続き適用のコンパイルの話。簡単にまとめると、

  • compile-applicationでは、演算子と非演算子がそれぞれコンパイルされ、 compile-procedure-callを呼び出す
  • compile-procedure-callでは、targetに返り値を格納し、 実行後はlinkageに戻る、手続き適用の実行コードが生成される
  • 手続き適用の実行コード生成の処理の本体である complie-proc-applでは、 targetvalか否か、linkagereturnか否か、で 4通りのコードのいずれかを生成する

個人的には、超循環評価機でもそうだったが、非演算子が評価・集約され 演算子手続きに適用される振る舞いを見ると、JavaScriptarguments[]arguments.calleeはきっとこれなんだろうなあと、 勝手に腑に落ちました。

5.5.4 命令列の組み合わせ

命令シーケンスのコンパイルの話。

要は、append-instruction-sequencesなどで命令シーケンスを連結し、 preservingで余分なスタック退避を取り除いている、ということだと思うが、 処理の細かい点まで理解しようとすると結構むずかしい。

ただ、これらの手続きの出力結果としてどういうコードを生成するかが より重要だと思うので、細部は置いといて先へ進みます。

それと、脚注に結構おもしろいことが書いてあった。 訳文を非公式SICP(真鍋版)より引用。

コンパイラに末尾再帰のコードを生成させるというのは 素直な考え方のように思えるかもしれません。 しかし、C言語Pascalを含め、一般的な言語ではこれを行わず、 そのためこれらの言語では反復プロセスを手続き呼ひ出しだけで表現することはできません。 これらの言語で末尾再帰が難しいのは、それらの実装では スタックをリターンアドレスを格納するのに使うだけでなく、 手続きの引数や局所変数を格納するためにも使っているからです。 この本で記述されているSchemeの実装は、 引数と変数をメモリに入れ、ガベージコレクションの対象にしています。 変数と引数にスタックを使う理由は、 ほかのところでガベージコレクションを使わない言語では、 そうすることによってガベージコレクションが必要なくなり、 またそれがより効率的たと一般に信じられているということです。 実際のところ、高機能なLispコンパイラは、末尾再帰を壊さずに 引数のためにスタックを使うことかてきます。 (snip..) また、そもそもスタック割り当てはガベージコレクションより効率的なのか というところにも議論がありますが、この問題の詳細はコンピュータアーキテクチャの 細部によるようです (snip..)

こうやって処理系を内部を追っていくと、 末尾再帰ガベージコレクションを持つ・持たないの戦略の違いがわかってとても良い。

5.5.5 翻訳したコードの例

compileSchemeソースコードコンパイルすると、 どういったオブジェクトコードが生成されるか、という話。 前に問題5.31、5.32で試してきたような内容。

問題 5.37

preservingで行っている不要なスタックの退避・復元を取り除くと、 生成するコードはどう変化し、不要なスタック演算は何かを特定せよ、という問題。

preservingから不要なスタック演算を省く処理を削除する。

 (define (preserving regs seq1 seq2)
   (if (null? regs)
      (append-instruction-sequences seq1 seq2)
      (let ((first-reg (car regs)))
-      (if (and (needs-register? seq2 first-reg)
-               (modifies-register? seq1 first-reg))
            (preserving (cdr regs)
             (make-instruction-sequence
              (list-union (list first-reg)
                          (registers-needed seq1))
              (list-difference (registers-modified seq1)
                               (list first-reg))
              (append `((save ,first-reg))
                      (statements seq1)
                      `((restore ,first-reg))))
-           seq2)
-          (preserving (cdr regs) seq1 seq2)))))
+            seq2))))

問題 5.31の(f (g 'x) y)コンパイルしてみる。

'((env continue)
  (env proc argl continue val)
  ((save continue)
   (save env)
   (save continue)
   (assign proc (op lookup-variable-value) (const f) (reg env))
   (restore continue)
   (restore env)
   (restore continue)
   (save continue)
   (save proc)
   (save env)
   (save continue)
   (assign val (op lookup-variable-value) (const y) (reg env))
   (restore continue)
   (assign argl (op list) (reg val))
   (restore env)
   (save argl)
   (save continue)
   (save env)
   (save continue)
   (assign proc (op lookup-variable-value) (const g) (reg env))
   (restore continue)
   (restore env)
   (restore continue)
   (save continue)
   (save proc)
   (save continue)
   (assign val (const x))
   (restore continue)
   (assign argl (op list) (reg val))
   (restore proc)
   (restore continue)
   (test (op primitive-procedure?) (reg proc))
   (branch (label primitive-branch1))
   compiled-branch2
   (assign continue (label after-call3))
   (assign val (op compiled-procedure-entry) (reg proc))
   (goto (reg val))
   primitive-branch1
   (save continue)
   (assign val (op apply-primitive-procedure) (reg proc) (reg argl))
   (restore continue)
   
   ;; snip...

おお! 元々のpreservingでは一切出なかったenvへのスタックの退避・復元が、 envから変数を探索する度に実行されることがわかる。 問題 5.31でenvの退避・復元が出なかった理由の予想はどうやら当たっていたみたい。

次は「5.5.6 文面アドレス」から。


※「SICP読書ノート」の目次はこちら