end0tknr's kipple - web写経開発

太宰府天満宮の狛犬って、妙にカワイイ

FSM (有限ステートマシン) からの behavior tree

先日の FSM / ステートパターン のエントリで扱った例を behavior tree で実装しようと考えていましたが、 behavior treeで扱うには、その例が簡単すぎたみたい。

end0tknr.hateblo.jp

なので、 behavior tree の簡単なまとめだけを記載しておきます。

決定木( decision tree )と異なり、 Sequence(AND)やSelector(OR)等の多様なノードがある点で、 behavior tree の方が多機能ですね。

unreal engineでは、behavior tree のguiなエディタがあるみたいですけど、 同様の問題はprologでも解けそうですね。

参考url

niconare.nicovideo.jp

www.slideshare.net

代表的なノード

f:id:end0tknr:20170701105532p:plain

サンプル

f:id:end0tknr:20170701114612p:plain

f:id:end0tknr:20170701114614p:plain

behavior tree の長所/短所

  • ◯ 状態管理は複雑になってもFSMより管理が簡単
  • ◯ 全体像を見渡せる
  • × 全てのノードを探索する場合があり、CPU負荷:高

Re: 旋回しながら追いかける動き（操舵行動 / 追跡 = Steering Behaviors / Seek）

操舵行動って、オライリーの「実例で学ぶゲームAIプログラミング」に記載されていたものですね。

p5.js は、利用したことありませんが、分かりやすい!!

qiita.com

ちなみに「実例で学ぶゲームAIプログラミング」では、操舵行動の中で - 探索(Seek) - 逃走(Flee) - 到着(Arrive) - 追跡(Pursuit) - 逃避(Evade) - 徘徊(Wander) - 障害物回避(ObstancleAvoidance) - 壁回避(WallAvoidance) - 介入(Interpose) - 隠身(Hide) - 経路追従(FollowPath) - オフセット追跡(OffsetPursuit) を具体的なコード付で紹介しています

GoFのステートパターンの振り返り ( ≒ FSM ? )

有限ステートマシン(FSM)を実装しようと思ったら、そもそも理解できていなかったようですので、GoFデザインパターンを振り返り

参考にさせて頂いたurl

私が探した範囲では、次のurlが分かりやすいように思えます。 また、このエントリの内容も、このurlの写経です。

labo.mamezou.com

ヒーターをサンプルに利用

f:id:end0tknr:20170626104708p:plain

f:id:end0tknr:20170626104714p:plain

これの GoFステートチャート

以下の通り f:id:end0tknr:20170626104730p:plain

これの クラス図

以下の通り f:id:end0tknr:20170626104746p:plain

historyやサブ状態を有するステートパターンは次回

以下は、気が向いたら… f:id:end0tknr:20170626104757p:plain

DBI for perl でのトランザクション管理は、begin_work, commit, rollback

$dbh->{AutoCommit} と紹介しているところもありますが…

http://search.cpan.org/perldoc?DBI

↑こちらに記載されている通り、基本は、 $dbh->begin_work, $dbh->commit, $dbh->rollback　。

↓gihyo.jpにも同様に記載されています。

gihyo.jp

線形代数 : 行列式とサラスの公式、そしてクラメル式によるn元1次連立方程式の解

「1次連立方程式の解」について「掃き出し法」は知ってましたが、 「クラメル式」は知らなかった(or すっかり忘れてた)のでメモ。

2次行列の行列式

{\bf{A}} = \left( \begin{array}{cc} {a} & {b} \\\ {c} & {d} \end{array} \right)

について、 \displaystyle \left| \bf{A} \right| = ad - bc

3次行列の行列式 (サラスの公式、4次以上もOK)

\displaystyle \left| \bf{A} \right| = a_{11}a_{22}a_{33} + a_{12}a_{23}a_{31} + a_{13}a_{21}a_{32} - a_{13}a_{22}a_{31} - a_{11}a_{23}a_{32} - a_{12}a_{21}a_{33}

f:id:end0tknr:20170617090330p:plain

クラメル式によるn元1次連立方程式の解

\displaystyle \left( \begin{array}{cccc} a_{11} & a_{12} & \cdots & a_{1n} \\\ a_{21} & a_{22} & \cdots & a_{2n} \\\ \vdots & \vdots & \ddots & \vdots \\\ a_{n1} & a_{n2} & \cdots & a_{nn} \end{array} \right) \left( \begin{array}{c} x_{1} \\\ x_{2} \\\ \vdots \\\ x_{n} \end{array} \right) = \left( \begin{array}{c} b_{1} \\\ b_{2} \\\ \vdots \\\ b_{n} \end{array} \right)

