データサイエンスを学習し始めて３日経ち、感じた事

今年の7月始めからデータサイエンスの学習をしています。 学習してから、2～3日経って思ったことをまとめます。

目次

1. データサイエンスを学び始めた理由
2. edXでデータサイエンスの授業を受けています
   1. 英語でデータサイエンスを学べる
   2. 最初の講義：ナップサック問題
   3. 次の講義：動的計画法
      1. 小さな問題に細分化して考え、その計算結果をメモに残す
      2. フィボナッチ数列を動的計画法で求める
   4. このような最適化問題をプログラムとして実装します
3. データサイエンス：数学とプログラミングの能力を活かせる分野

データサイエンスを学び始めた理由

これからの時代、データを適切に分析し戦略を立てる能力が求められるようになる気がします。 だから、データサイエンス(data science)や機械学習(machine learning)の基本を 学習すると決めました。

edXでデータサイエンスの授業を受けています

英語でデータサイエンスを学べる

「どんな場所でも生き抜く能力は何か」と考えました。 その代表例をあげるとすると、「プログラミング」と「英語」でしょう。

それを同時に学べるサイトがedXなのです。 特に留学希望者におすすめの学習サイトです。

まず、私はPython入門の授業（MITx: 6.00.1x）を受けました。 次に、今、データサイエンス入門の授業（MITx: 6.00.2x）を受けています。

データサイエンス入門の授業は、Python入門の授業の3倍くらい難しいです。 でも、楽しいです。 いま、3回目の講義を受けている途中です。

最初の講義：ナップサック問題

最初の講義のお題は、 ナップサック問題（knapsack problem）でした。 簡単に言うと、下のような最適解を求める問題です。（私がアイテム、価値、重さを決めました）

アイテムを適切に選んでナップサックに詰め込み、 ナップサックの中のアイテムの価値の和を最大にしなさい。

※ただし、以下の条件があります。

• ナップサック： 10kgまで入る
• アイテム： 人形、PC、時計、机がそれぞれ１個

アイテム名	価値[$]	重さ[kg]
人形	200	0.5
PC	500	3
時計	300	4
机	400	7.5

ナップサックの容量を無視していいとしたら、 持っていけるアイテムの組み合わせは全部で 2^n = 2^4 =16通り です。

１番目のアイテムを持っていくかどうかは２通り、 2番目も2通り、3番目も2通り、・・・、n番目も2通りです。 よって、全ての組み合わせは、2^n = 2^4 =16通り ですね。

人形	PC	時計	机	価値	重さ
x	x	x	x	0	0
x	x	x	o	400	7.5
x	x	o	x	300	4
x	x	o	o	700	11.5
x	o	x	x	500	3
x	o	x	o	900	10.5
x	o	o	x	800	7
x	o	o	o	1200	14.5
o	x	x	x	200	0.5
o	x	x	o	600	8.0
o	x	o	x	500	4.5
o	x	o	o	900	12.0
o	o	x	x	700	3.5
o	o	x	o	1100	11.0
o	o	o	x	1000	7.5
o	o	o	o	1400	15.0

人形、PC、時計という組み合わせが、この問題の最適解(optimal solution)です。 価値の合計は1000ドル。 10kg以下という条件を満たす組み合わせの中で最も価値が大きいです。

総当たりで解を求めたら、2^n回も計算しないといけないので、効率が悪いです。 そこで、1kgあたりの価値の高いものから順にナップサックに詰め込んでみましょう。

すると、計算回数が少ないわりに、ぼちぼち良い答えを求めることができます。 このような方法を貪欲法（ greedy algorithm）といいます。 貪欲に数字の大きい物からナップサックに詰め込むシンプルなアルゴリズムです。

次の講義：動的計画法

小さな問題に細分化して考え、その計算結果をメモに残す

引き続き、いろいろな最適化問題（optimization problem）を考えました。

最適解を求める過程で、同じような計算を何回もしている事があります。 しかし、それは非効率です。

だから、問題を小さな問題に細分化して、その計算結果をメモ化(Memoization)しましょう。 そして、必要なときにそのメモを呼び出します。 すると、重複した計算を省く事ができます。

このような手法は動的計画法（ dynamic programming)と呼ばれています。

フィボナッチ数列を動的計画法で求める

例えば、この前に紹介した フィボナッチ数列を再帰的に効率よく求めるプログラム のなかで、dynamic programming という手法が用いられています。

フィボナッチ数列F(n) を求めるという問題は F(1),F(2),F(3),...,F(n-1)を求めるという小さな問題に細分化されます。 このような小さな問題は部分問題（subproblem）と呼ばれています。

そして、部分問題の答えをメモとして記録し、必要なときに呼び出します。 すると、同じような計算を何回もしなくてすみます。

下の図を例に話します。F(5) を求めたいとします。

draw-fibonacci-tree.py

何度も同じ計算をすることを避けるため、 上の図の左端（黄色）のフィボナッチ数列の値を求めて、その結果をメモに記録します。 たったこれだけで、F(5) の値を求めることができます。

工夫しなければ、全部を計算しないといけません。 でも、工夫すれば、左端（黄色）の部分だけ計算すればいいのです。

普通にフィボナッチ数列を再帰的に求めるなら、指数関数的な計算回数が必要です。 nの数が大きいなら、一生かかっても計算しきれません。

一方、dynamic programming　を用いるなら、nに比例した計算回数ですみます。 一瞬で計算が完了します。

このような最適化問題をプログラムとして実装します

このような問題をPytyhonプログラムとして実装しています。 アイテムのclassを作って、メソッドを作って・・・、解を出力するみたいな感じです。

データサイエンスに興味がある人は、 Pythonプログラミングの基礎をしっかりと学習しておく必要がありそうです。

データサイエンス：数学とプログラミングの能力を活かせる分野

私がデータサイエンスを学習し始めて、3日くらい経ちました。 データサイエンスは数学やプログラミングの能力を活かせる分野だ、と私は思います。

「システム開発とデータサイエンスは似ているけど違う。転向はあまり簡単ではない」 と私は聞いていました。 言っている意味が分からなかったのですが、 早くもその意味を少し理解することができました。

データサイエンスは、数学の理論がベースにあって、 それをPython等のプログラミング言語で実装するような学問です。

プログラミングを使って、行列の掛け算したり、 連立一次方程式の解を求めたりしてる感覚に近いです。

つい最近、べき集合（Power set)を求めるようなプログラムを作りました。 データサイエンスの講義の演習問題です。

S=[a,b,c]の場合、 べき集合 p(S)=[[],[a],[b],[c],[a,b],[b,c],[c,a],[a,b,c]] です。

２進法をイメージすれば、べき集合を求めるプログラムを作るのは意外と簡単ですが、 何もヒントがなければ、難しかったでしょう。