アルゴリズムのチカラ～大規模データ処理からAIまで～

九州大学 システム情報科学研究院
准教授 稲永 俊介

自己紹介

出張講演＠佐世保高専

1

自己紹介
氏名：稲永 俊介（いねなが しゅんすけ）
出身：福岡県
現職：九州大学 システム情報科学研究院 准教授
専門：情報科学出張講演＠佐世保高専

2

アルゴリズムとは？

出張講演＠佐世保高専

3

アルゴリズムって何？
 コンピュータ上で行われていることはすべて「計算」である．

 コンピュータ上でいかなる「計算」を行うときも、その計算方法の基礎であるアルゴリズムの設計が重要となる．

出張講演＠佐世保高専

4

アルゴリズムって？
 コンピュータは、四則演算（＋，－，×，÷）などの単純な計算を高速かつ正確に行える

 しかし、複雑な問題を解くための「手順」をコンピュータ自身が編み出すことはできない

 単純な計算を組み合わせて、より複雑な問題を解くための手順のことをアルゴリズムという出張講演＠佐世保高専

5

アルゴリズムの例（その１）
問題：迷路を脱出せよ！
コンピュータは前後左右に動くことはできるが、いつどの方向に行けばいいか知らない
スタートゴール
出張講演＠佐世保高専

6

アルゴリズムの例（その１）
問題：迷路を脱出せよ！
行き止まりになったらどうしたらいいんですかー？
スタート

ゴール
出張講演＠佐世保高専

7

アルゴリズムの例（その１）
問題：迷路を脱出せよ！
壁に右手をついたまま進みなさい
スタート

ゴール
出張講演＠佐世保高専

8

アルゴリズムの例（その１）
問題：迷路を脱出せよ！
いきまーす！
スタート

ゴール
出張講演＠佐世保高専

なぜ迷路を抜けられるのか？
•

迷路を以下の３つのパーツに分割して考える．

入口

出口
出張講演＠佐世保高専

10

なぜ迷路を抜けられるのか？
•

迷路を以下の３つのパーツに分割して考える．
(1) 入口から見て右側の壁に繋がっている部分．
(2) 入口から見て左側の壁に繋がっている部分．
(3) その他の部分．
入口
(1)

(2)

(3)

出口
出張講演＠佐世保高専

11

なぜ迷路を抜けられるのか？
•(1) のみに着目し， (2)(3) は無視する．

•(1) の壁沿いに歩けば，出口に通じるのは明らか．
入口

(2)

右手法
(1)

(3)

出口
出張講演＠佐世保高専

12

アルゴリズムの研究


問題を解く手順を与えれば、コンピュータは人間よりもずっと高速かつ正確に問題を解くことができる

 ただし、問題を解く手順（アルゴリズム）を考案するのは、人間の役割である

 備考：アルゴリズムをコンピュータが理解できるように書いたものがプログラム

出張講演＠佐世保高専

13

アルゴリズムの「良さ」
 同じ問題でも、それを解くためのアルゴリズムは何種類もありえる

解き方は一通りとは限らない 「良い」アルゴリズムの条件
1.

正しく問題を解ける

2.

高速に問題を解ける

出張講演＠佐世保高専

14

アルゴリズムの例（その２）
問題：９つのコインがあり、その中に一つだけ偽物のコインがある。偽物は本物より重い。
天秤を使って、偽物を発見せよ。
12345678

9

天秤を何回使えば偽物を発見できるだろうか？
出張講演＠佐世保高専

15

アルゴリズムの例（その２）
適当に選んだ１個と残りの８個を順番に比べれば、最悪の場合でも８回天秤を使えば偽物が見つかる

2134より少ない回数でできるだろうか…?

6578

１個づつ天秤に乗せていく
出張講演＠佐世保高専

16

アルゴリズムの例（その２）
実は、たったの ２回 で発見できる！
123456789

出張講演＠佐世保高専

17

考え方
コインが３個の場合を考える

123出張講演＠佐世保高専

18

考え方
コインを２個選び、天秤にかける

3a. 1 のほうに傾けば、1 が偽物
b. 2 のほうに傾けば、2 が偽物

12c. 釣り合えば、3 が偽物
出張講演＠佐世保高専

19

考え方
コインが３個のときは、天秤を １回 使えば偽物を発見できる

3a. 1 のほうに傾けば、1 が偽物
b. 2 のほうに傾けば、2 が偽物

12c. 釣り合えば、3 が偽物
出張講演＠佐世保高専

20

考え方
コインが９個のときは、コインが３個のときのやり方を応用する

123456789出張講演＠佐世保高専

21

考え方
コインを３つのグループに分ける

1231456278出張講演＠佐世保高専

9322

考え方
グループを２つ選び、天秤にかける

712314859362

