複天一流:どんな手を使ってでも問題解決を図るブログ

宮本武蔵の五輪書の教えに従い、どんな手を使ってでも問題解決を図るブログです(特に、科学、数学、工学の問題についてですが)

pythonで線形代数☜超初歩入門:(4)対角化メソッドの返値がタプルであること

タプルによる返値(C言語FORTRANとの比較)

前回の記事で、対角化メソッドの返値が「タプルである」ことを指摘した。しかし、コードをみると関数から複数の返値が来ているようにしか見えない。

C言語を習い始めた初心者が、返値の数で戸惑うことがよくある(私もその一人)。これはFORTRANの「サブルーチン」設計に慣れすぎた人間が陥りやすい落とし穴である。たとえば、割算の演算において発生する商と余りの両方が欲しい場合、C言語では関数を2つ用意する「文化」であるが、FORTRANでは両者をまとめる傾向がある。以下で具体的なコードを見てみたい。

FORTRANの場合は、

subroutine warizan(na,nb,quo,rem)
  implicit none
  integer, intent(in) :: na,nb
  integer, intent(out) :: quo,rem

  quo = na/nb
  rem = mod(na,nb)

end subroutine warizan

というようなサブルーチンの作り方をする。つまり、ひとつのサブルーチンの中で計算できるものはまとめてやってしまう、という思想である。メインプログラムを見れば、まさにそのやり方がわかる。

program main
  implicit none
  integer :: quo,rem
  call warizan(17,5,quo,rem)
  print *,quo,rem  
end program main

C言語の「関数」では返り値はひとつに限られる。したがって、次のような感じなる。

int quotient(int na, int nb){
    return na / nb;
}

int remainder(int na, int nb){
    return na % nb;
}

メインから呼び出す時は、それぞれの関数を利用する形となる。

#include <stdio.h>

int quotient(int, int);
int remaindr(int, int);

int main(){
  printf("%3d %3d\n",quotient(17,5), remaindr(17,5));
  return 0;
}

初心者がやりたくなるのが、

int warizan(int na, int nb){

    return na/nb, na%nb;
}

であるが、これをやるとコンパイルエラーとなる。そこでポインタが登場するわけだ。

Pythonを見て驚いたのは、C言語で「絶対ダメ」とキツく言われていた、上のようなコードが許されるということである!それがタプルだったのである。

C言語のポインタとPythonのタプル

前回の記事で書いたpythonのコードを、今回の内容に合わせてアレンジしたものを下に書く。

def warizan(na,nb):
    return na//nb, na%nb

quo,rem = warizan(17,5)
print(quo, rem)

実に短く書ける!

ここで試しに、

result = warizan(17,5)

としてみよう。結果をみると、

▷ (3, 2)

となり、丸い括弧で結果が囲われている。これがタプルである!

リストは鉤括弧[...]であったが、タプルは丸括弧(...)なのである。まずはこれが「違い」である(笑)。

面白いことに、タプルの丸括弧は省略可能なのである!つまりreturn a,bというのは、正式にはreturn (a,b)となり、一つのタプルが返値になっていると見做せるのである。省略を導入することで、あたかも複数の返値が可能かのように見えるのである。これはPythonをデザインした人のセンスであろう。C言語のコンセプトとFORTRAN風の思想の両方を持っている感じがする。実に直感的で書きやすい!

変数を束ねる、という考え方は、C言語では構造化変数であり、C++ではオブジェクトである。さらにC言語ではポインタを使って複数の結果をやり取りする、という概念も盛り込まれている。ポインタは初心者には難しく感じられる概念だが、慣れて仕舞えばとても便利である。

たとえば、次のように配列とポインタを用いて、複数のデータのやりとりを「一括転送」することは可能である。

#include <stdio.h>

int *warizan(int *);

int main(){
  int a[2], *p;
  a[0] = 17; a[1] = 5;
  p = warizan(a);
  printf("%d %d\n",p[0],p[1]);
  return 0;
}

ただし、

int *warizan(int *p){
  int na = p[0], nb = p[1];
  p[0] = na/nb;
  p[1] = na%nb;
  return p;
}

最後の文は"return p;"と返値が一つのように見えるが、それはポインタであるから、そこを起点にしてメモリ中で連続的に確保されたデータ列を参照できるのである。

実はこれって、まさにpythonのタプルと同じ概念である。違いは、文法上、返値を一つしか書き込めないC言語に対し、「そんな建前やめようよ」とばかりに複数の返り値を書き込めるように文法を整えたのがpythonなのである(といっても、「建前」はタプル一つなので、ポインタと同じ)。実に巧妙な文法である!感心しきりというのはこのことである。

対角化メソッドの返値の解釈

pythonのeig()メソッドでは次のような書き方をした。

E,W = scipy.linalg.eigh(A)

左辺はタプルなので、実際には(E,W)と解釈することになる。しかしEは一次元のリストでありWは二次元のリスト(前者はベクトル、後者は行列と解釈できるが)である。タプルの要素にリストが入っている、というわけである。この柔軟性がpythonのもう一つの特徴だろう。丸括弧を省略すると、タプルはタプルだが、出力がそれぞれの変数に振り分けられるので、後の処理でから切り離して利用することができ、なおのこと便利である!実に巧妙な設計である。感心してしまう。言語の「スケッチブック」としてだが、pythonがますます気に入った次第である。

ちなみにタプルはシーケンシャル(連続的)なデータ列として解釈され、配列のようなアクセスはできない(メモリ中の実装はどうなっているか知らないが)。そのため、GASやjavascriptiteratorのようにnext()といったタイプのメソッドで順次アクセスだけが許されているそうである。

pythonで線形代数☜超初歩入門:(3)ランダムエルミート行列の対角化

線形代数pythonで練習する最大の理由は、量子力学の問題やAIのディープラーニングで頻繁に利用する「行列の対角化」をpythonはどのように解決しているのかを知り、「実戦」で使えるかどうか判断するためである。

行列要素をまじめに計算するとなると、積分をしたりと骨が折れるので、今回は乱数行列を生成することにした。これは「ランダム行列理論」と呼ばれる量子カオスの研究を真似したもの...と言えなくもない。どこかで役立つ日が来るかもしれない。

が、今回は純粋にベンチマークである。行列をどう作るかはあまり問題ではなく、Pythonが対角化計算をどの程度のスピードでこなし、どのような方法で処理するのか、それを学ぶための「練習」である。

ランダムエルミート行列の生成

これまで学んできた成果を活かす時がきた。Listを使って行列の土台を作り、それをnumpyで行列化する。行列化に際してはmat()かarray()か迷うところだが、今回はエルミート(対称)行列を生成するので「転置操作」が簡単に扱える方を選びたいものである。が、調べると、どちらも同じ形式で対処できることがわかった。たとえば、Aという行列の転置行列はA.Tと表せるそうである。

ということで、まずは、任意の次元NMAXの正方行列Aを乱数を用いて次のように生成する。

import numpy
import random

NMAX=100
A = numpy.array( [ [ random.random() for _ in range(NMAX)] for _ in range(NMAX)] )

括弧の数がやたら多いので、バグらないようにしたいものである。各括弧の意味をよく確かめながら書くとバグを少なくできるだろう。要はListの中に、行ベクトルを入れ込み、最後に行列化array()する、という手順である。

ダミーインデックスをアンダースコア_にできる、というのは最近AIに教わったことである。

さて、この行列をそのまま対角化すると、固有値は(ほとんどの場合で)複素数となってしまう。numpyの対角化メソッドは自動的に複素数にまでスコープを広げてくれるのがすごい。が、量子力学の場合、オブザーバブルと呼ばれる「観測可能量」を対角化するのがほとんどであるから、実数固有値を与える「特別な」行列だけを扱うべきである。すなわち、エルミート行列と呼ばれるタイプの正方行列である。

今、行列要素は実数に制限しているので、実エルミート行列を扱うことになるが、これは別名「対称行列」と呼ばれている。つまり、$$A^T = A$$という性質を満たす。