\displaystyle \left| \bf{A} \right| ≠ 0 のとき、上記の解は次のように行列式により算出できる。

\displaystyle \underline{ x_i = \frac { \left| \bf{A_i} \right| }{ \left| \bf{A} \right| } } 　ただし、i = 1～n。 また、Aiは、次のようにi列目をbに置換したもの

\displaystyle \left| \bf{A_i} \right| = \left| \begin{array}{cccccc} a_{11} & a_{12} & \cdots & b_{1} & \cdots & a_{1n} \\\ a_{21} & a_{22} & \cdots & b_{2} & \cdots & a_{2n} \\\ \vdots & \vdots & \ddots & \vdots & & \vdots \\\ a_{n1} & a_{n2} & \cdots & b_{n} & \cdots & a_{nn} \end{array} \right|

線形代数 : 空間座標における直線式と平面式

直線

点A(x1, y1, z1)を通り、方向ベクトル:dの場合

\displaystyle \underline{ \bf{p} = \bf{a} + t \cdot \bf{d} }

ただし、 { \bf{p} = \left( \begin{array}{c} x \\ y \\ z \end{array} \right) } 、 { \bf{a} = \vec{OA} = \left( \begin{array}{c} x_1 \\ y_1 \\ z_1 \end{array} \right) } 、t は媒介変数、 { \bf{d} = \left( \begin{array}{c} l \\ m \\ n \end{array} \right) }

l≠0 m≠0 n≠0 のとき

\displaystyle \frac{x - x_1}{l} = \frac{y - y_1}{m} = \frac{z - z_1}{n}

平面

点A(x1, y1, z1)を通り、ベクトル:d1, d2 を張る場合

\displaystyle \underline{ \bf{p} = \bf{a} + s \cdot \bf{d_1} + t \cdot \bf{d_2} }

ただし、 { \bf{p} = \left( \begin{array}{c} x \\ y \\ z \end{array} \right) } 、 { \bf{a} = \vec{OA} = \left( \begin{array}{c} x_1 \\ y_1 \\ z_1 \end{array} \right) } 、s , t は媒介変数、 { \bf{d_1} = \left( \begin{array}{c} l_1 \\ m_1 \\ n_1 \end{array} \right) } 、 { \bf{d_2} = \left( \begin{array}{c} l_2 \\ m_2 \\ n_2 \end{array} \right) }

また、点Aを通り、法線ベクトル: h =(a b c)の場合

\displaystyle \underline{ a \cdot (x - x_1) + b \cdot (y - y_1) + c \cdot (z - z_1) = 0}

回帰分析における寄与率(=決定係数)と、残差や相関係数との関係

先程のエントリにも記載していますが、 「寄与率」は回帰分析にもあり、それを混同していたので、再整理。

f:id:end0tknr:20170521193847g:plain

寄与率(=決定係数) の定義式

総平方和： S_T = \sum_{i=1}^{n} (y_{i} - \overline{y} )^{2}

ここで、 y_{i} は実測値で、 \overline{y} は実測値の総平均。

残差平方和： S_E = \sum_{i=1}^{n} (y_{i} - \hat{y_{i}} )^{2}

ここで、 \hat{y} はモデル値(予測値)。

これらを用いて、寄与率(=決定係数)は次のように定義されています。

寄与率(決定係数)： R^{2} = \frac{ S_T - S_E }{ S_T }

また、上記の「回帰による平方和」を利用し、次のように表すことが可能です。

回帰による平方和： S_R = \sum_{i=1}^{n} (\hat{y_{i}} - y_{i})^{2}
寄与率(決定係数)： R^{2} = \frac{ S_R }{ S_T } = \frac{ S_T - S_E }{ S_T } = 1 - \frac{S_E}{S_T}

寄与率(=決定係数) は、なぜ Rの2乗で表すか?

相関係数であるRと、寄与率(=決定係数)の間に2乗の関係があることが理由のようです。

更に…自由度修正済み寄与率

先程、記載した寄与率は説明変数が増える程、上昇するらしい。 (実際の説明力の有無に関らず、寄与率が増加…)

そこで「自由度」を考慮し修正した「自由度修正済み寄与率」があるらしい。(以下)

自由度修正済み寄与率( R^{2} ) ： R^{2} = 1 - \frac{ \frac{残差の平方和}{残差の自由度} } { \frac{総平方和}{ n - 1} }

ただし、 n=データ数、残差の自由度 = データ数(n) - 説明変数の数 - 1

