2009年度 情報科学演習Ⅲ 今井研課題説明会 ２００９年４月１０日 TexPoint fonts used in EMF.

Presentation on theme: "2009年度 情報科学演習Ⅲ 今井研課題説明会 ２００９年４月１０日 TexPoint fonts used in EMF."— Presentation transcript:

1 2009年度 情報科学演習Ⅲ 今井研課題説明会 ２００９年４月１０日 TexPoint fonts used in EMF.
Read the TexPoint manual before you delete this box.: A

2 今井研究室の研究テーマ アルゴリズム 今井研究室の研究テーマは情報科学の基礎である「アルゴリズム」そのものです。一口にアルゴリズムと言っても、さまざまな側面からの研究があります。

3 今井研究室の研究テーマ アルゴリズム 基礎理論 計算量 計算量 計算量 最適化
アルゴリズムの速さの解析や、アルゴリズムを適用する問題そのものの解析を行う、計算量、最適化といった側面からの研究や

4 今井研究室の研究テーマ 現実社会へ の応用 アルゴリズム 基礎理論 計算量 計算量 暗号理論 計算量 計算量 計算量 計算量 生体認証
ゲーム理論 計算量 計算量 計算量 計算量 生体認証 交通量解析 　　　現実社会へ 　　　　　の応用 計算量 最適化 アルゴリズム 基礎理論 結果や考え方を現実社会での問題に応用するという側面からの研究、

5 今井研究室の研究テーマ 現実社会へ の応用 アルゴリズム 基礎理論 新しい計算の 枠組み 計算量 計算量 暗号理論 計算量 計算量 計算量
ゲーム理論 計算量 計算量 計算量 計算量 生体認証 交通量解析 　　　現実社会へ 　　　　　の応用 計算量 最適化 アルゴリズム 基礎理論 新しい計算の 　　　枠組み 計算量 量子 またこれらの問題を、これまでの計算の枠組みとは異なる量子計算の枠組みで考えるという研究

6 今井研究室の研究テーマ 現実社会へ の応用 アルゴリズム 基礎理論 新しい計算の 枠組み 数理構造そのもの 計算量 計算量 暗号理論 計算量
ゲーム理論 計算量 計算量 計算量 計算量 生体認証 交通量解析 　　　現実社会へ 　　　　　の応用 計算量 最適化 アルゴリズム 基礎理論 新しい計算の 　　　枠組み 計算量 量子 そしてこれらの研究を支える数理的構造の研究など、今井研究室では基礎から応用、古典から量子まで、幅広い分野に挑戦しています。 計算量 計算量 組合せ論 グラフ理論 計算量 計算量 数理構造そのもの 計算代数 計算幾何

7 博士論文(1) 計算幾何 アレンジメント再構成の組合せ論的複雑度評価（青木 保一，1993）
リーマン計算幾何：凸包，ボロノイ図とデローネ型三角形分割 （大西 建輔，1998） 特徴多様体上のクラスタリング問題について（稲葉 真理，1999） 整数計画法による三角形分割の最適化（田島 玲，2000） 三角形分割の組合せ論（竹内 史比古，2001） 多面体的複体のシェリング向き付け： シェラビリティー判定と離散最適化の組合せ構造 （森山園子，2006） 有向マトロイドの実現を与える方法および特徴のある有向マトロイド （中山　裕貴，2007） 計算代数 単模およびLawrence型整数計画問題に対する計算代数的解析 （石関 隆幸，2003） 量子計算 計算量的観点における量子計算モデルの計算能力（小林 弘忠，2002） 資源制約下における量子計算モデルの計算能力（ルガル フランソワ，2006） エンタングルメントコストの解析とホレボ容量の計算（下野 寿之，2006） Bell不等式とカット多面体：量子情報科学と組合せ最適化の結合 （伊藤　剛，2007） － 現実世界の設定下で定量的な安全性を初めて保証したデコイ法量子鍵配送 の理論と実験（長谷川 淳，2008） － 量子状態上のボロノイ図とその量子通信路容量の数値的評価への応用 （加藤 公一，2008） 今井研がどのような研究をしてきたところか知ってもらう 7

