naoya_t@hatenablog

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

トップ > Coursera

Courseraレポート（〜9/3）

Coursera 量子力学&量子計算 Algorithms

前回までのあらすじ（〜8/26）

現在、量子力学＆量子計算のクラス（Umesh Vazirani先生）と、8/26に参戦したアルゴリズムのクラス（Robert Sedgewick先生＋Kevin Wayne先生）を受講中。量子計算の方がメイン。

Quantum Mechanics and Quantum Computation (Umesh Vazirani, UCB) - 7/17開講; 現在7週目

  • Week 6
    • 量子回路: n量子ビット系, ユニバーサルな量子ゲート, 可逆な計算
    • 初期の量子アルゴリズム: フーリエサンプリング, Simonのアルゴリズム、二重スリット実験

講義ビデオをひと通り見て、ぼんやりした理解（ノートは取ってるけど自分が書いたノートが何言ってるのかさっぱり分からん）のままAssignment 6を受けた。１回目は得点が８割に満たず。

  • 解けない問題から、自分が何が分かっていないのかが見えてきたのでその辺りを何とかするため講義ビデオを見直し。アダマールゲートが何故フーリエ変換的な役割を果たすのか、ちくちく手計算してみて腑に落ちる。
  • 問題文が曖昧な箇所があって困ったのだけれどその辺りは4択問題をbrute forceで解いた結果から問題の意図を推測してくれている先人の人柱のお陰で何とかなった。お陰様で2度目で満点。2度目なので10%減点されて90点相当。通算58.7/60なう。

Week 7では量子フーリエ変換とShorのアルゴリズムに入る。その前にWeek 6の後半をおさらいしておかなければ恐らくわけわかめだろう。頑張る。

Algorithms, Part I (Robert Sedgewick & Kevin Wayne, Princeton) - 8/12開講; 8/26参戦; 現在4週目

アルゴリズムのクラスは2週+α遅れ参戦のせいでAssignmentの締切りがギリギリ、ということもあり（内容を知ってる気になっているという事もあり）講義ビデオを視聴する時間がフルで取れない。
そこで、講義ビデオを見る前にExercisesの問題を先に開き、解けない問題があった場合にビデオを見る、という戦略でやってみることにした。（問題を解くのに）必要な情報をつまみ食いする感じ。講義の中で定義されている内容を参照している場合は見るしかないが。

Exercisesについてはそれで割と何とかなるのだけれど、Programming Assignments の方はそうは行かない。講義で説明していない（用意されているjarに入ってない）クラスは使えない、という縛りのせいもあるけれど、講義ビデオで実装を紹介しているのをコピペすれば済む箇所もあるので、講義ビデオを早送りで見るケースが多い。（Sedgewick先生の講義は大抵x1.75で見ている。これは先生の英語が聴きやすいからこそできる事）

Programming Assignmentsはメモリや時間、特定メソッドの呼び出し回数などに制限がつけられていて、簡単には満点が取れないような設計になっていて面白い。（TopCoderで言ったらDiv I Medium問題を解いてるような感じ。Javaだけど）

Javaでプログラム書くのがちょっと面白くなってきた。SRMのDiv2過去問あたりJavaで解いてみようかな。

Courseraレポート（〜8/26）

Coursera 量子力学&量子計算

前回までのあらすじ（〜8/9）

現在、量子力学＆量子計算のクラスを受講中。
Sedgewick先生のAlgorithmのクラスに手を出すか悩む。最初の課題が今日（8/26）の12:59まで。→手を出した

Quantum Mechanics and Quantum Computation (Umesh Vazirani, UCB) - 7/17開講; 現在6週目

5週目のAssignmentまで消化。（5週目は締め切りギリギリ…）
問題がだんだん難しくなってる印象があるけれど、問題文をコピペして負符号がU+2212 (MINUS SIGN)になってたのが☓になったりとか、自己共役の上の線（複素共役）の有無を確認してなかったりした以外はとりあえず全部合ってたので何とかなっている（通算49.7/50）。このまま頑張って修了証（通算8割+）を目指したい。