寄与度/寄与率 : データ全体(合計)の"変化"に対する各構成要素の貢献度

寄与度の定義

「全体の"変化"に対する」がポイントで、 年度の総売上額に対する部門Aの寄与度/寄与率は次式で算出できます。

部門Aのt年の寄与度 = \frac{ 部門Aのt年売上 - 部門Aの(t-1)年売上 }{ (t-1)年総売上額 } \\\ 　または　 { 部門Aのt年成長率 \cdot 部門Aの(t-1)年構成比率 }
部門Aのt年の寄与率 = \frac{ 部門Aのt年寄与度 }{ 総額のt年成長率 }

例題

例として、年度の総売上額に対する部門A～Cの寄与度/寄与率を算出します。

年度 部門A 部門B 部門C 総額
2011 500 300 200 1000
2012 600 300 400 1300
2013 800 500 300 1600
2014 1000 600 400 2000

年度毎の変化

まず、上記の表から年度毎の変化を整理します

年度<-前年 部門A 部門B 部門C 総額
2012<-2011 100 0 200 300
2013<-2012 200 200 -100 300
2014<-2013 200 100 100 400

寄与度

次に寄与度を算出しますが、 例えば、部門Aの2012年寄与度は「(600-500)/1000 = 0.1」です。 他部門や他年度も同様に寄与度を計算すると次のようになります。

年度<-前年 部門A 部門B 部門C
2012<-2011 0.10 0.0 0.20
2013<-2012 0.15 0.15 -0.08
2014<-2013 0.13 0.06 0.06

寄与率

まず、総額成長率( (t年売上 - (t-1)年売上) / (t-1)年売上 )を算出します。

年度<-前年 総額成長率
2012<-2011 0.30
2013<-2012 0.23
2014<-2013 0.25

寄与率は「部門の寄与度」と「総額の成長率」により算出され、 例えば部門Aの2012年寄与率は、0.1x0.3=0.03となります。 他部門や他年度も同様に寄与率を計算すると次のようになります。

年度<-前年 部門A 部門B 部門C
2012<-2011 0.03 0.0 0.06
2013<-2012 0.03 0.03 -0.02
2014<-2013 0.03 0.02 0.02

固有値、固有ベクトル

主成分分析に利用する為、おさらい。

その他、シュレーディンガー方程式(量子力学)、マルコフ連鎖、グラフ理論 でも利用されるらしいが、対角行列に変換できることに関係するのかな?、まっ、今回は単なるおさらいなので、気にしませんが

定義

n次正方行列Aに対し、 A \textbf{x} = \lambda \textbf{x} が成立するとき、定数:λを「固有値」、 ベクトル \textbf{x} を「固有ベクトル」

固有値、固有ベクトル の算出例

\left( \begin{array}{cc} 8 , 1 \\ 4 , 5 \end{array} \right) の固有値、固有ベクトルを算出する。

まず、 \left| A - \lambda E \right| = 0 の行列式を解き、固有値を求める。

\left| \begin{array}{cc} {8 - \lambda} & {1} \\\ {4} & {5 - \lambda} \end{array} \right| = 0
(8 - \lambda)(5 - \lambda) - 4 = 0
\lambda^{2} - 13 \lambda + 36 = 0
\underline{ \lambda = 4 , 9 }

次に λ = 4 , 9 に対応するそれぞれの固有ベクトルを求める。

まずは「λ = 4」の場合

\left( \begin{array}{cc} {8 - 4} & {1} \\\ {4} & {5 - 4} \end{array} \right) \left( \begin{array}{c} x_1 \\\ x_2 \end{array} \right) = 0
\left( \begin{array}{cc} {4} & {1} \\\ {4} & {1} \end{array} \right) \left( \begin{array}{c} x_1 \\\ x_2 \end{array} \right) = 0
4 x_{1} + x_{2} = 0

よって、「λ = 4」に対応する固有ベクトルは t \left( \begin{array}{c} {1} \\ {-4} \end{array} \right) 　※ただし、tは0以外の任意数。

次に「λ = 9」の場合

\left( \begin{array}{cc} {8 - 9} & {1} \\\ {4} & {5 - 9} \end{array} \right) \left( \begin{array}{c} x_1 \\\ x_2 \end{array} \right) = 0
\left( \begin{array}{cc} {-1} & {1} \\\ {4} & {-4} \end{array} \right) \left( \begin{array}{c} x_1 \\\ x_2 \end{array} \right) = 0
\begin{cases} - x_{1} + x_{2} = 0 \\\ 4 x_{1} -4 x_{2} = 0 \end{cases}

