naoya_t@hatenablog

いわゆるチラシノウラであります

トップ > Coursera

今週のCoursera（〜7/3）

Coursera

コンパイラ実装に優先的に時間を割いたので講義ビデオ消化は後回し。

あと、7/17から量子力学と量子計算のクラスが始まるので受講登録しました。これは楽しみ。

参加しているクラス

Machine Learning (Andrew Ng, Stanford) - 4/23開講。現在第10週

  • XVI. Recommender Systems
    • 協調フィルタリングの話。復習テスト+実装課題(ex8)あり。
    • 実装課題が終わったのが提出期限19分前。焦った

Compilers (Alex Aiken, Stanford) - 4/23開講; 5/10参戦。現在第10週

  • Programming Assignment 4
    • 最終フェーズ。Cool言語のASTからMIPSコードを生成する部分の実装。
    • テスト項目が59個（各1点。lambda-calculusとGCのテストを含むやつ1つだけ5点で計63点）
    • MainクラスをnewしてMain.main()を読んでくれるコードは用意されているので、空っぽのmain() をMIPSで書いてみるあたりから。1点目が取れ始めるまでが長かった。
    • 週末にカラオケ屋の1室でコンパイラ実装オフを開催

↑最初は「自然言語処理カラオケ」しようと思ってたんですが
↑なんぞこれ
↑JITとか面白そうだけど今回の課題締め切りに間に合いそうにないので見送り
↑コンパイラを実装します
↑PFIの人まで来ますか...
↑(」・ω・)」うー！(／・ω・)／にゃー！係ありがとうございます

    • メソッドやメンバ変数の継承とか面倒だった。基底クラスにnew SELF_TYPEして返すメソッドがあった場合、そのオブジェクトの型は継承したクラスの方。てことはnewに相当する処理を動的に呼ばないといけない、とか。あとtypcaseの評価順とか。
    • 63点満点達成！
  • (Week 9) Register Allocation
    • 中間言語ではテンポラリ変数を無尽蔵に使っているが、マシンのレジスタは有限。どう割り振るか
    • FORTRANコンパイラの頃はこなれていなかったが、後にグラフ彩色アルゴリズムの応用でましになった
    • グラフ彩色に関する選曲はこの辺りか

  • (Week 9) Garbage Collection
    • ストレージ管理の話。レジスタ、キャッシュ（L1, L2[, L3]）、メモリ、ディスク
    • コンパイラはキャッシュの管理がまだ苦手
    • 神の言語LISP界隈で研究されてきたGCが90年代以降のJava人気で主流に
    • （途中）

Automata (Jeffrey Ullman, Stanford) - 4/23開講。全6週

  • 修了済

Computer Vision：The Fundamentals (Jitendra Malik, UCB) - 4/23開講; 5/25参戦

  • 見てない

来季があれば絶賛参加予定

Natural Language Processing (Dan Jurafsky, Christopher Manning) - TBA

  • ほとんど見てない

今週のCoursera（〜6/24）

Coursera

参加しているクラス

Machine Learning (Andrew Ng, Stanford) - 4/23開講。現在第10週

  • 貯金あるのでお休み

Compilers (Alex Aiken, Stanford) - 4/23開講; 5/10参戦。現在第10週

  • Week 8の内容。最適化！
    • 中間コード、peephole、データフロー解析、定数伝播、ループ解析、etc.
    • そろそろProgramming Assignment 4（最終フェーズ。Cool言語のASTからMIPSコードを生成する部分の実装）に手を付けたい

Automata (Jeffrey Ullman, Stanford) - 4/23開講。全6週

  • 修了済

Computer Vision：The Fundamentals (Jitendra Malik, UCB) - 4/23開講; 5/25参戦

  • 見てない

来季があれば絶賛参加予定

Natural Language Processing (Dan Jurafsky, Christopher Manning) - TBA

  • ほとんど見てない
  • ちょっとFSNLP読んでた

先週〜今日のCoursera（〜6/19）

Coursera

週末はPRMLってたのと、今日Ullman先生のAutomataのクラスのFINAL EXAMが終わったのとで今日までの分のまとめを書こうかなと。

ビデオ消化が間に合っていないAutomataのクラス、のなかなか理解できない特定の1本のビデオを中心に進めた（というか停滞した）。

参加しているクラス

Machine Learning (Andrew Ng, Stanford) - 4/23開講。現在第9週

Compilers (Alex Aiken, Stanford) - 4/23開講; 5/10参戦。現在第9週

  • Week 7の内容。この辺りはSICPの5章を思い出しますね
    • Code Generation: MIPSコード吐くよ！
    • Operational Semantics: 操作的意味論