8 博士論文(2) ゲームツリー探索 AND/OR木探索アルゴリズムDf-pnの提案とその応用（長井 歩，2002）
(美添一樹, 2009) パズル・計算量 　　 －別解問題の計算量解析の統一的手法 (八登崇之, 2009) ゲノム・文字列処理 文書検索と圧縮の統合-接尾辞ソート、ブロックソート法、接尾辞配列- （定兼 邦彦，2000） 部分文字列の性質に基づく計算機援用大規模生物実験設計 （土井 晃一郎，2001） 生物配列情報の比較と検索のための高速なアルゴリズムの研究 （渋谷 哲朗，2002） グラフ理論 Tutte多項式の計算アルゴリズムとその応用（関根 京子，1997） リンクベースのWeb上情報発見手法の新しいフレームワーク （浅野 泰仁，2003） ネットワーク ネットワーク通信において通信品質を保証するアルゴリズム （古賀 久志，2002） 8

9 最近三年間の修士論文 (1/2) 離散数学 最小包含球問題から得られるCube グラフの向きづけ（西鳥羽 二郎，2007）
マトロイドの向き付けの計算解析及び離散幾何における接続関係の問題への応用 　　（松本宜丈, 2009） 半正定値計画法による有向マトロイドの構造解析 （宮田 洋行，2009） 計算幾何 Angular Voronoi Diagram の退化（牟田 秀俊，2008） 計算量理論 　　　　　　Ｌ対Ｐ問題の折り返し対アクセス問題への関連付けとそれらの組み合わせ構造 　　　（上野 賢哉，2007） 暗号理論 Final Round 攻撃対策のなされたAES に対するキャッシュタイミング攻撃 （永岡 悟，2008） 量子攻撃耐性と平均的困難性を備えた生体暗号システム （小島 晃司, 2009)

10 最近三年間の修士論文 (2/2) 量子計算 可解群に対する多項式時間量子アルゴリズム（乾 義文，2007）
二分NAND式木上の量子ウォークアルゴリズムの解析（鈴木 真吾, 2008） 2-Prover 1-Round Game としてのベル不等式における最大量子破れ （高橋 敏明，2008） ２部グラフ上での量子ウォーク探索アルゴリズムのデコヒーレンスの影響の解析 　　　(徳田 優, 2009)

11 演習の内容 研究のための基礎訓練 テーマを自力で見つける能力 もちろん質問は歓迎 文献を探す、調べる 分かりやすい発表
研究について自分で考えることを身につける 研究のための基礎訓練 文献を探す、調べる 分かりやすい発表 テーマを自力で見つける能力 何を研究すればよいのか？ なぜその研究が必要か？ もちろん質問は歓迎 メールor研究室（一度研究室に来て雰囲気を知る こともお勧めします） 今井研セミナーの見学も歓迎 今井研の目指す演習Ⅲの目標とは研究について自分で考えることを見につけてもらうことである。 研究のための基礎訓練として文献を探す、調べる テーマを自力で見つける能力 独りよがりなテーマでは意味がない！ 何を研究すればよいのか？なぜその研究が必要になるかを理解するセンスを見につけてもらうことが目標である。 もちろん質問は歓迎、メールを送るか研究室に来てもらえれば研究室の先輩が応対してくれます 今井研セミナーへの見学も歓迎しています

12 日程 １週目：テーマ設定 ２週目：中間発表 ３週目：中間発表 ４週目：最終発表 学期末：真の最終発表（任意）
毎週水曜日14：00から236にて 都合が悪い場合はflexibleに対応します １週目：テーマ設定 ２週目：中間発表 ３週目：中間発表 ４週目：最終発表 演習の日程ですが 毎週水曜日１時から２１４教室に行います。 都合が悪い場合もflexibleに対応します。 １週目はテーマを設定してもらい、 ２３４週目では研究室のメンバーの前で発表をしてもらいます。 ４週目が最終発表となります。 前もってセミナー担当の自分にメールしてもらえばいきなり１週目からの発表ができます 学期末：真の最終発表（任意）