Week 6からいよいよ量子計算に入る。楽しみ。

    • 量子回路（n量子ビット系, 量子ゲート, 可逆計算）
    • 初期の量子アルゴリズム（フーリエサンプリング, Simonのアルゴリズム, 二重スリット実験）

Algorithms, Part I (Robert Sedgewick & Kevin Wayne, Princeton) - 8/12開講; 現在2週目

  • 1週目の課題締め切り（8/26 12:59JST）に駆け込み参加中【間に合った！】
  • Union Find
    • 講義ビデオ見た
    • Exercise 完了
    • Programming Assignment (Percolation) 完了。Java。
      • NxNセルを１つずつランダムに開けていって、一番上の列のどれかと一番下の列のどれかがUnion Find的に繋がるかどうかの判定。percolation判定は一番上の列すべてに繋がるvirtualなセルと、一番下の列すべてに繋がるvirtualなセルを用意すれば楽ちんなんだけど、個別のセルが上から繋がっているかをチェックできるかどうかも見られていて、この方法だと下の方のセルで上からは繋がってないのに下のvirtualなセル経由で繋がってる判定をされるもの(backwash)があって課題的に減点を食らう。実行時間やunion-findの接続判定の呼び出し回数にもペナルティがあって、簡単には満点取らせない問題になっている。union-findは用意されているものしか使えない。まだ習ってないデータ構造（HashMapのことw）は使えない。試行錯誤の末、思いついたらなーんだそんな事かって感じの解法で満点クリア。（ネタバレはできないのでご想像にお任せします）
  • Analysis of Algorithm
    • 講義ビデオ途中（問題を解くのに必要な分だけは見た）
    • Exercise 完了

Machine Learning修了証頂きました + 8/20開講のお知らせ

Coursera

CourseraのMachine Learningのクラス（Andrew Ng先生; Stanford）が、また今日8/20から開講されます。所要10週間です。

PRML読みの皆さん、何度時間遡行を繰り返してもワルプルムルの夜が倒せない皆さん、機械学習に関心のある皆さんetc. あとcoursera未体験の人も、ぜひ参加してみてください！
講義ビデオは英語です（英語字幕可; スピード調整可）。プログラミング演習の言語はOctaveです。

参加を決めるにあたって参考になるかもしれない記事とか：

所定のカリキュラムをこなすと
f:id:n4_t:20120823105656j:plain
こんな修了証（PDF）がもらえます。（↑今日届きました。これで3枚目）
ps. このマスコットキャラクターのTシャツが欲しい、的な書き込みがフォーラムにあったけどその話どうなったんだろう…

Courseraレポート（〜8/9）

Coursera 量子力学&量子計算

前回までのあらすじ

量子力学＆量子計算のクラスのみ受講中。

Quantum Mechanics and Quantum Computation (Umesh Vazirani, UCB) - 7/17開講; 現在4週目

3週目のAssignmentまで消化（締め切りまで余裕がないのでもうちょっとペースを上げた方がよさげ）
式展開（ブラケット記法とか、ヒルベルト空間とかテンソル積とか）にも慣れてきた。

量子力学のクラスは評価基準が厳しめ（再試行のペナルティが10％/回, 通算で8割取らないと修了証が出ない）。今のところ何とかなってる（28+/30）けど頑張らないと。

Compilersの修了証を頂きました

Coursera

おととい一度発行されたのですが、配点の25%分に充てられるはずのFinal examの点数が反映されていなかったため再発行されました。
DeduceIt（1段1段演繹を行うパズルのようなもの）の得点がボーナス的に追加されるため100点を超えています。
f:id:n4_t:20120728103133j:plain
Programming Assignmentは任意で、やってもやらなくても必要点の70%に達していれば修了証がもらえるのですが、Programming Assignmentをやって必要点が取れると