Automata (Jeffrey Ullman, Stanford) - 4/23開講。全6週 →修了！

  • FINAL EXAMを6/19 15:59:00JSTまでに受験しなければならない
  • 講義ビデオ残りあと2時間38分
    • 19. Specific undecidable problems: ライスの定理、ポストの対応問題
      • このビデオで1週間以上停滞していたと思う
      • Wikipediaの記事などと照らしあわせつつ頑張って解釈したけどこれは分かりにくい。ちゃんと理解できてないと思う。
      • 「何言ってるかさっぱり意味不明なのでとりあえずメモっておいて、後で例を挙げてくれた時にその例から遡って何を説明しようとしていたのかを憶測する」対Ullman戦法
    • 20. P and NP
      • ビデオ内クイズ3問目が納得行かない
    • 21. Satisfiability and Cook's theorem
      • 証明にうなずけるほどの理解はない気が
    • 22. Specific NP-complete problems
      • 3-SATは楽しかった
      • 最後のpartition-knapsackへのreductionのsとか2kとかが謎なまま
  • FINAL EXAM
    • 頑張ってビデオ見終わった。締め切り1時間半前に問題を開く。
    • 3時間とかいうけど1時間半ぐらいあれば何とかなるだろう、と思ってたら25問もあった。時間ぎりぎり＞＜
    • 採点結果はすぐ分かる。スコアは148.00/170.00点。
      • ノート見てじっくり考える時間があればあと10〜15点は取れたと思う。
      • しかし最後のNP完全/NP困難あたりの理解が浅いので,何か別の本でも読んでおさらいしたい。
      • コースの配点は普段の宿題:50%, FINAL:50%らしい（ので全体の93.5%を確保。certificateげｔ確定）
  • Problem Session
    • FINAL EXAMを終えてから、「Problem Session」というタイトルのビデオ4本を見た。講義の中でわかりにくい個所、質問の多い個所、間違って理解してる人の多い個所などを解説してくれてる補足ビデオ。
    • 本来EXAMの前に見ることを想定されてるようだ
  • これでおしまい！
    • Automataの講義ビデオは、Coursera向きに構成変えたほうがよいと思う。
      • 証明パートを別ビデオにするとか。
    • ていうかこの内容で6週間は詰め込みすぎかも
    • Forumに「だらだら本読んでるだけじゃんこれじゃ意味わかんないよ」的なコメントがあったけど思わず頷いた
    • とはいえAutomataは興味深いテーマで、面白いところは面白かった
    • Good bye, and good luck!

Computer Vision：The Fundamentals (Jitendra Malik, UCB) - 4/23開講; 5/25参戦

  • 見てない

来季があれば絶賛参加予定

Natural Language Processing (Dan Jurafsky, Christopher Manning) - TBA

  • 見てない

今週のCoursera（〜6/9）

Coursera

（TODO: 週末に進めた分をあとで追記）

参加しているクラス

Machine Learning (Andrew Ng, Stanford) - 4/23開講。現在第8週

  • K-Means法で教師なしクラスタリング
    • K-Meansは（個人的には割と）直感的な手法なのでまあ余裕
    • そういえば以前にAWKで実装したりとかした
  • 主成分分析 (PCA) で次元数削減
    • 分かりやすかった。
    • "99% of variance is retained."

「数学的にいうとこの共分散行列は常に symmetric semidefinite を満たしているんだけどまあ知らなくてもいいからね」

（線形代数的な性質を強調しすぎないのが好感）

  • Ng先生のクラスは本当に分かりやすいと思うので（特にPRML買ったけど歯が立たない人は）みんな見るべき

Compilers (Alex Aiken, Stanford) - 4/23開講; 5/10参戦。現在第7週

  • PA3も終えて2週間分貯金があるので今週はお休み。
  • 次はWeek 6。
    • self型の説明がここにあるのか... PA3やる前に見ておけばよかった

↓

  • 貯金とか言ってたけど想定カリキュラムから見ると2週間のビハインド。課題の締め切り的に余裕があるにすぎない。この先生の講義は発音も綺麗だし1.25倍速でも聞き取りやすいのでさっさと進めて（遅れを取り戻して）しまおう
  • というわけでWeek 6のビデオを全部見た(6/11)。概ね知ってる内容（だけれどここで言われている通りにしないとQuizが解けないので黙って見る）
    • Cool Type Checking: 静的型と動的型、SELF_TYPE型の導入
    • Runtime Organization: スタックとかヒープとか、Activation Record（frameのことだ）とか。
  • Quizは自分の脳内がデフォルトでレキシカルスコープになってるのがよくわかる問題だった