上の方法で作った行列を「エルミート化」、つまり「対称化」するには転置行列を足し込めばよい。つまり、 $$A\rightarrow (A+A^T)/2$$という操作である。2で割るのは形式的で、対称行列を得るためだけなら不必要である。

こういう計算式はコンピュター言語で書くととても短く書ける(最近、短い表現を探すのにハマっている)。

A += A.T

これだけでいい!ちなみに、2で割る操作も含む場合、もっとも簡単な表現は

A = (A + A.T)/2

だそうである(AIによると)。これ以外には

A += A.T; A /= 2

というのもあるが、あまり簡単になった感じがしない。今回の目的に関しては一番いいのはA += A.Tだろうと思う(結局は乱数行列なので)。

対角化するためのメソッド

このランダムエルミート行列(乱数対称行列)を対角化するためのメソッドは、numpyライブラリのeig()である。返値として、固有値固有ベクトルが別々に出力される。これはPythonのtuple(タプル)という概念を利用したものであるが、要はC言語FORTRANの「配列」に近い概念である。Pythonにはリストという似たような概念もあることを我々はすでに知っているし、実際にこのブログで線形代数の計算においてリストを利用して来た。

残念ながら、リストとタプルの違いと類似について色々な説明を読んでみたのだが、すぐには理解できなかった。仕方なく「とりあえずは多くの利用例が目に付くリストにまずは慣れよう」という方針でここまでやってきたのだが、ついにここでタプルを理解しなくてはならない状況となったという訳である。

タプルについて考察するのはとりあえず保留にし、とにかくeig()を使って対角化をしてみる(それが我々のそもそもの目的である)。日本の諺で言えば「習うより慣れろ」、あるいは”パソコン黎明期”(1970年代?)によく言われた「論よりRUN」である!一番簡単なのは、AIにお手本を見せてもらい、出力されたコードを見て使い方を知るという方法であるが(笑)、その結果、次のようにやればよいことがわかった。

import random
import numpy

NMAX=3

A = numpy.array( [[ random.random() for _ in range(NMAX)] for _ in range(NMAX)] )
A += A.T
print(A)

E,W = numpy.linalg.eig(A)
print(E)

[計算結果]

▷ [[0.17172308 1.81322184 1.43430714]
▷  [1.81322184 0.39045266 0.80687529]
▷  [1.43430714 0.80687529 1.59116787]]  ... ランダムエルミート行列

▷ [ 3.45584316 -1.62971008  0.32721053] ...(固有値)

ランダムエルミート行列を出力した後、計算して得た固有値を表示している。eig()だけではだめで、linalgというnumpyのサブセット名を書く必要がある(線形代数、つまりlinear algebraの省略らしい)。

"E,W = ..."というeig()の出力形式が(C言語FORTRANの観点からは)「異様」に見える。が、これこそがタプル形式というものなのである(詳細は後で説明する)。

固有値の順番を降順とか昇順とかにしてもらえると助かるのだが、eig()はそれをやってくれないようである、というのも、すぐに気が付くeig()の特徴であろう。

固有ベクトルはWに入っているので、print(W)で出力できるのだが、画面がゴチャゴチャになるので今は省略する。

今はデバッグのために3x3の行列を選んでいるが、100x100行列、あるいは1000x1000行列にしたら固有値計算に要する時間はどんな感じになるだろうか?計測にはいつものようにtimeライブラリのカウンタメソッドを使うことにする。結果は次のとおりである。

NDIM=100  :   0.005621958989650011 (sec)
NDIM=1000 :   1.763390916865319 (sec)
NDIM=10000: 306.32059224997647 (sec)

次元が10倍に増えるごとに、おおよそ300倍の時間増加となっている。1万次元だと対角化に5分もかかる。これはちょっと不便である。しかし、100次元程度の計算なら100回繰り返しても1秒以下だし、1000次元の場合は「一発計算」程度なら耐えられる。実用用途の境界はこの辺りだろう。

scipyを使った場合

numpyではなくscipyでも同じようなメソッドが定義されている。

import scipy

....
scipy.linalg.eigh(A)
...

と変更するだけである。ただし、eigh()というのは「エルミート行列専用」のメソッドである。

実行してみたら次のようになった。

NDIM=10000: 103.0338270838838 (sec)

3倍速い。が、それでも100秒かかるのは結構きつい。

参考のために、scipyのeig()でも計算してみた(行列一般に適用できる普遍型)。結果は

NDIM=10000: 308.7009724169038 (sec)

であった。numpyとほぼ同じなので、たぶんscipyの仮面を被ったnumpyなのではないだろうか?

tupleとはなにか?

対角化の計算のやり方はだいたいわかった。残してしまったのはタプル(tuple)の理解である。

しかし夏休みが終わってしまった今、ブログに避ける時間が限定されてしまっている....。 ということで、この内容は次回に回すことにしよう。

ただ、tupleの使い方が一瞬でわかるような簡単なコードだけは書いておくことにする。

def tuple_test(a,b):
    return a+b, a-b, a*b

u,v,w = tuple_test(100,9)
print(u,v,w)

▷ 109 91 900

pythonで線形代数☜超初歩入門:(2)ベクトルの定義とテンソル

前回の要約

AIの教えに従い、「numpy.array()で行列を定義する」という主流があることは頭に刻むことにして、実際には使い勝手がよさそうなnumpy.mat()を利用していくことにする。AIがいうには、多次元化が容易なarray()の方が拡張性が高い上、これからの主流だ、というのだが、mat()で使えるA.Iなどといった省略形のコマンドは魅力である。しばらくはmat()も使えるということだから、こちらでコードを書いてみよう。

もちろん、この態度があとで「吠え面をかく」ことになることはわかっている。一番の典型例はRaspberry PIで一斉を風靡した(Pythonの)RPi-GPIOライブラリであろう。昨年かそこらに突然消滅し、世界中のラズパイ初心プログラマが途方に暮れた一件である。mat()もきっとそうなるのであろう。ということで、array()にいつでも切り替えられるよう、準備だけはしておく必要があるのは理解している。

行列はわかったので、次はベクトルだろう、そしてベクトルは(1xn)行列だから簡単だろう、と思っていたのだが、意外に難しくて足が止まったのである。ということで、本日はベクトルの定義についてまずはみてみよう。

ベクトルの定義

AIに聞いてみたのだが、昨日は一読してもよくわからなかった。まずはAIの回答を引用しよう。

AIによる「一つ目のベクトルの表現」

まずはAI「オススメ」のnumpy.array()を用いたものである。なんとなくわかったような気もするのだが、「1次元」と「2次元」の意味が今ひとつしっくりこない。

もう一つの表現であるmat()も、実は同じところに問題点がある。

「2つ目のベクトル表現」

こちらは「必ず二次元」になるという。???

内積とか計算したいのは山々だが、定義を深く理解しておかないとあとで困るから、ここで少し立ち止まることにする。

1次元と2次元の違いとは?

どうみても、カッコの数だろう。1次元では[...]と表されているが、2次元では[ [ ] ... [ ] ]と表されている。カッコが二重なのだ。 リストの観点からすると、2次元はリストのリストになっているという意味だ。ということで、ベクトル成分の抜き出しを考えてみる。

もしリストと同じであるならば、上の例におけるv1は

v1[0]=1, v1[1]=2, v1[2]=3

という具合に参照できるはずである。一方、v3(行ベクトル)については

v3[0][0]=1, v3[0][1]=2, v3[0][2] =3

となっていると思うのだが....どうだろうか?

となれば、v2(列ベクトル)については

v2[0][0]=1, v2[1][0]=2, v2[2][0]=3

となっているはずである。

