MyEnigma

とあるエンジニアのブログです。#Robotics #Programing #C++ #Python #MATLAB #Vim #Mathematics #Book #Movie #Traveling #Mac #iPhone

スタンフォード大学の学生が学ぶ行列入門

目次

 

はじめに

スタンフォード大学には

機械学習を学ぶ上での第一歩として、

Introduction to Matrix Methods (EE103)という授業があります。

 

今回の記事では、

この授業の教科書である

Introduction to Applied Linear Algebraを

読んだ際の技術メモです。

 

この教科書は下記のリンクのページから

pdfをダウンロードすることができます。

 

本記事では、

上記の教科書の行列の部分のみのメモです。

他の部分に関しては、下記の記事を参照下さい。

myenigma.hatenablog.com

myenigma.hatenablog.com

 

行列

行列の基礎

行列のインデックスも、

ベクトルと同じようにプログラミング言語によって、

インデックスの表し方が異なる。

多くの低レベルプログラミング言語では、

行列のインデックスは0始まりだが、

幾つかの高レベル言語では、

1始まりの場合もある。

 

多くの教科書や論文では、

行列は大文字のアルファベットで表し(例:A)

ベクトルは小文字のアルファベットで表す(例:a)

 

行列データの例

  • 画像

  • 降水量データ (m個の場所におけるn時間の降水量データ)

  • 投資回収 (m個のアセットにおけるn期間の利益率)

疎行列

nnz(A)はAの各要素の0でない要素の数を表し、

nnz(A)が小さい行列を疎行列という。

疎行列は効率的に保存する方法があり、

多くのデータ(購入行列など)は大抵疎行列である。

三角行列は50%は0でないため、スパースではない。

 

転置

行列の転置は、部分行列の場所を転置し、

その部分行列を転置したものと同じになる。

f:id:meison_amsl:20180512095218p:plain

行列ノルム

行列のノルムの代表的なものに、

フロベニウスノルムがあり、

||A||_F や ||A||と表記される。

フロベニウスノルムは、行列の各要素の二乗の総和のルートである。

行列のノルムは、行列の各ベクトルのノルムの和と同じになる。

 

行列の掛け算

ベクトルに行列を掛け算することにより、

べクトルの差分を計算することができる。

f:id:meison_amsl:20180512100014p:plain

f:id:meison_amsl:20180512100030p:plain

 

また、同じように

ベクトルの累積和ベクトルを計算することもできる。

f:id:meison_amsl:20180512100223p:plain

f:id:meison_amsl:20180512100245p:plain

 

行列演算の応用例

幾何学的変換

  • スケール変換

  • 回転

  • 同次変換

  • セレクター (ベクトルの一部を抽出したり、順番を変える)

  • 画像のダウンサンプリング

  • グラフ構造

  • ネットワーク

畳み込み

畳み込みの計算は*(アスタリスク)で表すことができ、

行列の掛け算で表すことができる。

 

mean filter、画像のぼかしフィルターなどは

Convolutionで表すことができる。

この畳込みn計算は、高速に計算するアルゴリズムがあり、

Fast FFTなどで利用されている。

 

線形変換

多くの関数は、

線形 y = Axやアフィンy = Ax+bに近似することで、

利用しやすくなる。

その近似手法の一つがテイラー展開である。

 

線形動的モデル

下記の式を線形動的モデルと呼ぶ。

f:id:meison_amsl:20180520151657p:plain

 

線形動的モデルでは、

Aが時刻によって変わらないAt=At-1のことを、

Time invariant モデルといい、

ut(input)とct(offset)はシステム外部からの、

システムへの影響を表す。

この線形動的モデルのように、

次の状態が現在の状態のみに依存することを

マルコフ性という。

 

この線形動的モデルを利用することにより、

  • 各年齢の人口分布の推移

  • 伝染病のモデル

  • 物体の運動

  • 需要と供給のモデル

などを表すことができる。

行列の掛け算

ベクトルの内積: a^Tb

ベクトルの外積: ab^T

ある行列Aに対して、

G = A^TAとなる行列をグラム行列という。

 

ある行列Qにおいて、転置した行列と

逆行列が同じ行列を直交行列という。

Q^T = Q^-1

直交行列 - Wikipedia

 

QR分解とは、

QR分解 - Wikipedia

ある行列Aを、ある直交行列Qと、

上三角行列Rに分解すること。

A = QR

このQR分解をすることにより、

ある行列の逆行列が計算できるようになる。

QR分解の代表的なアルゴリズムとして、

グラム・シュミッドアルゴリズムがある。

グラム・シュミットの正規直交化法 - Wikipedia

 

逆行列

ある正方行列の逆行列を計算できる場合、

その行列を可逆行列 invertible matrixや特異行列singular matrixという。

 

線形方程式の解法

上三角行列Rに対して、

Rx =b

という形の線形方程式は、

Back substitution(後退代入法)を使うことで解くことができる。

 

通常の行列Aに対して、

Ax = b

という線形方程式を解く場合は、

まず初めに、AをQR分解し、

A = QRを計算し、

QRx = bから、

Qは直行行列であるため、

両辺の左からQ^-1を掛けて、

Q^-1QRx = Q^-1bより、

Rx = Q^-1b = Q^T bとなる。

あとは、QR分解の結果のRとQを使って、

上記の上三角行列の線形方程式を

Back substitutionで解けば、

逆行列が計算できる。

 

逆行列の計算量は行列の次元をnとすると、

約3n^3である。

 

Ax = bの式において、A^-1bを計算する演算を

バックスラッシュで表すプログラミング言語もある。

(MATLABなど)

 

この逆行列を利用することにより、

  • 多項式補間

  • 化学反応の平衡シミュレーション

  • 熱放射シミュレーション

などを実施することができる。

 

Pseudo inverse 疑似逆行列

over determinedやunder-determinedな線形方程式における

逆行列は疑似逆行列として計算できる。

 

疑似逆行列の計算としては、

A = QRのQR分解が計算出来た場合、

疑似逆行列 A^+は、

A^+ = R^-1 Q^T

で計算でき、

A^T = QRのQR分解が計算出来た場合は、

A^+ = Q (R^-1)^T

で計算できる。

 

参考資料

myenigma.hatenablog.com

myenigma.hatenablog.com

myenigma.hatenablog.com

myenigma.hatenablog.com

myenigma.hatenablog.com

 

MyEnigma Supporters

もしこの記事が参考になり、

ブログをサポートしたいと思われた方は、

こちらからよろしくお願いします。

myenigma.hatenablog.com