よって、「λ = 9」に対応する固有ベクトルは t \left( \begin{array}{c} {1} \\ {1} \end{array} \right) 　※ただし、tは0以外の任意数。

正弦定理の証明

正弦定理は、なんとか…記憶にありましたが、余弦定理のついでに

正弦定理とは?

f:id:end0tknr:20170514175841p:plain

\frac {a}{sin A} = \frac {b}{sin B} = \frac {c}{sin C} = 2R 　ただし、Rは外接円の半径。

正弦定理の証明

先程の余弦定理と同様、∠Aが鋭角,直角,鈍角に分け、導出します

(正弦)鋭角

f:id:end0tknr:20170514180317p:plain

まず、点Bと円の中心を通るBDを描くと、 BDは円の中心を通る為、△BCDは直角三角形 となります。

また、a を共有する為、∠A = ∠D でもあります。

ここで、sin BDC を求めると、 sin BDC = \frac{BC}{BD} = \frac{a}{2R} となり、最終的に正弦定理を導出できます。

sin A = \frac{a}{2R} \rightarrow \underline{2R = \frac{a}{sin A}}

(正弦)直角

f:id:end0tknr:20170514191350p:plain

上図の通り、a = 2R で、また、sin A = sin 90 = 1 の為、以下が成り立つ。

\underline{2R = \frac{a}{sin A}}

(正弦)鈍角

f:id:end0tknr:20170514191700p:plain

上図のように、円の中心を通るBDを描くと、 □ABCDは外周円を持つ為、∠A + ∠D = 180度。

ここで、sin Dを求めると、以下のように正弦定理を導出できます。

sin D = \frac{BC}{BD} = \frac{a}{2R}
sin (180 - A) = \frac{a}{2R}
\underline{ sin A = \frac{a}{2R} }

余弦定理の証明

こうも忘れていると「そもそも当時、理解してたの?」と思いますが、 余弦定理と正弦定理もすっかり忘れていたので、以下、自分用メモ。 まずは、余弦定理から

余弦定理とは?

f:id:end0tknr:20170514170556p:plain

\displaystyle a^{2} = b^{2} + c^{2} - 2bc \cdot cos A
\displaystyle b^{2} = a^{2} + c^{2} - 2ac \cdot cos B
\displaystyle c^{2} = a^{2} + b^{2} - 2ab \cdot cos C

余弦定理の証明

∠Aが鋭角,直角,鈍角に分け、導出します

(余弦)鋭角

f:id:end0tknr:20170514171207p:plain

上記のように補助線CHを描くと、CH, BHは次のように表せる。

CH = b \cdot sin A , BH = c - b \cdot cos A …(1)

また、△BCHは直角三角形である為、ピタゴラスの定理(三平方の定理)から BC^{2} = CH^{2} + BH^{2} …(2)が成立する。

式(2)へ式(1)を代入し変形すると、余弦定理の式が導出できる。

BC^{2} = (b \cdot sin A)^{2} + (c - b \cdot cos A)^{2}
a^{2} = (b^{2} \cdot sin^{2} A) + (c^{2} - 2 bc \cdot cos A + b^{2} \cdot cos^{2} A)
a^{2} = b^{2} (sin^{2} A + cos^{2} A) + c^{2} - 2 bc \cdot cos A
\underline{ a^{2} = b^{2} + c^{2} - 2 bc \cdot cos A }

(余弦)直角

f:id:end0tknr:20170514173423p:plain

また、△ABCは直角三角形である為、先程と同様、 ピタゴラスの定理(三平方の定理)を用います。

a^{2} = b^{2} + c^{2}

また、∠A=90度 のとき、cos A=0 となる為、次の式が成立します。

\underline{ a^{2} = b^{2} + c^{2} - 2 bc \cdot cos A }

(余弦)鈍角

f:id:end0tknr:20170514173853p:plain

まず、直角三角形 BCHに対し、ピタゴラスの定理(三平方の定理)を用います。

BC^{2} = BH^{2} + CH^{2} …(1)

また、

sin (180-A) = \frac{CH}{b} \rightarrow CH = b \cdot sin (180 - A) \rightarrow CH = b \cdot sin A …(2)
BH = BA + AH = c + (b \cdot cos(180 - A)) = c - b \cdot cos A …(3)

最後に式(2)(3)を式(1)へ代入し、変形すると、余弦定理の式が導出できます。