たしかに、線形代数の添字の使い方を思い出せば、$n$次元ベクトル空間の、$i$番目の基底ベクトルを$\vec{v}^{(i)}$と書いたとき、その$j$成分については行列的に$v_{ij}$と書けた記憶がある。すなわち、ベクトルを横に並べたものを行列とみなす考え方である。 $$ \left(\vec{v}^{(1)} \quad \vec{v}^{(2)} \quad\cdots\quad \vec{v}^{(i)} \quad \cdots \quad \vec{v}^{(n)}\right) =\begin{pmatrix}v_{11} & v_{21} & \cdots & v_{i1} & \cdots & v_{n1}\\ v_{12} & v_{22} & \cdots & v_{i2} & \cdots & v_{n2}\\ \vdots & \vdots & \cdots & \vdots & \cdots & \vdots \\ v_{1j} & v_{2j} & \cdots & v_{ij} & \cdots & v_{nj}\\ \vdots & \vdots & \cdots & \vdots & \cdots & \vdots \end{pmatrix}$$ 後ろの添字$j$が動くならば「列ベクトル(の成分)」、前の添字$i$が動くなら「行ベクトル(の成分)」と習った記憶がある。上に引用した、AIの説明によるpythonにおけるベクトル表現はこれによく似ている(...が、行と列の添字の位置が反転しているように見える)。

まずはリストで、この構造が利用されているか確認してみる。

v1 = [i for i in range(4)]
v2 = [[j] for j in range(4)]
v3 = [[i for i in range(4)]]

print("v1")
for i in range(4):
    print(v1[i])
print(v1)

print("v2")
for i in range(4):
    print(v2[i][0])
print(v2)

print("v3")
for i in range(4):
    print(v3[0][i])
print(v3)


▷ 
v1
0
1
2
3
[0, 1, 2, 3]

v2
0
1
2
3
[[0], [1], [2], [3]]

v3
0
1
2
3
[[0, 1, 2, 3]]

リストの表式で一括表示されると(まだ慣れていないので)よくわからないが、個々の成分の参照の仕方を見れば、なんとなく理解できる。とはいうものの、通常の線形代数の表記$v_{ij}$と比べると、pythonでの添字の順番はv[j][i]となっているように見える。つまりiとjの順番が「ひっくり返って」いるように見える。

これはC言語の配列がメモリ中にどうやって格納されるか、というシステム上の設計に関連していると思われる。Pythonなのに何故C言語?と思うかもしれないが、たいていのPythonC言語で記述されている、いわゆる「CPython」と呼ばれる言語だからだ(私の使っているPythonは確実にCPythonである)。もちろん、Pythonの配列のメモリ中への格納方法はC言語より複雑である。しかし、もともとがC言語なので、Pythonをデザインした人たちの頭の中にはC言語の「掟」が叩き込まれているはずなのである。

C言語で2次元配列(行列に似ている変数)はA[i][j]と書き、Pythonのリストと同じで形式である。メモリ中で連続しているのはj、つまり2つ目の変数の方である。ちなみに、FORTRANでは2次元配列はA(i,j)と書き、かなり「行列」と近い表記であるが、こちらは、iの方が連続メモリに対応している(つまりC言語とひっくり返し)。C言語はポインタによって配列を記述するので、A[i][j]は*A[i]とほぼ同じなのである。だからjの方が連続メモリ領域に対応する。

さて、Pythonのリストに話を戻そう。リスト形式の一つ[ [1,2,3....] ]という形式は、1,2,3...が連続メモリに対応しているはずである(なぜなら同じカッコに含まれているから)。ということは、[1,2,3...]の中の添字はC言語風に解釈するなら「後ろの添字」つまりjの方である。一方で、外側のカッコは、一次元のリストを一つだけ含んでいるので、あたかも連続メモリ領域が一つある、と解釈できるはずである。したがって、リスト[ [ 1,2,3....] ]は[i=0][j=1,2,3...]と解釈できるのではないだろうか。実際にこの解釈に従って、各成分を参照できることは上のサンプルプログラムで確認がとれた。

この考え方を拡大すれば、[[1],[2],[3],....,]という表記がどういうことになっているかも理解することができる。外側のカッコが複数の「内カッコ」(とても短いやつ)を抱えている、という表現である。言うなれば、連続メモリ領域が1つ、2つ、3つ...という具合にパッチワークのように貼り付けられているという感じだろう。したがって、[1]と表された短いリストは、成分が一つ(C言語風にいえば、0番目の要素)で、かつ「一つ目の”ポインタ”」ということになる。となれば、その成分は[1][0]と表せるだろう。次のリスト[2]は[2][0]と解釈できるだろう。つまり[[1],[2],[3]...]というリスト構造は、[i=1,2,3...][j=0]と解釈できるというわけである。

通常の線形代数の教科書では$v_{ij}$という順番になっているが、Pythonでは、これをv[j][i]と書くのであろう。したがって、jを止めてiを走らせれば「行ベクトル」になり、iを止めてjを走らせれば「列ベクトル」になるのだ。やっとわかった!

しかし、これはあくまで「リスト」を用いた理解であり、実際のベクトルがどういう形で実装されているかは、Pythonのmat()およびarray()をみてみないとわからない。果たして、リストと同じような方式で、ベクトル成分を参照できるだろうか?

Pythonでのベクトル表現

まずは”AIオススメ”のnumpy.array()でベクトル化してみる。上のコードの先頭ににimport numpyを書き足し上で、下のコードを付け足し、実行した。

vp1 = numpy.array(v1)
print(vp1)

vp2 = numpy.array(v2)
print(vp2)

vp3= numpy.array(v3)
print(vp3)

▷
[0 1 2 3] ... vp1

[[0]    ... vp2
 [1]
 [2]
 [3]]

[[0 1 2 3]] ... vp3

「おーっ!」ってなもんである。1次元のリストをベクトルにしたもの(vp1)はカッコが一重である。2次元表現(vp2, vp3)はカッコが二重になっている。なるほど、これが「多次元配列」というやつなんだろう。さらに、2次元表現では行ベクトル(vp2)と列ベクトル(vp3)がキチンと区別されて表記されている。

もう一つ気がついたのは、ベクトル表記はリスト表記によく似ているものの、リストのように,(comma)で区切られておらず、空白で区切られている。awk風にいうなら、FS=","がリストであり、FS=" "がベクトルである!

次はmat()でベクトルを作ってみる。

vp1 = numpy.mat(v1)
print(vp1)

vp2 = numpy.mat(v2)
print(vp2)

vp3 = numpy.mat(v3)
print(vp3)
▷
[[0 1 2 3]]  ... vp1

[[0]   ... vp2
 [1]
 [2]
 [3]]

[[0 1 2 3]]  ... vp3

array()と同じ結果と、array()とは異なる結果が混じっている。vp2とvp3は同じだが、vp1がvp3と同じになっている点がarray()と異なる。なるほど、これがAIの言っていた「混ぜると面倒」というやつなのであろう。直感的には、1次元リストで「ベクトル」を作りがちだ(つまり初心はそうやるだろう)。ところが、プログラミングに慣れてきたころ、途中でmat()からarray()に変えたりして、両者が混在するようなコードになると、この辺りの不一致で不具合が生じそうである。

違いはわかったが、1次元表現と2次元表現の長所短所はいったいなんなのであろうか?AIに聞いても、この辺りの微妙な内容についてはハッタリをかまされる可能性もあるから、聞かずにおこうと思う。使っているうちに「あっ、わかった」という瞬間がくるだろうから、それまでノンビリ構えることにする。