13 演習III研究テーマ 計算代数・算術計算 暗号理論 離散数学・計算幾何 ゲーム木探索 量子情報科学 この他希望があれば 対応します
この他希望があれば　　対応します 質問はメールまたは研究室(311,314)まで

14 算術計算・計算代数 Vorapong (M2), 宮田 (D1)

15 算術計算 関数や算術を高速化する分野 高速化したいもの 初等関数 足し算、引き算、掛け算、割り算 省エネルギー ,ケイ素の節約
　省エネルギー ,ケイ素の節約 　有限体上の計算とその暗号理論への応用 数学関数  Bessel 関数(電磁波, 熱伝導, … ) 高精度計算  正確な計算 Picture Courtesy by upload.wikimedia.org/wikipedia,

16 Hardware Implementation
どうやって高速化するか 例 :桁集合の拡張 普通は2進表現を使って、数を格納する。  di2i, di 2 {0,1} ただし、他の表現を使ったら  dibi, di 2 DS ひく時間　がO(n) から O(1)　まで改善できる かける時間　半分になる … Hardware Implementation Number Theory Computer Algorithm

17 計算代数 計算機上で代数的な計算を行う方法に関する研究 例： 因数分解、多項式の方程式系の求解、 イデアル所属問題など 因数分解
例：　因数分解、多項式の方程式系の求解、 　　　イデアル所属問題など 因数分解 方程式系の求解

18 方程式系に解があるか厳密に判定する手法 グレブナ基底 不等式系 方程式系 線形 ( ) 簡単 Simplex法 Gauss消去法 非線形
(実数体上) (代数的閉体上) 線形 ・・・ ・・・ ( ) 簡単 Simplex法 Gauss消去法 [‘63 Dantzig] 講義でも習ったはず 非線形 ・・・ ・・・ ( 　　) 非常に非効率で使い物にならない 難しい グレブナ基底 Cylindrical Algebraic Decomposition　[‘75 Collins] [’85 Buchberger]

19 目指すものの例 グレブナ基底の研究 不等号を含むような多項式系を(ある程度)効率的に扱う手法の確立 数学の研究支援 期待される応用
等式系に関する既存研究： 不等式系に関するこれからの研究： グレブナ基底の研究 不等号を含むような多項式系を(ある程度)効率的に扱う手法の確立 数値計算的手法の導入など.. 数学の研究支援 期待される応用 ・座標環上での計算 ・有向マトロイドの実現不可能性判定 ・加群の極小自由分解 ・semi-algebraic setの連結性判定 ・準素イデアル分解 ・・・ ・・・ 他分野への応用 その他の全く新しい展開？？ ・整数計画法の新解法　　　　　　 ・マルコフ基底を求める初めてのアルゴリズム(統計学) ・・・

20 演習3の進め方について ・最終週あたりで、その発展を考察 ・さらに改良できないか ・まず、論文の購読 ・・・・
　　テーマ例：不等式系の扱い方、対称性を生かした高速化など ・最終週あたりで、その発展を考察 　 ・さらに改良できないか 　　・ 別の問題にその考え方が使えないか 　　・他の手法と組み合わせられないか ・・・・

21 暗号理論 Vorapong (M2)

22 暗号理論 安全のため数学やアルゴリズム ALICE BOB M 暗号理論のレイヤ 実装技術 ALICE は BOBにメッセージを送る
BOB は送信者が ALICEかどうか調べたい ALICE は他の人に送ったメッセージを読まれたくない 誰か何万個のメッセージがBOBに送ってもまだ大丈夫 … まだたくさんある 暗号プロトコル 算術計算 数学

23 研究に必要なもの 抽象代数の基礎 アルゴリズム,計算量理論の基礎 線型代数の基礎 暗号理論の基礎知識 (RSA, … ) 群、環、体、。。。
楕円曲線暗号・超楕円曲線暗号, … アルゴリズム,計算量理論の基礎 ハッシュ関数,デジタル署名 , … 線型代数の基礎 格子暗号, … 暗号理論の基礎知識　(RSA, … ) Picture Courtesy by ocw.mit.edu, math.stanford.edu

24 ゲーム木探索 美添 (研究員)