Furthermore, a full compiler including lexical analysis, parsing, type checking, and code generation for a real machine, was satisfactorily completed.

の一文が修了証に加わります。（上の画像の最初のパラグラフ参照）

というわけでこれで2枚目ゲットです。神龍を呼び出せるまであと5枚集めないと…

Courseraの7月期が始まった（〜7/22）

Coursera 量子力学&量子計算

Courseraに12の大学が新たに加わるというニュース。Courseraで学べる内容にも幅が出てきて、夏以降の楽しみが増えた。

とりあえず、École Polytechnique Fédérale de Lausanne (スイス連邦工科大学ローザンヌ校, EPFL) の Introduction à la Programmation Objet のクラスは（ぱっと見たところ）唯一フランス語で開講されるので覗いてみたい。Javaで学ぶオブジェクト指向プログラミング、みたいな（正直どうでもいい）クラスなのだけれど。EPFLでは他にデジタル信号処理とか、Scalaで学ぶ関数型プログラミングとか開講予定で楽しそう。

今週のCoursera

さて。量子力学と量子計算のクラスが7/17から始まったので受講を開始。

Quantum Mechanics and Quantum Computation (Umesh Vazirani, UCB) - 7/17開講; 第1週

Anyone who is not shocked by quantum mechanics has not understood it.

-- Niels Bohr

  • Youngの二重スリット実験の話
    • 弾丸の場合（干渉縞なし）／波の場合（干渉縞あり）
    • 光子を飛ばしたら？波の性質。1"粒"ずつ飛ばしても干渉縞パターンが出る不思議

射出された光子1粒が2つのスリットを半分ずつ(?)通って後で合流して干渉する？とか考えてみたけど、両スリットからの距離に開きがある地点xで干渉するのが納得いかない。それにもし「1粒」ならどちらのスリットも通り抜けられずスクリーンに到達しない確率がかなり高い気がする。
とりあえず、干渉縞と同じ確率分布で着地点がばらけるところまで理解。

  • 重ね合わせ原理
    • |ψ⟩=α0|0⟩ + α1|1⟩　←"standard basis"
      • α_i は "probability amplitude" と呼ばれる複素数
      • |0⟩ が観測される確率は |α0|^2, |1⟩が観測される確率は |α1|^2
      • 但し |0⟩ を観測すると|ψ⟩=|0⟩に、|1⟩を観測すると|ψ⟩=|1⟩になってしまう点に注意
      • |α0|^2 + |α1|^2 = 1
    • |+⟩ = 1/√2(|0⟩ + |1⟩ ), |-⟩ = 1/√2(|0⟩ - |1⟩ ) な "sign basis" を定義して |ψ⟩=β0|+⟩ + β1|-⟩ と表せる
      • ここで |+⟩ を観測すると|ψ⟩=|+⟩に、|-⟩を観測すると|ψ⟩=|-⟩になる
  • 不確定性原理
    • 素粒子の位置と速度の両方を同時に正確に知ることはできない
    • |0⟩ |1⟩ と |+⟩ |-⟩ を同時に観測しても一定以上のspreadが出来てしまう話（と計算）があったがそれは同じ事を言っているのか？

D

Course Note (PDF) がちゃんとしてて（講義ビデオより詳しいというか色々端折ってないというか）良かった。

Assignment
  • テキストフィールドに入れる数字を1つ書き間違えてドジっ子ポイント-10点get (50/60)
  • すぐに気づいたので再挑戦。このクラスでは（10%☓試行回数）のペナルティがあるので、満点でも(1.0 - 0.1t)*(60/60)=54/60相当の評価になった。
  • 今まで受けたクラスではペナルティ無しでほぼ無限に試行が可能だったのだけれど、ペナルティ有りの方が評価としては正当な気がする。ただ、全問ちゃんと分かるまで試行錯誤する、というのとは逆向きのインセンティブ。