Automata (Jeffrey Ullman, Stanford) - 4/23開講。全6週。

  • Week 5: Turing Machine
    • Homeworkのデッドラインがあるので頑張ってビデオ消化。
    • 言葉で（用語の操作で）説明してる時には何が言いたいのかさっぱり分からないが、その後に具体的な例を使って説明してくれたら遡って理解できる、という事がAutomataの講義では多い。というか自分的にはわかりにくい進め方なので辟易。というかビデオ長い。
    • 面白いテーマだと思うのでここはもっと楽しく観たいんだけど
    • 結局またビデオ全部見ないままにHomeworkを解いた
    • アンケートに答えろとメールが来たので、1本1本のビデオが長いので小分けにするなりブックマークできるようにするなりしてほしいとかCCの字幕タイミングずれてて泣けるとか書いて送った。
  • 最後の復習問題（NP完全とか非決定性とか）が火曜の15:59締め切りなので頑張って最後まで見ないと。
    • 講義ビデオ残りあと2時間38分。Ullman先生の2時間半はきつい＞＜
    • どうでも良いけどUllman先生ってハイジのおじいさんみたいだ
  • そしてFINAL EXAMが待っている。6/18までに受けなければならない。

Computer Vision：The Fundamentals (Jitendra Malik, UCB) - 4/23開講; 5/25参戦

  • 見てない

来季があれば絶賛参加予定

Natural Language Processing (Dan Jurafsky, Christopher Manning) - TBA

  • 講義ビデオは"Preview"リンクから全部見られるので、先に見ておこうかなと
  • Week1（正規表現、tokenize, stemming, 編集距離）のビデオは全部見た
    • Manning先生（FSNLPでお世話になっております）のオーストラリア訛りに好感
    • すごく今さらだけど Levenshtein距離のDPが腑に落ちた
  • Week 2（言語モデル、N-gram）に突入。
  • 来季はよ

今週のCoursera（〜6/2）

Coursera

（see also:先週のCoursera）

今週からどのビデオを見たか、どの演習をやったか等をGoogle Spreadsheet上でチェックしながら進めています。このシートを見ればまあどの辺りにいるのか分かりますが

という声もありますし時々の振り返りも重要かと思うので今週のCourseraメモ行ってみます。

参加しているクラス

Machine Learning (Andrew Ng, Stanford) - 4/23開講。現在第7週

  • 機械学習システムの設計の指針
    • 闇雲にデータを大量に集めれば良いってものでもない
      • 「そのデータがあれば専門家は自信をもってクラス分類できるのか？」
      • 「大量に訓練データを用意できるか？」
    • さくっと（汚くても良いので）１発目の実装を。そして学習曲線取ってみてbias/varianceを見る。分布の偏ったクラス分類（99%:1%みたいな）にはprecision/recallとF1スコアが効く。
  • そして期待のサポートベクタマシン（SVM）
    • 「最大マージン分類器」
    • 原理はPRML（下巻の最初）でもちゃんと説明されてるわけだが
    • カーネルの説明。超わかりやすかった。cf.
    • Ng先生のビデオ見て色々と腑に落ちた。分かりやすい。というか、すっと分かるための取っ掛かりの与え方がうまい。
    • 最後に説明してる全ての訓練データ点にカーネル適用して素性として使うのってNadaraya-Watson modelか
  • Programming Assignment
    • 引き続きOctaveです
    • SVM実装させられるのかな？とかみんな期待しますよね。
    • そこまではしません＞＜
    • ガウシアンカーネル関数くらいは実装しますけど
    • あと、最適なパラメータの選択もさせられますけど
    • 分類境界がヴィジュアライズされるのは気持ちいいです
  • これで、講義ビデオと課題の消化がやっと追いついた