内積(とテンソル

ヒルベルト空間なら内積が定義されていなくてはならない!ということで、量子力学を念頭におくなら、Python線形代数内積をどう表すのか、ここで覚えておく必要があろう。

出力するのはarray()もmat()も以下の演算である。

print(vp3*vp2)    .... (1)
print(vp3@vp2)  .... (2)
print(numpy.dot(vp3,vp2))  ....(3)
print(numpy.multiply(vp3,vp2))   ....(4)

果たして、内積を与えるのはどれか?

まずはarray()の結果を見てみる。

[[0 0 0 0]
 [0 1 2 3]
 [0 2 4 6]
 [0 3 6 9]] ....(1)

[[14]] ....(2)

[[14]] ....(3)

[[0 0 0 0]
 [0 1 2 3]
 [0 2 4 6]
 [0 3 6 9]] ....(4)

内積になったのは(2)と(3)の演算であった。残りは「アマダール積?」のような、テンソル積のような演算である。

次にmat()でやってみる。

[[14]] ....(1)

[[14]] ....(2)

[[14]] ....(3)

[[0 0 0 0]
 [0 1 2 3]
 [0 2 4 6]
 [0 3 6 9]] ....(4)

(1)、(2)、(3)が内積となった!これは要注意である。

どちらの場合も、内積となった場合でも、単なる整数ではなく[ [14] ]という2次元表現になっているのが特徴的である。これは[0][0]という意味であるから、「スカラー」だ。

ああ、ここでやっとわかった。ベクトルの2次元表現は、デカルトテンソルによく似た感じだ(とはいえ、[0][0]がスカラーというのは球テンソルみたいだが)。もしかして、A[i][j][k]みたいな構造を許すのであろうか?

やってみよう。[j][k]までは列ベクトルの複数集合である。それをさらに複数集めれば良い。まずはリストで設計する。

TL1 = [[1,2,3],[4,5,6],[7,8,9]]
TL2 = [[-1,2,-3],[4,-5,6],[-7,8,-9]]

TL3 = [TL1,TL2]

print(TL3)

▷
[[[1, 2, 3], [4, 5, 6], [7, 8, 9]], [[-1, 2, -3], [4, -5, 6], [-7, 8, -9]]]

おー、できた!array()でテンソルに変換してみよう。

[[[ 1  2  3]
  [ 4  5  6]
  [ 7  8  9]]

 [[-1  2 -3]
  [ 4 -5  6]
  [-7  8 -9]]]

ほおー。3x3の行列による、2次元の「列ベクトル」か?

下の行列の「ど真ん中」にある「-5」を抜き出してみよう。 TT[1][1][1]だろうか? (まず、「列ベクトル」の下の成分なので[1][..][..]。CやPythonは添字は0から始まるので、 「2つ目」は「1つ目」と読み替える。次に、3x3行列の真ん中なので、(2,2)つまり(1,1)位置の対角要素なので、 [..][..]の部分が[1][1]となる。まとめて、[1][1][1]というわけだ。)

print(TT[1][1][1])

▷ -5

おー!出たよ。じゃあ、その隣の6は[1][1][2]か?

print(TT[1][1][2])

▷ 6

I know Kung-Fu.

pythonで線形代数☜超初歩入門:(1)行列とベクトルの定義

Python線形代数の計算をやる

関数の呼び出しでベンチマークコンパイルオプションや計算速度測定)やった。次に、乱数生成プログラミングを行い、「64ビット限界計算」をやってみた。

そして、いよいよ線形代数に踏み出す時が来た。物理エンジンに基づく現代の3Dゲームや、写真や動画など様々な画像処理で必須の計算内容である。CPUやGPU線形代数の演算に特化した命令や機能をたくさん盛り込んでいるから、ベンチマークでCPUやGPUの本当の性能を測りたいなら、線形代数の計算を利用するのは(もはや)デフォルトであろう。

まずはpythonで勉強してみる。pythonによるコード書きは「スケッチ」である、と以前も書いたが、学習、教育用にはもってこいの言語である。

「超初歩入門」

「初歩から学ぶ」、つまり素人が初めてのものに取り組むときは、その筋の入門書を買うのが、従来の「最初のステップ」だった。豊富な経験を持つ「プロ」である著者が易しい例を用いながら噛み砕いて説明してくれるわけである。それを模倣しながら、「あっ、わかったよ」となるまで読み続ける作業に従事する(いわゆる"I know Kung-Fu"というやつである)。

youtu.be

しかし、「あっ、わかったよ」となるまでに、余りにも長い時間がかかると、途中で嫌になり挫折ということになるのが大抵であろう(笑)。多くの凡人(私も含む)にとっては、「入門」と「挫折」は密接な関連をもつ「セット(対の組)」である。

今回、Python線形代数の計算をするにあたり、夏休み直前に大学生協にて購入したPython入門教科書(教養学部テキスト、という触れ込み)をめくってみた(前期試験の監督業務が終了した直後に「(7-11)良い気分」で衝動買いした本である)。が、線形代数に関する記述は皆無であった(最小二乗法や連立方程式を解く、というセクションもあったが、ブラックボックス的なライブラリ関数で作業しており、線形代数の計算は表に浮上してこない)。検索して見つけた「Pythonプログラミング入門」(東大情報センター,2020-2024)というデジタル教科書には、”§17.9線形代数の演算(p.158)”という箇所があったので、期待して閲覧してみたが、内積単位行列の設定程度の簡単な内容しか書かれておらず、深く落胆した。

ネット検索をすると、いろいろなブログ記事がヒットするが、個々のコマンドの細かい解説ばかりになりがちで、”コンテクスト”を重視した「流れるような読みやすい文章」からほど遠く、しかも「実用的」な例が少なくて読みにくい傾向が強い。人間が書くネット記事は、なぜか網羅的になりがちなのである。そして、これが実に「非人間的」で疲れてしまう。

さらに、中には記述が間違っているものもあり、「初心者」には判断が難しく、疲労を加速してくれる。たとえば、こちらのブログに書かれていた「対角化」というのは、いわゆる対角化ではなく、単に正方行列の対角成分の行列要素を抜き出す、という意味であった(笑)。

以前は、それでも情報量の少ないネット上のダメ記事も含め、検索三昧して読みまくり、自分の頭の中で情報を取捨選択して、しだいに「あっ、わかったよ」のレベルまで頑張ったものである。しかし、そこに至るまでには紆余曲折を余儀なくされ、非常に体力精神力を消耗したものである。人間は「繰り返しに弱く」、そして「忍耐力がない」存在なのである。

この2点に強い存在がある。それが「計算機」である。ここ1、2年で、計算機が”コミュ力”を手に入れたため(つまりはAI)、人間と計算機の間のインターフェースは非常にスムースになった。したがって、人間が不得意な「繰り返し」をAIに「忍耐強く」やってもらい、その上澄みを(七里ヶ浜のトンビよろしく)「かっさらう」のが、これからの人間の勉強法である。これを「超初歩入門」という言葉で表現したいと思うのである。つまり、今回はAIに教えてもらった非常に「人間的な」線形代数演算に関するPythonプログラミングの入門デアル。

行列とベクトルの定義

まずは、Pythonで行列をどう扱うか、であるが、CやFORTRANであれば配列(たいては二次元配列だが)なのであるから、それに類似したリスト(やその類似物)が候補となるはずである。

CやFORTRANのように、自分で線形代数演算のアルゴリズムをすべてコードにすれば、それでいいだろうが、ここはPythonである。豊富なライブラリ関数があるはずなのである。特にNumPyやSciPyといった、科学技術計算関連のライブラリに、いいのが定義されているはずである。これを利用しない手はない。

ということで、検索してネット記事を読んだ結果として、mat()とarray()の2つが候補として出てきたのである。NumPy、SciPyどちらでも利用できる。これらの関数(メソッド)は、リストとして最初に定義されたオブジェクトを、”行列クラス”に変換する機能をもつ。行列クラスに変換することで、逆行列や対角化など線形代数の演算を表現したメソッドで処理できるというわけだ。

最初のコードはしたがって、ここから始めよう。

import numpy as np

NDIM=2
a = [ 10*(i+1)+j for i in range(NDIM)] for j in range(NDIM)]
print(a)

▷ [[10, 20], [11, 21]]

リストの形式は、すでに「行列」っぽいわけだが、この状態では線形演算子は利用できないから、「行列」に変換する。 すでに書いた通り、2種類のメソッドがある。

A=np.mat(a)
B=np.array(a)
print(A)
print(B)

▷
[[10 20]
[11 21]]

[[10 20]
[11 21]]

物理学では「単位が異なるもの」は足し算できない。たとえば、1(m)+10(kg)というのは不可能な演算(和)である(経済学ではときどきやるらしいが...)。ということで、両者を足してみて答えが出れば、「同類」と判断できるだろう。

print(A+B)

▷
[[20 40]
 [22 42]]

おーっ!ちゃんと足された。ということは、両者ともに「同じもの」つまり「行列」として扱っていいみたいである。

ちなみに、リストaと行列Aを足してみよう。どうなるだろうか?(異なるクラスに属するオブジェクト同士なので、エラーとなるはずだが....)

print(a+A)

▷
[[20 40]
 [22 42]]