25 モンテカルロ法＝モンテカルロ木探索 4月8日付 朝日新聞 夕刊

26 ゲームAIの革命 MCTS Alpha-beta探索を超えるインパクト Monte Carlo Tree Search 囲碁だけが弱かった
古典的な囲碁プログラム (古典=2005年以前) 近代的なプログラム (近代的=2006年以後) 19路盤 2級から3級 19路盤 2段以上 9路盤 2級から3級 9路盤 アマ高段並 囲碁だけが弱かった 9路盤では既に複数のプログラムがプロに勝利した チェス、将棋、ポーカーなどはコンピュータが非常に強い [2006 Rémi Coulom] 2006年5月に発表されたMCTSによって状況が一変 19路盤では、公開対局で、7子のハンデでプロに勝利している ・CrazyStone対 青葉かおり ・MoGo 対 周俊勲 今までのアルゴリズムは、評価関数が無いとお手上げだった

27 原始モンテカルロ囲碁 [1993 Brügmann][2000ごろBouzy, Cazenaveら]
弱いけど早いプレイヤーにたくさん終局図を作らせる (40級のプレイヤーを1000万人くらい集める?) playout 多数決で良い手を決める 黒の手番 白の手番 黒勝ちの プレイアウト 白勝ちの プレイアウト 凡例 …白勝ち？ 当然、あまり強くない ・・・でも意外と強い (9路盤だと10級くらい?)

28 MCTS (Monte Carlo Tree Search) の成立
多数決じゃひどいのでちょっと工夫する 5月 CrazyStone [2006 Rémi Coulom] 2006Computer Olympiad 囲碁9路盤部門で優勝 重要な概念 をほぼ網羅 勝率最大化 リードしているときは安全に、負けているときは冒険をする 「有望な手」に集中 UCT Algorithm [2006 Kocsis & Szepesvári] 「有望な手」の理論的な基準 9月 MoGo [2006 Gelly, Wang, Munos & Teytaud] UCTを用いた初のプログラム 19路盤でアマ初段程度に到達 11月 「有望な手」を深く読む 全部2006年の出来事！

29 UCT Algorithm MCTSの発展 理論的背景 機械学習によるplayoutの強化 並列化 他の2人ゲーム 一人ゲーム 多人数ゲーム
40級? 20級? Multi Armed Bandit問題 他の2人ゲーム Lines of Action, Hex, Amazons, 将棋 並列化 与えられた枚数のコインで、 できるだけ多くの報酬を 得るための戦略を考えよ 一人ゲーム SameGame さめがめ 多人数ゲーム ハーツ UCB1という戦略 信頼区間上限を基準とする (Upper Confidence Bound) [2002 Auer, Cesa-Bianchi & Fischer] バイオメトリクス セキュリティ評価

30 今なら掘り放題！ まだ発表されて3年未満！ MCTSを実装しよう ゲームでも 理論的な貢献をしてみよう 並列化しよう なんでもいいから
機械学習のプロ、 探索のプロが多数参入 他の分野の人はまだ少ない MCTSを実装しよう ゲームでも それ以外でも 理論的な貢献をしてみよう 並列化しよう なんでもいいから やってみよう それができるテーマです

31 Min-Hsiu (研究員)，長谷川 (助教)
量子情報科学 Min-Hsiu (研究員)，長谷川 (助教)

32 量子とは？ ビット(0 or 1)の世界 量子ビット( )の世界 010001101001 リソースの違い 1
量子ビット( )の世界 イメージ：電子スピン リソースの違い “0”と”1”が確率1/2ずつで存在 1 エンタングルメント（量子相関） （情報処理能力の向上） 操作 変化なし 変化あり 相関なし 相関あり

33 量子を使うと何ができるの？ breakthrough exponential gap! 多項式時間で解ける！ 安全でない！ 現代の計算機
量子計算機 問題点 量子効果を積極的に利用する 現代の計算機では解けない問題を解く！ breakthrough 解決策 量子効果よる高速化の障害！！ コンピュータの高速化の限界 素因数分解アルゴリズム exponential gap! 最良の古典アルゴリズム 準指数時間アルゴリズム Shorのアルゴリズム [Shor 94] 多項式時間で解ける！ 暗号理論 RSA暗号 素因数分解の難しさに 安全性をおいている （計算量理論的安全性） BB84プロトコル[BB 84] 量子力学の不完全性定理 に安全性をおいている (情報理論的安全性) 安全でない！

