1/9 多次元データからの情報抽出: 回帰分析(2), 発展項目

1/9 多次元データからの情報抽出: 回帰分析(2), 発展項目

前回の補足

試験について

前回の感想，質問より

Q.
連立方程式に対する前進消去が行列の行基本変形と似ていて面白かったです。
A.
前進消去は、行列の行基本変形そのものなので、昨年までのテキストではそのように説明していたのですが、高等学校の数学の範囲の変更を反映して、今回の標準テキストでは行列の言葉を使わずに説明しています。
Q.
9章のスライドの21枚目で0.1を二進数で表すと0.000100110011…と書いてあるのですが0.00011001100…の誤りではないでしょうか
A.
ご指摘の通り，1が1つ抜けていました．「教材」には修正版をアップロードしておきました．
Q.
連立一次方程式を有理数型を用いて解いたら、計算量はどれくらいになるのだろう
A.
Pythonではfraction パッケージを使えば，有理数型が使えるので，たとえば 
from fractions import Fraction
a = [[Fraction(2), Fraction(3), Fraction(4), Fraction(11)],
[Fraction(5), Fraction(2), Fraction(2), Fraction(6)],
[Fraction(-1), Fraction(5), Fraction(-1), Fraction(2)]]
solve_linear(a)
のように実行してみると， 
[Fraction(2, 93), Fraction(77, 93), Fraction(197, 93)]
と，有理数で答えを得ることができます．入力が有理数ならば誤差なく計算できるので有利ですね．

ただし，有理数型は，

  • 分子と分母となる整数として，64ビットで表せない数も表現できる代わりに，ビット数に応じてメモリを消費する．
  • 有理数型同士の四則演算はビット数に応じて時間がかかる．加減算は，表現に要するメモリ量に比例する実行時間で実現できるが，乗除算は使用するアルゴリズムによって計算量が異なる(「多倍長」，「乗除算」，「アルゴリズム」といったキーワードで検索してみてください)．
という理由で問題のサイズから簡単に計算量のオーダを求めることが難しくなっています．
Q.
与えられた行列の行列式を求めるプログラムを作成し、クラメルの公式を用いて連立方程式を解かないのは、計算量の問題ですか。（その場合のオーダーってn×n!ですか？）（ついでに行列式を求めるプログラムを紹介してほしさが少しあります）
A.
はい．クラメルの公式はわかりやすいのですが，計算回数が多いので使われませんね．オーダーは，n×n!といってもスターリングの公式を使って n! の近似をおこなって表現しても構いません． 行列式を求めるのは，前進消去の関数 fe にちょっと手を加えればできるので，興味があるのでしたら考えてみてください．
Q.
計算量のところでfeがeraseをn(n-1)/2回呼ぶと書かれているが、なぜその数になるのかがわからなかった。
A.
はい．これは考えてみないとわかりにくいかと思います．まずlen(a)がnに対応します． 
 for i in range(0, len(a)):
とあるので，iは0からn-1 まで繰り返しますが，たとえば，iが0の時， 
   for j in range(i + 1, len(a)):
      erase(a, j, i)
でeraseを呼び出すのは，jが1からn-1 まですなわちn-1回となります．iが1増えるごとに呼び出し回数が1減るので，総呼び出し回数は，(n-1)+(n-2)+...+1 となるわけです．高校で習ったとおり，これはn(n-1)/2 となりますね．

前回の課題について

講義資料

講義フォルダの作成

投票システム

vote.pyをダウンロードして(「リンク先のファイルを別名で保存」で，ホームフォルダの下のalgo18を選択(なければ作る)．".txt"を「追加しない」を選ぶ)保存します．ドックからターミナルを起動して， 
cd ~/algo18
を済ませてから， 
python vote.py 選択肢番号
のように使います．

Jupyter Notebookを使いながら(一旦終了せずに)，投票システムも使うには，ターミナルのメニューバーの「シェル」->「新規タブ」を選ぶか，[Command]+[T]で別のタブを開いて(あるいは[Command]+[N]で別のウィンドウを開いて)，投票システムを使うことをお勧めします．このあたりのことは，「はいぱーワークブック」の15.4 ターミナルの便利な使い方に書いてあるので参考にしてください．

テキストの補足

Notebook教材

以下のNotebook教材は，~/algo18 以下に ダウンロードして，Jupyter Notebookからopenして使ったり， Google Colaboratoryを使って，クラウド実行環境でPythonプログラムを実行できます．ダウンロードする場合もGoogle Colaboratoryの使い方を参照してください．Googleアカウントへのログインを求められたときは，通常のGoogleアカウント「XXX@gmail.com」ではなく，ECCSクラウドメールのアカウント「XXX@g.ecc.u-tokyo.ac.jp」を使ってログインしてください．

今日の課題