a. 1 のほうに傾いたら、1 の中に偽物がある
b. 2 のほうに傾いたら、2 の中に偽物がある
c. 1 と 2 が釣り合えば、3 の中に偽物がある
出張講演＠佐世保高専

23

考え方
偽物が入ったグループを見つけるのに１回
そのグループから偽物を見つけるのに１回
よって、コインが９個のときの天秤の使用回数は ２回

123467895

出張講演＠佐世保高専

24

コインが 27 個のとき３グループに分け、２つを天秤にかける112310 11 1219 20 2145613 14 1522 23 2478916 17 18225 26 27
3

天秤を１回使って、偽物が入ったグループを発見
あとは、コインが９個の場合と同様の手順⇒ 天秤を ３回 使用すれば偽物を発見できる
出張講演＠佐世保高専

25

天秤の使用回数 (n = 3k のとき)
コインの個数天秤の使用回数

3927
81

1234…

…

nlog3 n

天秤を１回使うと偽物の候補の数が3分の１になる．

log3 n = n を 3 で繰り返し割って1 になる回数
出張講演＠佐世保高専

26

天秤の使用回数（一般の場合）
コインの個数
2~34~910 ~ 27
28 ~ 81

天秤を１回使うと天秤の使用回数
偽物の候補の数が13分の１以下になる．

234…

…

nlog3 nlog3 n = n を 3 で繰り返し割って1 以下になる回数
出張講演＠佐世保高専

27

log3 n vs n - 1
600

天秤の使用回数500400

log_3 nn-1

300
200
1000

圧倒的高速化！
1

100200

300

400

500

コインの個数
出張講演＠佐世保高専

28

実社会のアルゴリズム

出張講演＠佐世保高専

29