Optional Assignment
  • 「qubitのstandard basisとsign basisの間の不確定性関係についてより定性的に理解することを目的とした問題」
    • 成績には反映されないが見てみよう
    • 計算に終始しているので全部解けてしまうのだけれど、|0⟩, |1⟩ が基底状態, 励起状態に対応してるとしたら |+⟩, |-⟩ は何に対応しているのだろう、という謎が脳内を駆け巡ったままですっきりしない。
驚きとか疑問とか
  • 量子は軌跡（経路）をもたない：（A地点を出発し、後にB地点で観測されたとしか言えない）
    • これは意外にもすんなり受け入れられた
    • 存在確率、というか自乗すると存在確率になる複素数が空間にうねうね満ち溢れているイメージとその積分
  • 光が空間を最短経路で進む（フェルマーの原理）とか屈折の法則（ホイヘンスの原理、スネルの法則）とかも解釈しなおすべきなのか（しなおすと言ってもラグランジアンの停留点とかその程度の漠然としたイメージしか持ってないので上書きするなら今のうち）
  • 波とか粒子とか言うけど自分が思ってるような波や粒子のイメージで良いのだろうか。
    • "波束"というのとどう違うんだろう。
  • 光子"1粒"ってどうやって出すんだろう。
    • 電子のほうが（ラザフォードの原子模型のせいで）"1粒"感があるけど電子雲として考えた方が（ベイズ的な何かを学んだ後の）今ではしっくりくる。

今週のCoursera（〜7/9; 4月期終了）

Coursera

Compilersの最終試験に間に合うように講義ビデオを頑張って消化。

そしてMachine Learningの残り２週分を消化。

というわけで4月期の3本を無事終了。

7月からのクラスも幾つか取ろうと思うのだけれど、3本*1同時進行は結構ハードだったので（分野にもよるけど）2本かな。とりあえず量子力学と量子計算のクラスは確定。

参加しているクラス

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

  • (Week 10) XVII. Large Scale Machine Learning
    • バッチ学習、オンライン学習、確率的勾配降下法
    • Map & Reduceとか並列処理とか
    • Review Questions. 締切まで時間あまりない
  • (Week 10) XVIII. Application Example - Photo OCR
    • 画像に含まれる文字列（看板の文字とか）の読み取りとか、歩行者の検出とか
    • Ceiling Analysisで、どのモジュールにまだ伸び代があるかを分析
    • Review Questions. 締切ぎりぎりで焦った
  • (Week 10) XIX. Course Summary
    • 5分弱のビデオ。この10週間で習ってきた事のまとめと、受講御礼
    • 皆さんもうMLのエキスパートなので、習ったことを生かしてあなたの暮らしが改善されるように、あと他のみんなの暮らしも改善してくれるといいな的な
    • Ng先生もCourseraのコースは楽しんでやってるような気がする

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

  • (Week 9後半) Garbage Collection
    • Mark&sweepにおけるpointer reversalの仕組みを反芻してた。GCする時ってそもそもTODOリスト用にメモリがアロケートできない為の工夫。
  • (Week 10) Java
    • COOLとの差分を紹介する形でJavaについて講義。
    • 概ね知ってるはずの内容だけれど、コンパイラを実装したばかりのCOOLとの比較によって内側から理解が深まった気がする
  • FINAL EXAM
    • 持ち時間4時間あるけど2時間程度で提出
    • 9.75/10
      • ケアレスミス（✔を消し忘れた）で0.25点引かれていた以外は全部合ってた（のでむしろ驚いた）
  • 全体の96.7%取れてるので修了証書は貰えそう
  • このコースはCOOLコンパイラの実装がchallengingなhackだったので面白かった

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

  • 修了済

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

  • 結局見なかった。コース3本が限界かな。

来季参加確定

Quantum Mechanics and Quantum Computation (Umesh Vazirani, UCB) - 7/17開講

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

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

*1:放棄したComputer Visionも入れるとEnroll4本