Compilers (Alex Aiken, Stanford) - 4/23開講; 5/10参戦。現在第6週

  • Midterm（中間試験）がある
    • Week 4までの講義の内容から
    • といってもこれまでの講義ビデオの半分ぐらいしかまだ消化できてない
    • Midtermの期限 (5/28月 15:59:00 JST) までに試験範囲の未消化ビデオを見て、Midtermも受けないと
    • やばい時間足りない
    • 1.25〜1.5倍速再生乱用。と言っても英語字幕付けれるしメモ取りたいところで止めれるし分からないところは巻き戻せるから無問題
    • handleとかviable prefixとかの辺りってなんか説明が曖昧で難儀。purple dragon bookでもその辺りで右往左往（right-/leftmost derivationとかright-/left sentencial formとか的な）した記憶
    • 試験範囲のQuizとDeduceItもやっとこう（同じ問題出るかもしれないし）
  • 15:59まであと残り1時間半… というところでMidtermを受けた。
    • 2時間半、といってもいつもの復習Quizと同じ形式なので正味20分もあれば解ける。但しいつもと違うのは一回しか受けられないこと。
    • 投了。
    • 採点すぐに出た。7.4 / 9 …なにそれそんなに間違ってるのかorz
      • Q3. ルールが6つあって文字列があってどのルールでacceptされるかという問題。全ルールが定義されていると思ってなかった（まあ問題文で言ってないし）ので「この文字列をacceptするにはどれとどれを使えば良いか」問題を解いてた。(-0.428571)
      • Q5.「This language produces exactly 2 strings of length 2.」をNOにした。確かに長さ2の文字列は2つacceptするが、他にもacceptするものがあるから。問題文がambiguous (-0.1666)
      • 講義で言ってたままの実装の再帰降下パーサでproductionを数えるとちゃんと奥までバックトラックできてないので違う数字を返す (-1.0)
    • あまり良い問題セットとは思えない
    • まあいい。先へ進もう
  • Programming Assignment 3に着手
    • COOL言語の型チェックとかSemantic analysisとか。
    • 型チェックはASTに対し何をする作業なのか講義ビデオで説明されているものの、用意されているスタブコードを読み解いて自分がやるべき差分を見つけ出すのがちょっとハードル高いような。
      • まあこれはハッキング課題なのだなと思って進めた

    • SELF_TYPEの仕様が（仕様書にちゃんと書いてあるっちゃあるけど）厄介で、最初に書き進めていた型チェッカでは74項目のチェックのうち1つだけどうしても通らないものがあって、1箇所採点サンプルしか通らないチート的コードを書いて最初の74点。
    • ちなみにCompilersクラスのプログラミング課題の採点は、（VirtualBox上で）プロジェクトをビルドして、74本のテストを行う採点スクリプト(perl)を走らせて、スクリプトが吐き出したハッシュ文字列をCourseraのwebフォームに貼り付けることで採点される仕組み。COOL言語で記述されたテストコードと、それに対する模範解答は与えられている。（この模範解答なしにはそもそもどういう文言のエラーメッセージを吐かないと通らないのか分からない。いわばこれらが仕様書である）
    • しかし、これでは気持ち悪い。コード提出求められたら（先生が）泣く。
    • SELF_TYPE問題に対処するため、型を保持するデータ構造にちょっと手を加えて途中から（40点ぐらいから）やり直した。今度はチートなしで74点行けた。採点スクリプトが吐くハッシュコードはチート込み74点も正攻法の74点も同じだった。
    • というわけで今回は期限2週間前に完了 (74.00/74)

Automata (Jeffrey Ullman, Stanford) - 4/23開講。全6週。

  • Programming Assignment を覗いてみたら簡単そうだったので、締め切り6/12だけど先に手を付けた。実装言語はPython/Javaで、もちろんPythonを選択。
    • 1つ目は正規言語のε-NFA化。先日来Schemeで書いてた物のごくごく一部にすぎない。こんなのでいいの？ってくらい簡単な課題。（てかCompilersの課題がでかすぎる）
    • 2つ目はCYKアルゴリズムの実装。

  • 締め切りの迫った復習クイズを消化。消化に必要なところからビデオを消化。（まだ１本20分ぐらいの未消化ビデオが５本ぐらいある）
    • Ullman先生のビデオって１本１本が長めだし先生の英語の抑揚が苦手だしちょっと億劫

    • 1.25倍速で聴いて理解できてるのかというと怪しい。Ullman先生の説明は帰納法的な証明が多いのと、ドラゴンブック的書物で背景的な知識*1がある程度あるから類推でなんとなく分かった気になってるけど、自分の英語解釈的には非常に怪しくて、1倍速で聴いても0.75倍速に落としても、クローズドキャプチャ＋穴埋めディクテーションしてテキストで読んでも何が言いたいのかわからなくて、そのちょっと後に描かれた図を頼りに当てはめていくと説明の意味が分かる、という事がしばしば。
    • ていうかクローズドキャプチャのタイミングが合ってないので付けると意味不明
  • 6/11〜18にFinal Examがあるのでそれまでに全部見ないと＞＜

Computer Vision：The Fundamentals (Jitendra Malik, UCB) - 4/23開講; 5/25参戦

  • 提出期限のある課題が（今のところ）ない、という事もあってまだIntroしか見てないまま

*1:Ullman先生の英語、も含め

Coursera消化シート

Coursera
  • 講義ビデオの視聴状況
  • 復習クイズの回答状況
  • プログラミング演習の提出状況

をGoogleスプレッドシートにまとめた → https://docs.google.com/spreadsheet/ccc?key=0AheVdNXZmJ18dHktcm9mbU5HNXZGcnJvTkZPMUxqWFE

// はてブロにスプレッドシートをembedする方法があったら誰か教えて