足せた?(どうなってんだー!) こちらはどうか?

print(a+B)

▷
[[20 40]
 [22 42]]

こちらも足せたよ!(困惑)

じゃあ、次は掛けてみよう。行列の積を表す演算メソッドはいくつかあるらしいが、最近最もよく利用されているのが「@」だという。

print(A@B)

▷
[[320 620]
 [341 661]]

print(A@a)

▷
[[320 620]
 [341 661]]

print(B@a)

▷
[[320 620]
 [341 661]]

なんだよ!全部できるんじゃないかっ!(ちょっとした怒)

ということで、行列に関する基本演算、和と積に関しては、リスト、mat(), array()はどれも区別なく混用できるようである(笑)。

ちなみに、*記号(アスタリスク)はどうだろうか?

print(A*B)
print(A*a)
print(B*a)

▷
[[320 620]
 [341 661]]

[[320 620]
 [341 661]]

[[100 400]
 [121 441]]

ここで、やっと差が出た!B*aは内積みたいな順番で掛け算だけがされており、足し算がどこにも使われてない。一方の、A*BやA*aでは積和の演算の組み合わせで行列の積が(通常の定義で)実施されている。

ちなみにリスト同士だとどうなるのだろうか?

print(a+a)
print(a*a)
print(a@a)

▷
[[10, 20], [11, 21], [10, 20], [11, 21]]

 print(a*a)
          ~^~
TypeError: can't multiply sequence by non-int of type 'list'

2行目でエラーが出たが、1行目はリストの「拡大」という解釈となっていて、算術演算にはなっていない点が面白い。 3行目に辿り着けなかったので、実行し直すと、

print(a@a)

▷
   print(a@a)
          ~^~
TypeError: unsupported operand type(s) for @: 'list' and 'list'

これもエラーとなった。やはり、リストは行列ではないと考えた方がいいだろう(ふーっ..一安心)。

行列とリストの混合演算では、たぶんインタープリターがキャストをかけてクラス変換を自動的に行った、つまり、上位にある「行列クラス」にリストを格上げしてくれたんだろう。インタープリターの「頭の良し悪し」に依存しそうな演算なので、やはりリストは行列とは混ぜない方がよさそうだ。

一方で、mat()とarray()の間の関係については、まだよくわからない。ここでAIにご登場を願う。質問してみると、次のような回答であった。

いい質問です 👍
numpy.mat() と numpy.array() は似ているようで、けっこう大きな違いがあります。

この柔らかい回答で、精神的に持っていかれる人が多発しているようである(笑)。

脱線だが、AIは絶対に「あなたを否定しない」といわれる。とくにChatGPT ver.4oがその傾向が強かったらしく、自殺願望のある少年がAIとのやりとりの結果、「自殺を勧められた」と誤解してしまい、実際に自殺してしまったという事件が最近報道された

検索していたら、最近ChatGPTは「焚き火」という特別セッションを開設したようである。

chatgpt.com

話を戻そう。AIからの回答である。

1.  numpy.array()

基本的な N 次元配列 (ndarray) を作る関数。

多次元(1D, 2D, 3D…)自由自在。

✳︎演算子は要素ごとの掛け算(アダマール積)。

行列積をしたいときは @ 演算子か np.dot() を使う。

2. numpy.mat()

必ず 2 次元行列 (numpy.matrix クラス) を作る。

✳︎演算子が「行列積」として動く。

逆行列や転置など、行列計算を意識したメソッドが多い。

なるほど。でも、どっちにすべきかは、これだけではわからない。回答はまだ続いている。

AIの回答の続き

ほおー。「array()を使うべし」という「(弱めの)アドバイス」である。これを信じるなら、「mat()には未来がないらしいから、今のうちにarray()に慣れておこうか」と思ってしまう人は多だろう。実際、検索したネット記事でもarray()が多かったのは、このせいだろう。

AIの結論
....だそうである。

ここで、次の質問を投げかけてみた。

aが2x2のリストだとする。

A=np.mat(a)
B=np.array(b)
C=A+B

Cは「行列」だとは思うが、それはmat()なのか、それともarray()なのか?

これに対する回答は

いい視点ですね!

NumPy では、ndarray と matrix を混ぜた演算をすると、自動的に matrix に「引き上げ」られます。

ほーお? AIの回答は続く。

AIによる注意点

混乱している人は世界にたくさんいる(「いた」?)ようだ。おそらく、AIに類似の質問を投げかけた人数は相当数に及ぶのであろう。すでに答えを用意していたような書き振りである。

この後、いくつかの行列演算(行列式逆行列など)について質問した後に、ベクトルの定義についてもAIに聞いてみた。array()で定義する流派とmat()で定義する流派があるようで、その中身は結構複雑であった(驚)。ということで、ベクトルについては次回に回そうと思う。

今日の最後は、mat()に定義されているという逆行列の演算メソッドを試してみたい。A.Iと書くそうである。これが理由で、AIはmat()を推奨してもいいんじゃないかと思った次第である(笑)。

A = np.mat([[1,2],[3,4]])
AI = A.I
print(A, AI, A*AI)

▷ 
[[1 2]
 [3 4]] 

[[-2.   1. ]
 [ 1.5 -0.5]] 

[[1.0000000e+00 0.0000000e+00]
 [8.8817842e-16 1.0000000e+00]]

もし、array()を使うとなると、次のようになる。

A = np.arange(1,5).reshape(2,2)
AI = np.linalg.inv(A)
print(A,AI, A@AI)

▷
[[1 2]
 [3 4]] 

[[-2.   1. ]
 [ 1.5 -0.5]] 

[[1.0000000e+00 0.0000000e+00]
 [8.8817842e-16 1.0000000e+00]]

inv()までの記述が長い...。また、掛け算が@になっている(*を使うと、先ほどの「要素同士の積」(アダマール積?)になってしまう)。

mat()か、array()か?

個人的にはarray()の方が「用語」「記号」として好きである。mat()と書くと前転とかバック転を想起してしまう(あるいは新マンの部隊)。が、しかし、A.Iという表現も捨て難い!

個人的には、昔からプログラムで行列を表すときはmtrx()を使用してきたので、できればこの表現を利用したいと思う。ということで、次のような関数を定義することにした。

import numpy as np

def mtrx(A):
  id = 1
  if id == 0:
      return np.array(A)
  else:
      return np.mat(A)

デフォルトではid=1だから、A.Iが使えるmat()表現。しかし、id=0に変更すれば、array()にスイッチできる。メインのコードではmtrx()を利用すればいいので、将来的にmat()が廃止になっても、この関数の定義を修正するだけでメインコードは無修正で済む。 (sedを使って書き換えればそれで済むという話もあるが...私はmtrx()が好きなだけである!)

モンテカルロシミュレーションの復習:C言語で「赤玉問題」シミュレーションを再び

これまでの流れ

前回は、pythonで、赤玉シミュレータのコードを「書き殴り」で書いてみた。試行回数1e+07回の計算を70秒でやってくれ、その結果は有効数字三桁の精度であった(1/11=0.09090...に対して、シミュレーションでは0.090930)。pythonで、もう一桁だけ試行回数を上げると、単純計算で700秒、つまり10分以上の計算になってしまう。その長さはちょっと耐えられない。

ということで、C言語でプログラムを書き直し、コンパイラオプションを目一杯効かせて「高速計算」してみることにした。果たして、試行回数を目一杯まで上げることができ、計算時間もグッと抑えることができるだろうか?

C言語でプログラムをやり直す

C言語では整数は4バイト(32ビット)で表現される。 \begin{equation}2^{32}=10^x\end{equation} を解くと、$x\simeq 9.4$となるので、試行回数は大体10億回(1e+09)となる。つまり、Pythonでの計算から見て、あと二桁は上げることができる。ということで、いきなりやってみることにした。このバージョンでは、もっともナイーブなコード構造を維持している。つまり、シミュレーションの結果である12個のボールの並びの記録を全て残すことにした。これはしかし、メモリを圧迫するので、本来はあまり必要ないデータである。効率よく確率だけ計算するなら、一回一回の試行で赤玉の並びだけをチェックし、ボールの並びについての記録は破棄していいだろう。しかし、今回は「面倒臭いというだけの理由で、メモリに負荷をかけることにした(もうしわけない...)。