実社会で活躍するアルゴリズム
 ウェブ検索 (Google）
 SNS （Facebookの友達候補・広告, twitterのボット）
 商品推薦 (Amazon など)
 航空機の自動操縦
 車の自動運転 (Tesla，ウェイモ)
 株式市場 (アルゴリズム取引)
 コンピュータ将棋・囲碁（ボナンザ，アルファ碁）
 クイズ (ワトソン)
出張講演＠佐世保高専

30

商品推薦
アルゴリズムに Amazon の商品推薦 基づいて商品を推薦

出張講演＠佐世保高専

31

商品推薦

アマゾンが開発した商品推薦アルゴリズムの解説論文

出張講演＠佐世保高専

32

クイズ
•

2011年，IBM が開発した質問応答システム「ワトソン」がアメリカの早押しクイズ番組 Jeopardy!
で人間のクイズチャンピオンと対戦して勝利．

•

オンライン百科事典「ウィキペディア」から学習した知識を利用して，クイズに回答する．

•

一方で，ワトソンが回答を出すプロセスは，人間の思考方法とはかなり異なる．
出張講演＠佐世保高専

33

ワトソンの応用••

医療アドバイス （東大医科研）


がんに関連する約２千万件の論文をワトソンが学習（機械学習）．



６０代の女性患者の白血病が治療が難しい特殊なタイプであるとの分析を１０分で行い，治療法の変更を提案．

人材マッチング （フォーラムエンジニアリング）•

ワトソンが個人の興味，関心，性格などを数値化して把握し，マッチングスコアを算出する．
2016年4月から実際に運用されている．

他にもいろいろ出張講演＠佐世保高専

34

コンピュータ将棋
将棋とは• 9×9のマスの中で，動き方8種類，40枚の駒を動かし，玉を取れば勝ち• 相手の駒を取り，自分の持ち駒として使うことができる• 将棋人口は約1300万人(レジャー白書調べ)• ニコニコ生放送カテゴリ別視聴数ランキングTOP3(羽生善治＆ドワンゴ社長対談)
出張講演＠佐世保高専

35

コンピュータ将棋の歴史
1974年 コンピュータ将棋開発開始？
…
2005年 「激指」がアマ竜王戦ベスト16
2006年 「Bonanza」登場（評価関数に機械学習を導入）
2010年 「あから2010」が清水女流王位（当時）に勝利
2012年 「ボンクラーズ」が米長永世名人（引退棋士）に勝利
2012年 電王戦にてコンピュータが現役プロ棋士チームに勝ち越し
以後コンピュータ将棋の優勢が続く（トップ棋士も敗れる）
出張講演＠佐世保高専

36

機械学習
•

機械学習：人間が自然に行っている学習能力と同様の機能をコンピュータで実現しようとする
技術 (Wikipedia)

知らない問題お手本学習させて・・・
出張講演＠佐世保高専

37

Bonanza 法 [保木，2006]•

コンピュータ将棋に，機械学習技術を取り入れた最初の手法．

•

現在も評価関数作成の基礎となっている，ブレイクスルー的な手法．

•

プロ棋士の棋譜を教師データとして，プロ棋士の手とコンピュータの手が一致するように評価関数を自動調整する手法．

出張講演＠佐世保高専

38評価関数（評価基準）
評価項目：どんな特徴を盤面の点数に反映させるべきか？
値の調整：各特徴に，どのくらいの点数を設定すればよいか？

••

例：駒に点数をつけて評価
金銀桂香

歩馬成銀成桂成香と170 140 100

80605020 185 160

91827865飛角龍

出張講演＠佐世保高専

39

コンピュータ将棋
コンピュータ将棋の代表的な評価項目
••
•
•

駒の価値
玉に対する金の位置
玉の危険度（玉周辺の敵駒の利き）
各駒の働き（利き，敵，味方の駒との位置関係）- 桂馬が跳べるか- 歩が進めるか- ひもがついているか組み合わせを考慮すると数億に及ぶ出張講演＠佐世保高専

40

コンピュータ将棋
コンピュータ将棋の代表的な評価項目
••
•
•

駒の価値
玉に対する金の位置
玉の危険度（玉周辺の敵駒の利き）
各駒の働き（利き，敵，味方の駒との位置関係）- 桂馬が跳べるか全部使うわけにはいかない- 歩が進めるか 計算時間がかかりすぎる 不要な項目もたくさんある- ひもがついているか組み合わせを考慮すると数億に及ぶ出張講演＠佐世保高専

41評価項目の選定の難しさ• これらの機械学習アルゴリズムの性能，ひいては人工知能 (AI) の性能は，対象をどんな項目で評価するかに大きく依存する．

出張講演＠佐世保高専

42

職人技
•

既存の機械学習の手法では，評価項目の選定と値の設定は人間が手作業で行っていた．

•職人技によるチューニングの世界．

金銀桂香

歩

馬成銀

170 140 100806050

20 185 16091

飛角龍

成桂成香と827865

出張講演＠佐世保高専

43

職人技
•

既存の機械学習の手法では，評価項目の選定と値の設定は人間が手作業で行っていた．

•職人技によるチューニングの世界．

この辛い作業を自動化したい…

角金銀桂香

歩

馬成銀

170 1409080605025 185 160

91

飛龍成
桂成
香と82

78

65

出張講演＠佐世保高専

44

深層学習 (Deep Learning)•

蓄積された大量のデータから，コンピュータが自動的に評価項目を作り出す手法．
 人間による評価項目の選定，数値の設定（職人技）を必要としない．

•

現在の人工知能ブームは，深層学習の発達・普及によるところが大きい．

•「人工知能研究における50年来のブレイクスルー」

出張講演＠佐世保高専

45

大規模データ処理

出張講演＠佐世保高専

46

ビッグデータ
毎日のように大量のデジタルデータが生成され，蓄積され続けている．
 Google: 60 億件の検索 Facebook: 43 億メッセージ
 Twitter: 5 億ツイート YouTube: 400 万時間分の動画

データは https://www.gwava.com/blog/internet-data-created-daily より
出張講演＠佐世保高専

47

情報爆発
•

電子データの量が「爆発的に」増加している！

喜連川優「情報爆発のこれまでとこれから」,電子情報通信学会誌, Vol.94, No8, 2011

出張講演＠佐世保高専

48

私の研究
【圧縮文字列データ処理】 デジタルデータを文字列（記号の連鎖）として捉え，
 データを圧縮したまま処理する技術．

出張講演＠佐世保高専

49

データ圧縮文字列データを圧縮して表現すれば，データの「無駄」を削減できる．
例１）すもももももももものうち＝すも8のうち
例２）にわにわにわにわとりがいる＝(にわ)4とりがいる
出張講演＠佐世保高専

研究成果• 圧縮された文字列データ上で情報検索を高速に行うアルゴリズムを開発した．
大量のデータも圧縮すれば小さくなる
 圧縮することで，情報検索の速度も向上！


出張講演＠佐世保高専

九州大学の情報系学科

出張講演＠佐世保高専

52

九州大学 工学部 電気情報工学科
工学部
電気情報工学

物質科学工学

地球環境工学

機械航空工学

建築学

電気電子工学課程

電磁気，電力システム，超電導など

電子通信工学課程

通信ネットワーク，信号処理など

計算機工学課程

アルゴリズム，ソフトウェア，人工知能など

出張講演＠佐世保高専

53

まとめ
• アルゴリズムとは，計算の手順のことである．
• アルゴリズムの工夫次第で，計算を高速化できる．
• 実社会の様々な場面でアルゴリズムが活躍中．
• アルゴリズム・プロコン等に興味がある人の大学編入・大学院進学を歓迎します！

出張講演＠佐世保高専54