a^{2} = ( b \cdot sin A )^{2} + ( c - b \cdot cos A )^{2}
a^{2} = ( b^{2} \cdot sin^{2} A ) + ( c^{2} - 2bc \cdot cos A + b^{2} \cdot cos^{2} A )
a^{2} = b^{2} (sin^{2} A + cos^{2} A ) + c^{2} - 2bc \cdot cos A
\underline{ a^{2} = b^{2} + c^{2} - 2bc \cdot cos A }

ベクトルの内積、内積の成分表示、シュミットの正規直交化法

シュミットの正規直交化法をすっかり忘れていたので、基本からのメモ

内積の定義

\displaystyle \textbf{a} \cdot \textbf{b} = \|a\| \cdot \|b\| \cdot cos \theta

※ \displaystyle ||a|| や \displaystyle ||b|| は、ベクトルの大きさ(ノルム)

内積の成分表示

2次元ベクトル

\displaystyle \textbf{a} = \begin{pmatrix} x_{1} \\\ y_{1} \end{pmatrix} , \textbf{b} = \begin{pmatrix} x_{2} \\\ y_{2} \end{pmatrix} \rightarrow \textbf{a} \cdot \textbf{b} = x_{1}x_{2} + y_{1}y_{2}

3次元ベクトル

\displaystyle \textbf{a} = \begin{pmatrix} x_{1} \\\ y_{1} \\\ z_{1} \end{pmatrix} , \textbf{b} = \begin{pmatrix} x_{2} \\\ y_{2} \\\ z_{2} \end{pmatrix} \rightarrow \textbf{a} \cdot \textbf{b} = x_{1}x_{2} + y_{1}y_{2} + z_{1}z_{2}

内積の成分表示の証明(2次元ベクトルにおける導出)

f:id:end0tknr:20170514085717p:plain bの反対ベクトル(-b)とで形成される△ADEで 三平方の定理(ピタゴラスの定理)を考える。

\displaystyle{ AE^2 = AD^2 + DE^2 }
\displaystyle{ \|a - b\|^2 = ( \|a\| + \|b\| cos\theta )^2 + ( \|b\| sin\theta )^2 }
\displaystyle{ \|a - b\|^2 = (\|a\|^2 + 2\|a\|\|b\|cos\theta + (\|b\|cos\theta)^2) + (\|b\|sin\theta)^2 …(1) }
\displaystyle{ \|a - b\|^2 = \|a\|^2 + 2\textbf{a} \cdot \textbf{b} + \|b\|^2 …(2) }

※式(1)→(2)の変形では、前述の内積の定義式や sin^{2} \theta + cos^{2}\theta = 1 を利用してます。

更に \displaystyle{ |a - b| = \begin{pmatrix} x_1 - x_2 \\ y_1 - y_2 \end{pmatrix} } も利用し、式(2)を更に変形し、完成。

\displaystyle{ (x_1 - x_2)^2 + (y_1 - y_2 )^2 = (x_{1}^2 + y_{1}^2) + 2\textbf{a} \cdot \textbf{b} + (x_{2}^2 + y_{2}^2) }
\displaystyle{ (x_{1}^2 - 2{x_1}{x_2} + x_{2}^2) + (y_{1}^2 - 2{y_1}{y_2} + y_{2}^2)= (x_{1}^2 + y_{1}^2) + 2\textbf{a} \cdot \textbf{b} + (x_{2}^2 + y_{2}^2) }
\displaystyle{ - 2{x_1}{x_2} - 2{y_1}{y_2} = 2\textbf{a} \cdot \textbf{b} }
\displaystyle{ \underline{ \textbf{a} \cdot \textbf{b} = {x_1}{x_2} + {y_1}{y_2} } }

シュミットの正規直交化法

今回は、シュミットの正規直交化法へつながる 「ベクトルa, bが与えられたときのaと垂直なベクトル」である

\displaystyle{ \underline{ \textbf{b} - \frac{ \textbf{a} \cdot \textbf{b}}{ \|a\|^2 } \textbf{a} } }

を導出します。

f:id:end0tknr:20170514101355p:plain

上図より、aと垂直なベクトル( \displaystyle{ \overrightarrow{BD} } )は、次のように表せる。

\displaystyle{ \textbf{b} - \frac{\|b\| cos\theta}{\|a\|} \textbf{a} …(1) = \textbf{b} - \frac{ \|a\|\|b\| cos\theta}{\|a\|^2} \textbf{a} …(2) = \underline{ \textbf{b} - \frac{ \textbf{a} \cdot \textbf{b} }{\|a\|^2} \textbf{a} …(3) } }

※(1)->(2)の変形では、2項の分母分子のそれぞれにベクトルaのノルムを掛け、 (2)->(3)の変形では、内積の定義式を利用しています