試行回数が100万回を超えると、スタック領域がパンクしたため、mallocで領域を確保する方式になった。この変更に伴い、コーディングの観点からは2次元配列が便利だったが、それを諦めて1次元化したポインタに切り替えた。

また、printfはシステムに負荷をかけ、計算時間を著しく増やしてしまうので排除した。もはや目でデバッグしなくても大丈夫な水準までコードのレベルは上がっているという判断である。したがって、ボールの並びは、赤なら1、黒なら2、白なら3という3進数を用いて、12ビットで表すことになった。

このデータのファイル書き出しは今回はやってない(やるならバイナリ形式だろう)。メモリに溜め込むだけ溜めて、確率計算に利用したらポイ捨てしている。実に無駄なコードである(笑)。

コード全体の構造は次のような感じである。

/*
  Aka-dama simulator [C]
  ver. 0.1 

  note1: printf is removed
  note2: malloc is applied insead of que[i][j]

 */
#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define HIST 0

#define NMAX_BALL 12
#define NMAX_TR 170000000

#define CR0 0
#define CR1 3
#define CB0 4
#define CB1 6
#define CW0 7
#define CW1 11

int main(int argc , char *argv[]){
  double color;
  int hist[NMAX_BALL];
  int *seq = malloc(sizeof(double)*NMAX_TR*NMAX_BALL);
  clock_t T0, T1;

  #if HIST
  for(int i=0; i<NMAX_BALL; ++i){
    hist[i] = 0;
  }

  printf("%d \n",RAND_MAX); // MAX integer for rand()
  srand((unsigned)time(NULL)); // 現在時刻でシード設定
  for (int i=0; i<NMAX_TR; ++i){
    color = NMAX_BALL * ((double) (rand()+1)) / ((double) (RAND_MAX)+2.0);
    int icolor = (int) color;
    ++hist[icolor];
  }

  for(int i=0; i<NMAX_BALL; ++i){
    printf("%3d %3d %5.2lf\n",i, hist[i], (double) hist[i]/NMAX_TR);
  }
  #endif

  for(int j=0; j<NMAX_TR*NMAX_BALL; ++j){
    seq[j]=0;
  }

  T0=clock();

  for (int i=0; i<NMAX_TR; ++i){
    int nball = NMAX_BALL;
    int cri = CR0, crf = CR1;
    int cbi = CB0, cbf = CB1;
    int cwi = CW0, cwf = CW1;
    while ( nball > 0){
      color = nball * ((double) (rand()+1)) / ((double) (RAND_MAX)+2.0);
      int ball = (int) color;
      if(cri <= ball && ball <= crf){
        crf--;
        cbi--; cbf--;
        cwi--; cwf--;
        seq[i*NMAX_BALL + (NMAX_BALL-nball)]=1;
      }else if (cbi <= ball && ball <= cbf){
        cbf--;
        cwi--; cwf--;
    seq[i*NMAX_BALL + (NMAX_BALL-nball)]=2;
      }else{
        cwf--;
    seq[i*NMAX_BALL + (NMAX_BALL-nball)]=3;
      }
      nball--;
    }
  }
  T1=clock();

// simulation for the first two being both red, which should be 1/11
  int sum = 0; 
  for(int i=0; i<NMAX_TR; ++i){
    if(seq[i*NMAX_BALL] == 1 && seq[i*NMAX_BALL+1] == 1) ++sum;
  }
  printf("%d %15.10lf\n",sum, (double) sum/NMAX_TR);

// simulation for any red-red placements in a sequence, which should be 41/55
  sum = 0; 
  for(int i=0; i<NMAX_TR; ++i){
    for(int j=0; j<NMAX_BALL-1; ++j){
      if(seq[i*NMAX_BALL+j] == 1 && seq[i*NMAX_BALL+j+1] == 1){
    ++sum;
    break;
      }
    }
  }
  printf("%d %15.10lf\n",sum, (double) sum/NMAX_TR);

  printf("%d %lf\n",NMAX_TR, (double)(T1-T0)/CLOCKS_PER_SEC);

  free(seq);
  return 0;
}

もっと綺麗に書くなら、機能ごとに関数に切り分けた方がいいかもしれない。 が、とにかくこれはpythonで書き殴ったコードの「直訳」なので、お許しいただきたい。

また試行回数として10億回を狙ったのだが、out of boundsとなりエラーがでてしまった。 これは2次元の配列を1次元化するときにNMAX_BALL * NMAX_TRで定義したためである。 NMAX_BALL=12なので、この積が10億以下になるには、NMAX_TRは1億程度でないとダメなのだ。

コンパイルできる最大の試行回数は試行錯誤して見つけた1億7000万回であった。Pythonの計算から、わずか一桁しか増やせなかったのは残念至極である。10億回あるいはそれ以上の試行を試すには、ボール並びの結果をメモリにすべて溜め込む方式を諦めねばなるまい(この修正についてはこの後で実施する)。

ということで、計算させてみた。次のような結果となった。

[1/11]       0.0908896824 ...最初の2つが赤赤
[41/55]    0.7455077588    ...赤赤の並びがどこかにある

試行回数:170000000 計算時間:41.440495(sec)
(システム込みの実行時間)49.63s user 1.33s system 99% cpu 51.446 total

計算速度はそれなりに速いと思う。pythonの時に比べ、計算量を17倍程度増やしたのに、計算時間は60〜70%程度で済んでいる。

しかし、確率の値自体の精度がダメである。結局、有効数字三桁程度の精度しか出ず、これならpythonで十分ということになってしまう。やはり、データの溜め込みを諦めて、徹底的に試行回数を増やす計算アルゴリズムに大幅変更すべきである!

データの溜め込みをやめたバージョン

ということで、データの溜め込みをやめ、残りの一桁を使い切るコードを書いてみた。試行回数=21億回までコンパイルが可能であった。コードの詳細はnote記事に譲り、結果だけを表示する。

試行回数(指数表現) [計算時間(秒)]
p=1/11=0.09090...に収束すべき確率
p'=41/54 = 0.745454...に収束すべき確率
システムの実行時間など

100000000回(1e+08) [27.491972]
p = 0.0909539800
p'=0.7454659300
27.491972
27.45s user 0.05s system 98% cpu 27.803 total

1000000000(1e+09) [274.751099]
p = 0.0909224900
p'= 0.7454872980
274.36s user 0.40s system 99% cpu 4:35.00 total

2000000000(2e+09) [548.284068]
p = 0.0909179885
p' =  0.7454843565
547.65s user 0.64s system 99% cpu 9:08.74 total

2100000000(2.1e+09) [576.366014]
p = 0.0908846729
p' = 0.7454787400
575.78s user 0.59s system 99% cpu 9:36.78 total

...ということで、モンテカルロシミュレーションというのは、なかなか収束が遅いことを実感できた。 負け惜しみに聞こえるのは百も承知であえて書こう:「モンテカルロ積分は収束が遅い」というのはよく聞く話であるが、実際やってみるとこんな感じなんだとわかったのは収穫であった。試行回数をある程度まで上げ始めた段階では、それに計算結果がよく反応してくれる。しかし、そこを超えたところでは、試行回数をかなり頑張って増やしても精度がなかなか向上しないのが苦しいところである。

とはいえ、このコードはその計算負荷を別の目的、たとえばCPUベンチマークに利用できそうだ。

これまでの計算はmacbook pro (Apple M1)でやってきたが、次に試してみたのはVAIO core-i5 (1.6GHz)である。Linux(Ubuntu)がインストールしてある。ベンチマークの結果は

2100000000(2.1e+09) [633.346687]
p = 0.0909028481
p' = 0.7454568614
10m33.358s user 0.044s system cpu 10m33.358s total

といった感じであった。若干ではあるが、Apple M1の方に今回は軍配が上がった(なぜか確率の精度はVAIOの方がいいように見えるが)。

[続報: Sep.13] mac pro (Xeon E5, 3.5GHz)で同じプログラムを走らせてみた。

