Aizu-SICP 第九回
やりました。今回の範囲は P76 1.3.4 ~ P81 1.3.4 終わりまでです。
1.3.4 返り値としての手続き
ここまでの例では、手続きを引数として渡す能力が私たちのプログラミング言 語の表現力を大幅に拡張するということを見てきました。この表現力は、返り 値自身が手続きであるような手続きを作成することによって、さらに強力にで きます。
(Page 76).
例が少し複雑であるため目的を見失いがちであるが、ここでの重要なこと上の文の通り (SICPにおけるプログラミング言語の具体例としての) Scheme が手続きを受けとって新しい手続きを返すといった高い表現力を持っているということであり、その強力さを示すための例としてニュートン法などが利用されている。
(define (average-damp f) (lambda (x) (average x (f x)))) ;; (Page 76).
少しわかりづらかったが、練習問題 1.36 で使った式を使って実際にあてはめてみるとそのままであることがわかる。
この定式化は、この手法の三つの考え方を明確に示しています。不動点探索、平均緩和法、そして関数 y → x/y です。この平方根の手法の定式化を1.1.7 節の 元のバージョンと比べると学ぶところがあるでしょう。これらの手続きは同じ プロセスを表現しているということに気をつけて、これらの抽象化を使って表現することでどれだけ考え方が明確になっているかを見てください。
(Page 77).
比べてみる。
;; 1.1.7 (define (improve guess x) (average guess (/ x guess))) (define (good-enough? guess x) (< (abs (- (square guess) x)) 0.001)) (define (sqrt-iter guess x) (if (good-enough? guess x) guess (sqrt-iter (improve guess x) x))) (define (sqrt x) (sqrt-iter 1.0 x)) ;; 本節 (define tolerance 0.00001) (define (fixed-point f first-guess) (define count 0) (define (close-enough? v1 v2) (< (abs (- v1 v2)) tolerance)) (define (try guess) (set! count (+ count 1)) (let ([next #?=(f guess)]) (if (close-enough? guess next) next (try next)))) (try first-guess)) (define (average-damp f) (lambda (x) (average x (f x)))) (define (sqrt x) (fixed-point (average-damp (^[y] (/ x y))) 1.0))
最初に見た時は関数全体で見てしまったため、そこまで違うだろうか？と思ったが、1.1.7節では停止条件が「二乗すると x に近くなったら」という固有のものであった。しかし新しい方では不動点を求めるという一般化された形である。また1.1.7節の方では improve 内に (average guess (/ x guess)) が埋め込まれており値の更新式が確認しづらい。しかし新しい方では fixed-point にその関数を渡すようになっている。これらの二つは sqrt の定義を確認することですぐにわかるようになっている。これが「これらの抽象化を使って表現することでどれだけ考え方が明確になっているか」を表していると考えられる。
ニュートン法
61 微積分の入門書では、ニュートン法は普通、xn+1 = xn − g(xn)/Dg(xn) という近似列として記述されています。私たちはプロセスに関して語る言語を持っているため、不動点の考えを使って手法の記述を簡単にできます。
(Page 78 注釈).
この文が読書会中参加者全員がいまいちピンと来ていなかったが、P78 の一番上の式というのは通常のニュートン法の式では無く、左辺が f(x) になっている。これはニュートン法を繰り返していった時に、最終的な結果として求まる x というものを代入した時に、f(x) = 0 となる (グラフとx軸が交差する) 点を表している。すなわちこの関数の不動点を求めることがニュートン法を用いて関数の解 x を求めることと同じになるのでこのような式で表現できる。注釈はそれを表していると考えられるが、読みとれなかった。
追記
「f(x) = 0 となる (グラフとx軸が交差する) 点を表している」と書いてしまったが、実際には勾配が 0 となる点でならば停止しうる。
多くの関数 g と、十分によい初期推測値 x に対して、ニュートン法は g(x) = 0 の解に急速に収束します。62
(Page 78).
「十分によい初期推測値」とはいったい何なのか。アマゾンの奥地へ飛ぶ必要がある。
ただ、この後で定義する newtons-method を利用すると、第八回のまとめで書いたような方程式の場合でも、適当な値を入力しても基本的に解が求まるようになるのでそこまで気にしなくてもいいのかもしれない。しかしなぜニュートン法を利用すると解が求まりやすいのかを理解できていない。
追記
機械学習における重みの更新と同様に、勾配の逆方向に x は更新されていくので初期値から最も近い解の近付いていくのだろうと考えた。解に近づくにつれて勾配は小さくなって行くので基本的に収束するということもわかった。
以下は x^2 + 5x + 6 を初期値 35 でニュートン法を使った例。
gosh> (newtons-method (^[x] (+ (* x x) (* 5 x) 6)) 35) #?- 16.253335843501315 #?- 6.883335900113309 #?- 2.2049919310939874 #?- -0.12093403572980543 #?- -1.2579229998223325 #?- -1.77832152189135 #?- -1.965952134171057 #?- -1.9989143418927326 #?- -1.9999988130790058 #?- -1.9999999999867224 -1.9999999999867224
抽象化とファーストクラス手続き
プログラマである私たちは、プログラムに潜んでいる抽象化を見つけ、それらの抽象化を使ってプログラムを構築し、さらに強力な抽象化を生み出すた めにそれらを一般化する機会を見逃さないようにしなければいけません。これは、いつでも可能な限り抽象的にプログラムを書かなければいけないということではありません。熟練プログラマであれば、タスクに対して適切な抽象レベルを選べるものです。しかし、新しい状況でも適用できるように、このような抽象化によって考えられるようになっておくことは重要です。高階手続きが重要なのは、これらの抽象化を明示的に私たちのプログラミング言語で表現することを可能にし、ほかの計算の要素と同じように扱えるようにしてくれるからです。
(Page 80).
この項のまとめ。
一章を終えて
ここまでで練習問題の一部 (過半数) を除く一章を読み終えました。数学の話が非常に多くなる場所であることは聞いており不安な場所だったが、読書会という形で参加者で集まって考え合うことができたおかげで楽しく読むことができた。一人では多分読み飛ばしてしまっていただろうと思うので、ここを読書会で読めたのは非常に助かりました。参加者も数学的な場所に対して自分が怖じ気ついている時に「やりましょう！」というような形で後押ししてくれたのでありがたかったです。
謝辞のようになりました。
また本来この Aizu-SICP の記事は参加できない方向けに書くというモチベーションで始めましたが、現在は読書会の後で再び一人で読みなおし、そのまとめだけでなく、議論などをふまえて理解をさらに進めるために書くようになりました。実際に読書会の時には少し曖昧だったものがこの記事をまとめている内に考えが深まる経験をしているのでまとめを書くようにして良かったと思います。
少し問題があるとすれば、参加者のひらめきも自分が思いついたかのように書いてしまっている箇所があるので、この SICP に関する記事は参加者達のおかげで書けているという点も、もし参加者以外に読んでいる方がいればご留意頂きたいです。
やはり謝辞のようになりました。
次回は飛ばした練習問題を解く予定です。