34 量子情報科学の観点から どのくらい情報を送れるか？ 古典エントロピー （Shannon entropy） 雑音ありの通信路
量子効果（エンタングルメント） によって情報量は増えるのか？ 量子操作と古典・量子通信路 容量との関係性は？ 量子の情報処理 能力が知りたい 1-p p p 1 1 確率 1-p 量子エントロピー （von Neumann entropy）

35 演習3の課題 シャノンの古典情報理論、量子力学(エンタングルメント、非局所性など)の初歩を学び、量子情報理論の論文購読を行い、その発展を自分で考えて新しい評価、プロトコルを作成。 エンタングルメントを用いた/用いない量子通信路における古典/量子情報伝達 量子通信路における秘密鍵・エンタングルメントの生成 新しい情報科学分野へようこそ

36 夫(M2), 奥田(M2), 宮田(D1), 田沼(D1), 森山(特任講師)
離散数学・計算幾何 夫(M2), 奥田(M2), 宮田(D1), 田沼(D1), 森山(特任講師)

37 抽象性が高く、基礎であるがゆえに幅広い分野の研究と関連
離散数学って、何をするものなの 目的：本質的に持つ構造をとらえること 対象: ばらばらなものたちの組み合わせや、関係性 x y z 紙と鉛筆もあり、計算機は手段としても、応用のためにも非常に重要！ 計算幾何 計算量理論 最適化 ゲーム理論 抽象性が高く、基礎であるがゆえに幅広い分野の研究と関連

38 離散数学の問題の一例 グラフ上の最小重み二部マッチング と のマッチングで、ペアになったものの 間の距離の合計が最小になるもの
工学的な応用上でも、重要な問題

39 一般のグラフにおけるアルゴリズム 離散数学講義でやったように、普通にやればO(n3) timeできる アルゴリズムの大まかな流れ
下の1, 2をO(n)回繰り返すというのを、O(n)回 注目している青い点からもっとも「近い」赤い点を探す – O(n) time 探し当てた点への距離の正負に応じて、マッチングや点の重みを改善する ここがミソ！

40 もっと、規則正しいようなグラフ上では？？
直交格子グラフ 幾何的な性質を使うと、1.がO(1)でわかるようなデータ構造で、 点の追加・削除がO((log n)3) timeでできるようなものを作れる トータルで、O(n2(log n)3) timeになる ← O((log n)n-3)の高速化！ aからbまでの最短距離 = aからcまでの最短距離 　 + cからbまでの最短距離 他のグラフについても、同じようにできないか 私がいまやっていること P. M. Vaidya, SIAM J. Comput., 18, (1989) a c L1距離のもつ、いい構造を明らかにして、利用している b

41 演習IIIでやること 演習3の進め方 何はともあれ
論文を購読して発表してもらいます。 (英語、英語、英語・・・・と大変でしょうが、残念ながら卒論も英語なので。) 最終週辺りで余力があればプロジェクトを自分で決めて簡単に研究してみましょう。 (せっかく今井研の演習３にきてもらうので。いい経験に なりますよ！！もしかしたら卒論のテーマになるかも？) 具体的に、どういうことをしている論文を読むの？ 計算機を使ってバリバリ数え上げるのも、紙と鉛筆で理論的に攻めるのも、どっちもアリ 前のスライドまではアルゴリズムの設計の話をしていたけど、他もアリ 最適化問題に挑戦 もっと、数学的な幾何構造に計算機を使ってアタック グラフ理論 Appendix : 今井研の宣伝(夫の独断) 部屋が綺麗！！　先輩方が親切だ！！　突発的な飲み会が多い！！ 学年の垣根がなく仲が良い！！　なにより先生が面白く、情熱的で素敵だ！！ (もう今井研にくる以外の選択肢はないですね。)