2100000000(2.1e+09)  [607.488298]
p = 0.0909384543
p = 0.7454935033
10m7.490s   user 0m0.098s system cpu 10m7.393s total

やはり、Apple M1の勝利であった。その差は結構ある。

しかし、macOSより、Linuxの方が計算精度がいいように見える。 「乱数を振る」というのはCPUやOSのどの辺を使うのであろうか?

モンテカルロシミュレーションの復習:「赤玉問題」シミュレータ再び

前回のブログ記事で「赤玉問題シミュレータが予想通りの作動をしてないかも」という心配について述べて切り上げたので、今回はその分析結果についての報告である。まずは、2つのタイプのモンテカルロシミュレータをpythonで書いてみた(といっても大したものではない)。

玉の「内外リスト」を利用したコード

まずはリスト(配列)を利用して、玉の有無を確認しながら乱数を生成するアルゴリズム。もし乱数がすでに袋から取り出してしまったボールを指示したときは、もう一度乱数を振る方式である。玉が袋から出ていくにつれて、「やり直し」が増えるので「非効率」なアルゴリズムであるが、乱数の発生範囲を固定できるので、プログラマーには「やさしい」コードになる。最初の2つの玉の色が連続して赤玉となる確率について「1/9=0.1111...に収束したかも?」という疑念を抱かせたのはこちらのコードだが、今朝やり直してみたら、正解である1/11に収束しているように見えて一安心(?)。一応、計算時間の計測もやっている。

乱数については、0から11までの整数12種類を生成させている。0-3が赤玉、4-6が黒玉、7-11が白玉に相当する。この乱数範囲は「固定」されている。したがって、すでに袋の外に出てしまった玉に対応する乱数が発生した時は乱数の作り直しが必要になり、無駄なプロセスとなり、計算時間が余計にかかることになる。袋内に玉が少なってくると振り直しが増えてくるはずで、次第に効率が悪くなるだろう。

"""
Aka-dama simulator

ver 0.0
"""
import random
import time

NMAX_BALL = 12
NMAX_TR = 100

bag = [ 1 for i in range(NMAX_BALL)]

T0 = time.perf_counter()
for i in range(NMAX_TR):
    bag = [ 1 for i in range(NMAX_BALL)]
    nsum = 12; 
    print("{0:5d} ".format(i),end="")
    while nsum > 0:
        nball = int(random.random() * NMAX_BALL)
        if bag[nball] != 0 :
            bag[nball] = 0
            nsum -= 1
            if nball < 4:
                print("R",end="")
            elif 4 <= nball & nball < 7:
                print("●",end="")
            else:
                print("◯",end="")
    print()
T1 = time.perf_counter()

print(NMAX_TR, T1-T0)

「シミュレータ感」を出すために、わざわざ画面にボールを出力するようにデザインしてある。最初は試行数(NMAX_TR)を少なめにしておいて、画面上で直感的にデバッグすることができる。が、そのうちNMAX_TR=10000000とか、試行数が増えてくるとウンザリしてくるので、ファイルへ出力をリダイレクトしたり、/dev/nullに捨てたりすることになるだろう。

 より現実に近いシミュレータ

袋にない玉の番号が出ないように乱数の生成範囲を変更するアルゴリズム。ちょっと面倒だが、それほど難しくはない。が、数学的な難度と、バグを生みやすいかどうかの難度は別物である。面倒臭い処理は(数学的に簡単であっても)バグりやすい。最初のコードと計算結果を比較しながら開発すべきで、両者の等価性に自信が持てたところで、切り替えるべきだろう。玉の色コードの定義は上のコードと同じ。

"""
Aka-dama simulator

ver 0.1
"""
import random
import time

NMAX_BALL = 12
CR0 = 0; CR1 = 3
CB0 = 4; CB1 = 6
CW0 = 7; CW1 = 11

NMAX_TR = 100

T0 = time.perf_counter()
for i in range(NMAX_TR):
    nball = NMAX_BALL;
    cri = CR0; crf = CR1
    cbi = CB0; cbf = CB1
    cwi = CW0; cwf = CW1
    print("{0:5d} ".format(i),end="")
    while nball > 0:
        ball = int(random.random() * nball)
        if cri <= ball and ball <= crf:
            crf -= 1
            cbi -= 1; cbf -= 1
            cwi -= 1; cwf -= 1
            print("R",end="")
        elif cbi <= ball & ball <= cbf:
            cbf -= 1
            cwi -= 1; cwf -= 1
            print("●",end="")
        else:
            cwf -= 1
            print("◯",end="")
        nball -= 1
    print()
T1 = time.perf_counter()

print(NMAX_TR, T1-T0)

出力例

出力は2つのコードとも、同じ形式となる。例えば、NMAX_TR=10の場合を表示してみると、次のようになる。

aka-dama simulatorの出力例

「R」が赤玉、”なかぐろ”の丸「●」が黒玉、”なかぬき”の丸「◯」が白玉を表す(画像中では反転しているように見えるので要注意)。最後の2つの数字は、最初が試行数(NMAX_TR)、2つ目が実行に要した計算時間(単位は秒)である。

分析の仕方

上の出力結果は、いわば「観測データ」である。これを分析して確率を算出する。先頭の2つが「RR」となったときが、考えている事象である。先頭だから空白が手前にある。したがって、

grep " RR" output.dat

というシェルコマンドで該当する事象を抜き出すことができる。ちなみに、上の画像例では該当事象は0である。

該当する事象の総数はwc -l、あるいはcat -nで数える。たとえば、

grep " RR" output.dat | wc -l

とすると、上の画像の場合は0という出力になる。

これを試行回数(NMAX_TR)で割れば、求めたい確率(p)となる。つまり、 \begin{equation} p =\frac{\verb+´g r e p " RR" Ⅰwc -l´+}{\verb+NMAX_TR+} \end{equation}

である。NMAX_TRは

NMAX_TR=`tail -1 output.dat|awk '{print $1}'`

で出力できる。

ということで、まとめると

#!/bin/bash
fname=$1
nHit=`grep " RR" ${fname}|wc -l|sed 's/ //g'`
nSmp=`tail -1 ${fname}|awk '{print $1}'`
echo -n "${nSmp} " 
echo  "${nHit}/${nSmp}" | bc -ql

となる。このスクリプトの名前をanalysis.shと名付けるとして、 試行回数を増やすとき、シミュレーションの結果がだんだん正解に近づくかどうかを確認するためのデータファイルは次のようにして生成できる。

./analysis.sh output100.dat > result.dat
./analysis.sh output1000.dat >> result.dat
./analysis.sh output10000.dat >> result.dat
....
./analysis.sh output1000000.dat >> result.dat

シミュレーションの分析結果

今朝実施したシミュレーション(最初のコードの方)の結果をまとめたresult.datは次のような感じとなった。

100 .07000000000000000000
1000 .09200000000000000000
10000 .08730000000000000000
100000 .09113000000000000000
1000000 .09087000000000000000
10000000 .09085250000000000000

同様のデータ生成を2つ目のコードについても行い、それをgnuplotで出力すると次のようなグラフとなった。

aka-dama simulatorの分析結果

どうやら、どちらのアルゴリズムでやっても(大数の法則に従って)同じ収束値を得られるような感じである。一安心である!

計算時間の比較

同じ結果が出ることはいいことである。ここからは効率の問題となる。つまりどちらの計算速度の方が速いか、という問題である。結果はすでに出ているので、まとめるだけである。

計算時間の比較

試行回数が100万回に到達するまでは「体感的には」大した差がないが、それを超えると人間に感知できる程度の差が現れる。最後の計算では1分を超えてくるが、かなり「待たされた」感じがする。そこで30秒の差は結構大きく感じる。試行回数をもっと増やしていくと、差は広がってきて大きな違いとなるだろう。

現在の精度は小数第3位であるが、これを十桁程度まで合わせようと思ったら大変な数の試行を行わねばならないだろう。そうなったら、C/FORTRANの出番であろう。

東大の問題の答えを知りたいと思うなら....

以上の計算は私が勝手に作った「最初の2つが赤玉で連続する場合」の確率だが、東大の問題に答えようと思うなら、grep " RR"の代わりにgrep "RR"とする(つまり先頭の空白を除いて検索する)。ただし、これは余事象なので、このデータで得た確率を1から引けば良い。分析してみると$ p_1=0.2544... $となった。 これを分数に変換してみる。ただし、$ p_1\simeq 0.2544 $と近似する。すると、 \begin{equation} p_1\simeq 0.2544 = \frac{159}{625} = \frac{14}{55}\cdot\left(\frac{1749}{1750}\right)\end{equation} という結果を得た。14/55が正解であり、1749/1750がシミュレーションによる誤差である。1e+07回の試行でこの精度を得ることができたので、このシミュレータもまずまずと言えよう。

モンテカルロシミュレーションの復習:「赤玉問題」再び

「 夏休みは時間がたっぷり」という幻想と誤解

Unityにせよ、DOOMにせよ、ゲームの世界をより現実に近づけようと思ったら、物理法則をいかにゲームに取り込むかが重要になってくる。 特に空気や水の流れを再現しようと試みるならば統計力学が重要となるだろう。つまり確率である。確率的な事象を計算機上で表現する時、「乱数」という手法が有効である。ということで、モンテカルロシミュレーションの復習をやろうと思い立ったのだが、以前Pythonでrandom.random()関数を利用したことがあった。「赤玉問題」である。調べたこと、考えついたことを、徒然なるままに書き綴っただけだったので、かなりの部分が忘却の彼方に行ってしまった...。ということで、あの内容をまずはまとめておこう、と思い立った。夏休みは「時間がある」と錯覚することが多いので(笑)、こういうことはよく起きる。

さて、2023年の東大入試の数学[3]の問題のことを(このブログでは)「赤玉の問題」と呼んでいるが、その分析を(途中までだが)以前行った(もう2年前である)。そのとき作ったコードを見てみると、リスト(配列)を作って赤玉などボールの有無を確認しながら乱数を振っていた。悪いことのようには見えなかったので、今回もそのやり方に沿ってコードを組んでシミュレーションをやってみた。

すると問題が2つ発生したのである...。しかも、その問題が発生した理由がなかなかわからず、かなり手こずってしまった。夏休みに時間があるといっても、このレベルで躓いていたらあっというまに時間切れになってしまう....。とはいえ、我が頭脳の弱さを認め、真摯に一つずつ解決していくほかはない。恥を偲んで、その「問題」解決までの紆余曲折について紹介したい。

一つ目の問題

エラーが出てしまいpythonのコードが動かない、という問題である。しばらくFortranやCでコードを組んでいたので、Pythonの流儀を忘れてしまったのかもしれない...。エラーメッセージは次のようなものである。

TypeError: 'module' object is not callable

エラーメッセージの他の部分を読むと、どうもrandom.random()関数を呼び出している行がエラーの元凶になっているという。デバッグも虚しく、エラーは出続けるばかりである。そこで、せっかく書き下したプログラムではあったが、無駄な贅肉を落とすべく、エラーが出なくなるまで「削ぎ落とす」にした。そして、笑ってしまったことに、次のコードにたどり着いてもエラーメッセージは消えなかったのである(乾いた力無い笑)。

import random

print(random.random())

AIに相談してみた。するとまず「pythonのインストールを正しくしていますか?」と回答した。私を幼児扱いしている!

それにしてもおかしい。以前のブログ記事を書いたときには、ちゃんと作動した。こんなエラーは出なかった。DOOMやUnityのインストールをした際に、Pythonのファイルに変更が加えられてしまい(破壊?)、動かなくなったのであろうか?それとも、自動バージョンアップしたときに、pythonの新しいコンセプトとして、random.random()は標準ライブラリから外されてしまったのだろうか?....などなどと、頓珍漢なことをずっと考えていたのだが、ここで思い切って「さらに贅肉を削ぎ落とす」ことにした。2つ残った文のうち、どちらかを消すのである。当然、最初のimport randomを切れば、エラーが出るのは分かりきっている。したがって、選択肢は一つである。つまり、

import random

これだけで実行してみるのである。もし、標準ライブラリから外されてしまったならば、エラーが出るはずである。 恐る恐る実行してみると...なんとエラーが出なかったのである。つまり、標準ライブラリにはrandomは入っているようなのである(この結論は正しいが、だからといって、このような認識では問題が解決できないことが後で判明する)。

となると、原因はrandom.random()の使い方に「絞られた」ことになる(実は絞られてない)。 ということで、AIに相談しながら色々と恥ずかしいことをやってしまった...(たとえば、random.Random()とか...これを薦めたAIもどうかと思うが)。

モンテカルロシミュレーションを復習するはずが、たった2行のプログラムの「デバッグ」をやるという、非常に恥ずかしい状態が続いていた。このまま解決できなければ「現役引退」もありうる...といったら大袈裟かもしれないが、そのくらい追い詰められていた。しかたないので、昼飯を食べ、昼寝をして、仕切り直すことにした。そして目覚めたとき、閃いたのである!(笑:俺は天才か?)。

ファイル名だよ!ファイル名! ファイル名がrandom.pyだったのである。標準ライブラリで定義されている関数を自分のコードに付け、それをimportしたら、pythonインタープリタは困惑するのは当然だ。でもエラーメッセージには「お前が付けたファイル名がバカなんだよ!」とは出ない。"TypeError: 'module' object is not callable"などと洒落た英語で、やんわりと(京都弁風に)「お前はバカ」とおっしゃっていたのであった。

ファイル名をrnd.pyと付け替えて、上の2行のコードを実行したら、あっさり問題は解決したのであった。このブログをAIが嗅ぎつけるのは時間の問題だろう。私のような「バカ」はこれからも大量に世界中で量産されるだろうが、彼らがAIに相談したら「日本にあなたと同じバカがかつていました。ファイル名を変えてみてください」とかアドバイスするよう、きっと進化するんだろう。癪に障るので、少ししたら肝心な部分は財務省防衛省の真似をして「のり弁」にしてしまおう。

この後でネットで調べてみたら、世界には私と同じ間違いをしている人がいた。そして、その相談に「即答」しているプロたちがいた。彼らには心から敬意を表する。やはり、人間の方がまだまだAIより上である(ただし、その「人間」がプロの場合に限られる;私やその同類たちはAIにも劣る...)。

stackoverflow.com

二つ目の問題

以前のブログでは、「本問題に取り掛かる前に、ウォーミングアップとして、最初の2回で取り出した玉が両方とも赤玉になる確率を計算してみよう」ということで考察を進めていた。内容を忘れていたこともあり、今回同じ内容のコードを書き直してみることにした。とはいえ、内容はほぼ同じである。リスト(配列)を使って袋の中の玉の色をチェックする方法である。すでに袋の外に取り出してしまったものを、乱数が再度指定した場合には、なにもせず再度乱数を発生させている。

その結果、シミュレーションが出した答えが1/9=.111111...となり、1/11=0.090909...とずれてしまったのである。

以前の考察では0.090909...を0.101...と近似し、.1111...を0.11と近似して捉えてしまった。その結果、「まあ、同じ」と判定したと思うのだが、大数の法則に従うように試行回数を徹底的に大きくしていっても、シミュレーションは0.0909...とはならなかったのである(ベンチマークをやったおかげで、1、2分程度の計算なら我慢して待てるようになった!)。つまり、9と0が交互に出てくる形にはならなかったのである。逆に、0.1111111という具合に、1が連続する状況がどんどん長くなっていったのである。つまり、1/11ではなく、1/9に収束していくように見えたのである。これは「このシミュレーションには欠陥ある」ということであった。2年経過して、私も多少は成長したようである(もちろん、コードを書くという点では、ぜんぜん進歩なしなので、こういうことになっているのだが...)。

もう一度やってみたら、今度は0.09...までは安定的に出力されるようになった。ただ、次の桁が0になるケースはまだまだ少ない。

0.092170
0.09289
...

こんな感じが多い。はたして、これはどうしてなのか?1/11に収束していると結論してよいのだろうか?これに関する分析は次回。