雑記: fastText のチュートリアルをやるだけ

インストール

以下の記事にしたがうと Ubuntu on Windows Subsystem for LinuxfastText をインストールできます。

以下のコマンドで usage が出てくればインストールできていると思います。

./fasttext

出てくる usage をみると、fasttext コマンドには以下のモードがあるようです(空欄は書き途中)。公式のチートシートCheatsheet · fastText )も参照してください。

supervisedラベル付きの教師データから分類器を学習する(オプション: たくさんあって例えば以下)。
  • -dim: 単語ベクトルの次元数(デフォルト 100)。
  • -lr: 学習率(デフォルト 0.1)。
  • -epoch: エポック数(デフォルト 5)。
上のようなハイパーパラメータはオートチューニングさせることもできる。オートチューニングに関するオプションは以下。
  • -autotune-validation: これに評価用データを渡すとオートチューニングする。
  • -autotune-duration: オートチューニングの探索時間(秒)。
  • -autotune-modelsize: モデルサイズを制限するとき指定する(Ex. 2M)。
quantizeラベル付きの教師データから分類器を学習する(オプション: たくさん)。メモリ使用量を減らすためモデルを量子化するバージョン。
test学習した分類器と任意のデータに対して精度と感度を出す(オプション: 予測ラベル数、予測確率の閾値)。
test-label学習した分類器と任意のデータに対してラベルごとに精度と感度を出す(オプション: 予測ラベル数、予測確率の閾値)。
predict学習した分類器で予測する(オプション: 予測ラベル数、予測確率の閾値)。
predict-prob学習した分類器で予測する(予測ラベルだけでなく確率値も出力する)(オプション: 予測ラベル数、予測確率の閾値)。
skipgramskipgram アルゴリズムで単語ベクトルを学習する(オプション: たくさん)。
cbowcbow アルゴリズムで単語ベクトルを学習する(オプション: たくさん)。
print-word-vectors学習した分類器と任意のデータに対してデータに含まれる単語のベクトルを出力する。
print-sentence-vectors学習した分類器と任意のデータに対してデータに含まれる文章の平均ベクトルを出力する。
print-ngrams
nn学習した分類器に対して指定した単語の nearest neighbors を表示する(オプション: 上位何件表示するか)。
analogies学習した分類器に対して指定した 単語A - 単語B + 単語C の nearest neighbors を表示する(オプション: 上位何件表示するか)。
dump学習した分類器から情報をダンプする(オプション: args, dict, input, output)。

複数のラベルが付いた文章を分類する

公式のチュートリアルをやります。

データの取得
上のページの Getting and preparing the data に倣ってまずデータをダウンロードします。

wget https://dl.fbaipublicfiles.com/fasttext/data/cooking.stackexchange.tar.gz && tar xvzf cooking.stackexchange.tar.gz

readme.txt を読むとこれは以下のサイトのデータとのことです。料理に関する質問サイトのようです。個々の質問にはいくつかのタグがついています(このタグがデータのラベルに対応しています)。

cooking.stackexchange.txt をみると、15404 行あって、以下のように各行が「ラベル1 ラベル2 文章」のようになっています(ラベルの数は不定)。複数のラベルが付いた学習データのようです。__label__ というのは fasttext がラベルと認識してくれるプレフィックスです(supervised モードの -label オプションで異なるプレフィックスも指定できます)。このようなデータを自分で用意すれば自分のデータも学習できます(日本語の場合は単語ごとにわかち書きしておく必要がありますが)。

__label__sauce __label__cheese How much does potato starch affect a cheese sauce recipe?
__label__food-safety __label__acidity Dangerous pathogens capable of growing in acidic environments
__label__cast-iron __label__stove How do I cover up the white spots on my cast iron stove?

チュートリアルでは最初の 12404 行を訓練用データ、最後の 3000 行を評価用データに切り分けているのでそれに倣います。

head -n 12404 cooking.stackexchange.txt > cooking.train
tail -n 3000 cooking.stackexchange.txt > cooking.valid

分類器の学習
文章のラベルを予測する分類器を学習します。supervised モードで以下のように実行します。

fasttext=/mnt/c/linux_home/fastText/fasttext
$fasttext supervised -input data/cooking.train -output model_cooking

以下のように学習が進み、model_cooking.bin と model_cooking.vec が生成されます。

Read 0M words
Number of words:  14543
Number of labels: 735
Progress: 100.0% words/sec/thread:   10556 lr:  0.000000 avg.loss: 10.200933 ETA:   0h 0m 0s

生成された model_cooking.vec の中身をみてみます。1行目は「14543 単語を 100 次元ベクトルに埋め込んだ」という意味です。実際、3行目は to という単語のベクトル表現、4行目は a という単語のベクトル表現です。となると、2行目は </s> という単語のベクトル表現にみえますが、</s> は実際の単語ではないです。これについては後述します。

14543 100
</s> -0.19674 0.79774 -0.32248 -0.48751 0.81991 0.44264 0.023684 -0.13507 0.93978 0.9933 -0.51045 0.1542 0.30656 0.7901 -0.37725 -0.11613 0.068653 0.16041 0.0173 -0.55148 -0.026323 0.75483 0.50935 -0.52323 0.0079467 -0.61519 0.48465 -0.63781 -0.40468 0.98114 -0.36877 -0.16163 -0.74467 -0.72118 -1.0947 0.037487 0.105 -0.61662 -0.16637 -0.3349 0.34562 0.90722 0.26701 0.58475 0.27875 -0.080856 0.067838 -0.22352 -0.48386 0.45114 -0.95859 0.62402 -0.82272 0.63454 -0.15089 -0.32259 -0.031502 0.26261 0.65062 0.36968 -0.4895 0.5752 1.0421 0.72295 -0.30713 -0.01582 -0.7944 0.30934 0.16335 0.42403 -0.88169 0.29987 -0.094941 -0.052784 -0.13877 -0.0081362 0.9565 0.76743 0.34506 -0.36395 -0.29721 0.442 0.93896 -0.53675 0.10719 -0.44839 0.20822 0.49516 -0.47837 -0.2682 0.86738 0.34557 1.3461 -0.83188 -0.17911 -1.0894 0.054833 0.7003 -0.56919 -0.45242
to -0.067108 0.39705 -0.16521 -0.26775 0.43871 0.27861 -0.034769 -0.096002 0.41407 0.4458 -0.075386 0.090708 0.052289 0.30679 -0.1375 -0.02269 0.017723 0.056648 -0.090194 -0.23134 0.064546 0.33595 0.14719 -0.16548 -0.025145 -0.26569 0.17582 -0.21569 -0.19566 0.32286 -0.12209 -0.091952 -0.31513 -0.29806 -0.42302 -0.021129 -0.0080154 -0.27211 -0.085119 -0.14138 0.15414 0.40777 0.067376 0.23067 0.12346 -0.0075088 0.00037916 -0.1155 -0.22735 0.13175 -0.42807 0.242 -0.3053 0.22256 -0.10684 -0.19737 -0.083466 0.12622 0.33479 0.14673 -0.14189 0.19358 0.41584 0.24277 -0.056506 0.024699 -0.39026 0.11678 0.056295 0.1298 -0.32616 0.14656 0.020648 -0.066931 -0.074845 -0.088811 0.37498 0.31593 0.18227 -0.1315 -0.10712 0.17731 0.38733 -0.14194 0.0040193 -0.19983 0.052696 0.14076 -0.23756 -0.10201 0.35857 0.12664 0.536 -0.37403 -0.0038928 -0.44641 0.071153 0.24687 -0.25552 -0.14378
a 0.012492 0.17169 -0.06459 -0.16798 0.2584 0.047045 -0.077651 -0.12495 0.29964 0.30246 -0.2987 0.047268 0.065618 0.16571 -0.17125 -0.06577 0.053795 0.052671 -0.016843 -0.10435 -0.0035953 0.18633 0.121 -0.11621 0.030406 -0.19042 0.19844 -0.3123 -0.22215 0.39258 -0.16879 0.02168 -0.22376 -0.3151 -0.52275 -0.025202 -0.10059 -0.13855 0.037249 -0.020664 -0.041001 0.38875 0.15119 0.21119 0.13383 -0.074202 0.1663 -0.033014 -0.13108 0.3875 -0.3598 0.23587 -0.29794 0.27076 -0.062832 0.037349 -0.051845 0.04353 0.14301 0.14153 -0.078114 0.35326 0.47126 0.32361 -0.26027 -0.056849 -0.27632 0.081134 0.093328 0.0080092 -0.20814 0.14146 -0.092766 -0.016157 -0.022588 0.092956 0.37898 0.20713 0.14062 -0.10115 -0.035477 0.14569 0.29206 -0.27978 0.040004 -0.18043 0.12128 0.23777 -0.10417 -0.08892 0.28171 0.14071 0.58662 -0.28369 -0.12543 -0.3648 -0.037512 0.31876 -0.089494 -0.21092

model_cooking.bin の方はバイナリなので中身を直接読めませんが、dump モードで情報を表示させることができます。args という引数を渡すと以下のように学習の設定が表示できます。

$fasttext dump model_cooking.bin args
dim 100   # 単語ベクトルの次元数
ws 5   # ウィンドウサイズ(supervised ではこの値は使われないらしい ※)
epoch 5   # エポック数
minCount 1   # 登場回数がこの数未満の単語は無視
neg 5    # 負例のサンプリング数(ベクトル表現を学習するとき中心語と文脈語の対かどうかの識別器を学習するのでそれだと思う)
wordNgrams 1
loss softmax
model sup
bucket 0
minn 0
maxn 0
lrUpdateRate 100
t 0.0001

※ については以下のスライドを拝見しました。

args の代わりに dict と指定すると訓練させたデータに含まれていた単語やラベルの集計が表示されます。input と指定すると数値が大量に表示されますが、これは model_cooking.vec と同一で、モデルが学習したベクトル表現のようです。output と指定するとやはり数値が大量に表示されます。これは正確に調べていませんが、fastText は多項ロジスティック回帰によって分類しているらしいので、その係数なのではないかと思います。

分類器による予測
学習した model_cooking.bin で実際に予測するには predict モードと predict-prob モードを使います。predict モードだと予測ラベルのみ出力されますが、predict-prob モードではラベルの確率値も一緒に出力されます。

$fasttext predict model_cooking.bin data/cooking.train > predicted_label.train
$fasttext predict model_cooking.bin data/cooking.valid > predicted_label.valid

データの代わりに - を引数に渡すと、タイプした文章にインタラクティブにラベルを予測してくれます。また、予測ラベル数や予測確率の閾値を指定することもできます。例えば predict モードで予測ラベル数を 3 に指定すると以下です。

$fasttext predict model_cooking.bin - 3
How much does potato starch affect a cheese sauce recipe?
__label__baking __label__food-safety __label__bread

predict-prob モードだと以下です。確率値も出ます。

$fasttext predict-prob model_cooking.bin - 3
How much does potato starch affect a cheese sauce recipe?
__label__baking 0.023058 __label__food-safety 0.0222845 __label__bread 0.0182505

最大のラベルでも 0.023 というのは小さいですね(といってもラベルは 735 個ありますが)。あとこのデータの真の正解ラベルである sauce も cheese も上位3件に入っていないですね…。

分類器の評価
test モードで分類器を評価できます。訓練データに対する評価は以下です。

$fasttext test model_cooking.bin data/cooking.train
N       12404
P@1     0.136
R@1     0.0589

評価データに対する評価は以下です。指標の値は訓練データに対するそれと近い気がします。

$fasttext test model_cooking.bin data/cooking.valid
N       3000
P@1     0.142
R@1     0.0613

引数に数値を渡すと P@k、R@k が計算できます。k=3 にすると k=1 より精度が下がり、感度が上がります。

$fasttext test model_cooking.bin data/cooking.train 3
N       12404
P@3     0.0819
R@3     0.107
$fasttext test model_cooking.bin data/cooking.valid 3
N       3000
P@3     0.0829
R@3     0.108

というか P@k と R@k の正確な定義がよくわかりませんが、ソースをみればいいと思います。

P@k と R@k の k は推論の際の予測ラベル数です。 各データに不定数の正解ラベルとk個の予測ラベルが付いていることになります。meter.cc の Meter::log() という関数の gold が全データの正解ラベルの総数(なぜ gold という変数名なのかわかりません)、predicted が全データの予測ラベルの総数、predictedGold が全データの予測ラベルの中でそのデータの正解ラベルに含まれていたものの総数です。そして、 P@k と R@k は

  • P@k = predictedGold / predicted
  • R@k = predictedGold / gold

です。test-label モードで実行するとラベルごとに指標が出せます。表にまとめるとこうです。

ラベル 正解ラベルにそのラベルを含むデータ数 予測ラベル(Top-k)にそのラベルを含むデータ数 予測ラベル(Top-k)にも正解ラベルにもそのラベルを含むデータ数 精度(Precision) 感度(Recall)
label1 gold1 predicted1 predictedGold1 predictedGold1 / predicted1 predictedGold1 / gold1
label2 gold2 predicted2 predictedGold2 predictedGold2 / predicted2 predictedGold2 / gold2
すべて Σ goldi Σ predictedi Σ predictedGoldi Σ predictedGoldi/ Σ predictedi Σ predictedGoldi/ Σ goldi
実際、test-label モードで実行すると以下のようにラベルごとに Precision と Recall がプリントされます。これをみると、Top-1 の予測では全てのデータが __label__baking か __label__food-safety か __label__substitutions のいずれかにしか予測されていないという事実がわかります(それ以下のラベルが全て Precision が None、Recall がゼロなので)。

$fasttext test-label model_cooking.bin data/cooking.train
F1-Score : 0.242344  Precision : 0.155056  Recall : 0.554498   __label__baking
F1-Score : 0.190454  Precision : 0.107175  Recall : 0.854188   __label__food-safety
F1-Score : 0.340326  Precision : 0.388988  Recall : 0.302486   __label__substitutions
F1-Score : 0.000000  Precision : --------  Recall : 0.000000   __label__equipment
F1-Score : 0.000000  Precision : --------  Recall : 0.000000   __label__bread
$fasttext test-label model_cooking.bin data/cooking.valid
F1-Score : 0.233992  Precision : 0.151484  Recall : 0.513889   __label__baking
F1-Score : 0.205660  Precision : 0.116205  Recall : 0.893443   __label__food-safety
F1-Score : 0.344023  Precision : 0.401361  Recall : 0.301020   __label__substitutions
F1-Score : 0.000000  Precision : --------  Recall : 0.000000   __label__equipment
F1-Score : 0.000000  Precision : --------  Recall : 0.000000   __label__bread

その他の機能
print-word-vectors モードでは、学習した分類器を指定して標準入力から適当なデータ(単語、単語列、文章)を渡すと、そのデータに含まれる単語のベクトルを出力します。

$fasttext print-word-vectors model_cooking.bin < data/cooking.valid   # ファイルから
$fasttext print-word-vectors model_cooking.bin   # インタラクティブ
How much does potato starch affect a cheese sauce recipe?
How 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
much 0.22722 0.91002 -0.84094 0.30225 -0.30555 -0.20168 -0.21758 -0.6925 0.050714 1.0291 0.18715 -0.4157 0.46272 -0.70559 0.73065 -0.31759 -1.1065 0.33034 -0.32165 0.042642 0.14589 0.46961 0.45965 0.67638 -1.1002 -1.2409 0.36938 -0.90074 0.20934 1.4298 1.3984 -0.82588 0.10168 1.2704 -0.86179 0.96689 -1.0505 0.11038 -0.42924 -0.049286 -0.19397 0.98325 -0.56746 -1.0483 -0.30183 -0.35669 0.042016 0.27229 0.20964 0.60953 -0.3668 -1.015 0.37869 0.33717 0.71164 -0.42239 0.022877 1.1084 1.0838 -0.87779 0.12118 0.23196 -0.20347 -0.6039 -0.21821 0.49487 -0.10744 -0.14096 -0.30951 -0.095197 0.49528 -0.51653 -0.75525 0.42532 -0.17701 -0.38641 -0.57726 0.16482 0.4644 0.4653 0.26798 0.5425 -0.37393 -0.32621 0.51616 0.57581 -0.93669 0.33229 -0.069224 -1.0827 0.059751 -0.42559 0.10031 -0.25191 0.28528 0.13178 -0.18955 -0.54339 -0.14521 -0.80504
does 0.32834 -1.19 0.54817 -0.36809 -0.19435 1.6243 -0.91674 0.15332 -0.26709 -0.014865 -0.33856 0.27598 -1.0753 0.54718 -0.63769 0.87679 0.18369 0.30915 0.37365 -0.50254 -0.96701 0.019201 0.059845 0.94462 -0.88541 -0.35104 0.034312 -0.42082 1.489 1.3392 -0.87674 -0.16115 0.83928 0.072629 0.11015 0.38114 -0.038614 -0.45594 -0.19126 1.7607 0.76206 -0.74446 -0.12468 -0.3788 -0.55383 0.083704 0.12357 -0.4626 -0.3055 0.048537 0.76693 0.76688 0.19337 0.61716 -0.82591 0.71833 0.57165 -0.76735 0.17664 -0.73828 -1.431 -0.042516 -0.16645 0.81091 -0.1387 -0.50888 0.59268 0.13015 -0.18835 0.65158 0.019614 -0.20911 -0.061807 0.58231 -0.45009 0.52177 -0.056014 -0.29689 0.37619 0.12884 -0.84277 -0.10887 0.36958 0.18755 -0.20866 -0.16468 -0.6531 0.21326 -0.039295 0.55748 0.87626 0.70385 0.32218 -0.25354 -0.11062 -0.43616 -0.71879 -0.96103 0.66443 0.14404
(略)

print-sentence-vectors モードでは、学習した分類器を指定して標準入力から適当な文章を渡すと、その文章の平均ベクトルを出力します。

$fasttext print-sentence-vectors model_cooking.bin 
How much does potato starch affect a cheese sauce recipe?
–0.017273 0.15645 -0.066831 0.16971 -0.0041063 0.21166 -0.21562 -0.23493 -0.081128 0.20374 0.0048495 0.1151 0.10965 -0.34534 -0.047381 -0.13311 0.24108 0.15479 -0.13747 -0.27368 -0.40173 0.12487 -0.10497 0.13571 0.1871 -0.36978 -0.15183 0.086557 0.075239 0.29059 -0.045744 0.012255 0.021844 0.015772 -0.1261 0.13502 -0.0162 -0.16172 0.11094 0.42339 -0.28965 0.03484 -0.063112 0.012793 -0.065129 -0.093443 0.030201 -0.045701 0.089005 -0.16689 -0.087488 -0.0070809 -0.017829 -0.016135 -0.062578 -0.083085 -0.23386 0.11845 -0.069138 0.075327 -0.14469 0.084418 -0.15946 0.18345 -0.2987 0.036661 -0.086342 0.10253 0.121 0.10054 -0.14697 0.020506 0.096789 -0.078027 0.0063817 -0.066075 0.089692 0.0079195 0.15794 0.026881 0.06317 0.17406 0.27988 -0.1954 -0.20847 -0.095213 0.27147 0.19933 -0.05129 0.21674 0.25814 0.19353 0.42013 -0.26088 0.14899 0.30501 0.045966 0.20921 0.13989 -0.21196
  • print-sentence-vectors モードを使用してみるとわかりますが、このモードで出力される文章の平均ベクトルは単純に文章中に含まれるベクトルの平均とは合わず、全ての文章に </s> なる単語が1つ足されていると考えると平均が合います。なので、</s> なる単語は意味を解釈するなら文章の区切りのようなもの(?)で、はたらきとしては文章ベクトルのオフセットのようなものだと思います。

複数のラベルが付いた文章を分類する(プレ処理とハイパーパラメータの変更)

先ほどの結果は Top-1 の全体の精度が約 14 %で感度が約 6 %でした。予測ラベルが本当に正しい割合が 14% とか、正解ラベルを検知できる割合が 6% とかはちょっと低いと思います。チュートリアルの Making the model better にならって、符号を切り離したり、全て小文字に揃えるプレ処理をしてみます。そうすると精度と感度が少しよくなります。

cd data
cat cooking.stackexchange.txt | sed -e "s/\([.\!?,'/()]\)/ \1 /g" | tr "[:upper:]" "[:lower:]" > cooking.preprocessed.txt
head -n 12404 cooking.preprocessed.txt > cooking.train
tail -n 3000 cooking.preprocessed.txt > cooking.valid
cd ..
$fasttext supervised -input data/cooking.train -output model_cooking
$fasttext test model_cooking.bin data/cooking.valid
N       3000
P@1     0.171
R@1     0.074

また、supervised モードの usage からわかるように学習のハイパーパラメータも色々あります。チュートリアルにしたがって学習率とエポック数を変更してみます。そうすると精度と感度がもっとぐっとよくなります。

$fasttext supervised -input data/cooking.train -output model_cooking -lr 1.0 -epoch 25
$fasttext test model_cooking.bin data/cooking.valid
N       3000
P@1     0.58
R@1     0.251

複数のラベルが付いた文章を分類する(オートチューニング)

ハイパーパラメータを変更すると精度がぐっとよくなることがわかりました。が、よいハイパーパラメータを探すのは面倒です。しかし幸いなことに、fastText にはオートチューニング機能が実装されました。

上のページにしたがって以下のように実行してみます。そうするとデフォルトで5分間探索するようです。

$fasttext supervised -input data/cooking.train -output model_cooking -autotune-validation data/cooking.valid
$fasttext test model_cooking.bin data/cooking.valid
N       3000
P@1     0.568
R@1     0.246

さっきより悪くなりました…。デフォルトでは f 値にフィッティングするみたいなんですが精度も感度も下がっているのでふつうにだめっぽいです。学習されたモデルの設定をダンプしてみると、まずベクトルの次元数が変わっています。

$fasttext dump model_cooking.bin args
dim 91
ws 5
epoch 100
minCount 1
neg 5
wordNgrams 3
loss softmax
model sup
bucket 2015548
minn 2
maxn 5
lrUpdateRate 100
t 0.0001

よくならないと悲しいので、ベクトルの次元数及び先ほど変更したハイパーパラメータは固定した上で、探索時間を 10 分にしてみます。そうするとさすがによくなりました。よかった。

$fasttext supervised -input data/cooking.train -dim 100 -lr 1.0 -epoch 25 -output model_cooking -autotune-validation data/cooking.valid -autotune-duration 600
$fasttext test model_cooking.bin data/cooking.valid
N       3000
P@1     0.608
R@1     0.263

このときのハイパーパラメータはこんな感じだったようです。

dim 100
ws 5
epoch 25
minCount 1
neg 5
wordNgrams 2
loss softmax
model sup
bucket 122181
minn 0
maxn 0
lrUpdateRate 100
t 0.0001

デフォルト値からずれているのは wordNgrams と bucket です。

ベイズ統計の理論と方法: ノート4章その1

以下の本を読みます。キャラクターは架空のものです。解釈の誤りは筆者に帰属します。おかしい点がありましたらコメント等でご指摘いただけますと幸いです。

ベイズ統計の理論と方法

ベイズ統計の理論と方法

書籍サポートページ
f:id:cookie-box:20190101155733p:plain:w60

気付いたんですけど、今度この章を発表するので教科書の流れにかかわらず自分の流れでまとめようと考えていたんですが、まずは教科書を読む必要があるのではないでしょうか。

f:id:cookie-box:20190101160814p:plain:w60

当たり前だよね??

f:id:cookie-box:20190101155733p:plain:w60

なので改めて4章の最初から確認していくと、定義14の(位相)多様体の定義は一般的なものですよね。定義14の中ほどの2つの式は、2つの座標近傍の重なり U^\ast 内の点について、\phi_1 座標から \phi_2 座標にする写像と、その逆の写像ですね。これらが共に C^r 級なら \mathcal{M}C^r微分多様体というんですね。

f:id:cookie-box:20190101160814p:plain:w60

以前の記事(雑記: 1の分割の話)で私そう言ったよね…。

f:id:cookie-box:20190101155733p:plain:w60

さらに解析関数なら解析多様体とありますが、この言葉この後で出てきていますかね…。ときに副部長、この定義をみると、「このようなものをアトラス(座標近傍系)という。\mathcal{M}多様体という」という文章になっていると思うのですが、これでは「いつ」「何を」多様体というのか曖昧ではありませんか? 「そのハウスドルフ空間に何かアトラスが存在するとき、そのハウスドルフ空間多様体という」のですか? それとも「ハウスドルフ空間と特定のアトラスの組を多様体という」のですか? 例えば「位相空間」といったら、「集合とある特定の開集合系の組」ですよね? であれば後者ですか?

f:id:cookie-box:20190101160814p:plain:w60

松本本の42ページに、「 C^r多様体は、位相空間 M とその上の C^r 級座標近傍系 S で決まる。したがって  C^r多様体は正確には (M, S) とかくべきものである」とある。だから C^r微分多様体については明確に後者、「ハウスドルフ空間と特定のアトラスの組」だね。 C^r微分多様体ならアトラスは  C^r 級アトラスに固定しておかないとおかしい気はするし。他方、38ページの位相多様体の定義の方は前者のような記述にみえる。こちらは「何かアトラスが存在するとき、そのハウスドルフ空間多様体という」であって、特定のアトラスをくくりつけておくわけではないっぽい。ウィキペディアの「可微分多様体」の最後の方の記述も、「微分可能多様体は」アトラスを対にするということを支持しているようにみえる。単に「多様体」といったときは「局所局所に座標がかき込めるかどうか」が大事で、「微分多様体」といったときは「なめらかにうつり合う座標がかきこまれていること」が大事なんじゃないかな。

f:id:cookie-box:20190101155733p:plain:w60

「正確には (M, S) と書くべきものである」とか「明示すると分かりやすい」とか、最初からそう書いてくださいよといった感じなんですが…そのくらい定義から理解しろということなんでしょうか。手厳しいですね。例10 の多様体の例をみると、(1) は疑いないですね。(2) は松本本の 43 ページの例1にもありましたよね。「2次元球面」といっうのは3次元空間内の、中が空洞のビーチボールのビニールの部分ですよね。これは一つのチャートで被覆することはできず、松本本の例では「北半球」と「南半球」と、「アメリカ半球(?)」と「中国半球(?)」と、「太平洋半球(?)」と「アフリカ半球(?)」の上下左右前後の6枚のチャートで覆っていますね。地球上全体に座標をふるには「北半球」と「南半球」の2枚でよさそうなのに、随分効率が悪い気がしますが…。

f:id:cookie-box:20190101160814p:plain:w60

開集合の取り方を変えれば2枚のチャートでもいけるけど、その6枚なら、「北半球」にわりふる2次元座標を「3次元空間での座標から『地軸方向』を取ったもの」にできるからね。地表の点を地軸に垂直に地球を切断した断面の円盤に射影するだけでいい。それがその地点の座標。

f:id:cookie-box:20190101155733p:plain:w60

(3) は、これは何でしょう… d=2 でイメージすると、2次元上に何か関数 K(w) があって、 K(w)=0 を満たす領域(曲線でしょうね)があるとして、ただこの曲線上で  \nabla f(w) = 0 な点がないならばこの曲線は多様体であると…え、いや、f(w) って誰ですか??

f:id:cookie-box:20190101160814p:plain:w60

この本で Kf は平均誤差と対数尤度比として使用されているけどここではそういうわけではないよね…。この f は単に K の誤植と考えれば意味は通るね。そして、K を平均誤差と考えれば、W_0 は最適なパラメータの集合に他ならない。例10の (3) はだから、「最適なパラメータの集合が『結び目』のような取り扱いにくい点をもたなければ、最適なパラメータの集合には上手く座標が入れられる」っていっているね。

f:id:cookie-box:20190101155733p:plain:w60

結び目? って何ですか? そんなことかいてませんよ?

f:id:cookie-box:20190101160814p:plain:w60

K(w)=0 上で \nabla K(w)=0 となるような点がないなら  \{w \, | \, K(w)=0\}多様体だといっているよね。 じゃあ \nabla K(w)=0 となるような点があるってどういう状況だろう。と考えると、その点 w_0 からどの方向に(微小に)逃げても、「逃げた距離の1次に比例して K(w) が大きくなる」ような方向がないんだよね。例えば以下のページにある「結び目」なんかがそうなる。2次以上でしか逃げられない。

他に、K(w)=0 となる領域が広がりをもっている場合とかも \nabla K(w)=0 となるね。

f:id:cookie-box:20190101155733p:plain:w60

その絵は… 紛れもなく結び目ですね。

f:id:cookie-box:20190101160814p:plain:w60

例10の (3) は K=0 上に \nabla K(w)=0 な点があると嫌だよね、っていいたいんだと思う。

f:id:cookie-box:20190101155733p:plain:w60

なるほど…? 次のページも例が続きますね。例11は、これは何でしょう。直和?

f:id:cookie-box:20190101160814p:plain:w60

2本の紐がある。こちらの紐とあちらの紐で、座標がかけ合わせて1になる点どうしはくっつけることにする。そうすると2本の紐はぺったりくっついていき、輪っかになる。この輪っかはハウスドルフ空間になっている。ここで輪っか上の開集合とは、2本のひもにばらしたときそれぞれのひもの上で開集合になっているような集合ね。そして2本のひもはこの輪っかのアトラスになっている。多様体って先にハウスドルフ空間があってその上にアトラスを用意するイメージだったけど、例11ではアトラスから多様体をつくったんだね。例12も同じで2枚の紙から球面状の多様体をつくっている。以下の図みたいに。

f:id:cookie-box:20190101155733p:plain:w60

また絵が雑ですね…では、例13も同じように考えればいいのでしょうか。例13も「貼り合わせる」のは2枚の紙のようですね。それで貼り合わせ方は…え? 何ですかこれ?

f:id:cookie-box:20190101160814p:plain:w60

1枚目の紙の y 軸上のどの点も、2枚目の紙の x 軸上のどの点とも同一視されるんだよね。貼り合わせ方としてはこんな感じかな。

2枚の紙を貼り合わせた結果、1枚の紙になっていると思う。

f:id:cookie-box:20190101155733p:plain:w60

紙、伸び縮みしすぎですよね…? 本当に紙ですか? まあ例12でも伸び縮みしてましたが…。しかし、2枚の紙が1枚の紙になったんですか。例11や例12のように輪っかや球面ができたわけではないんですね。それ、何かうれしいんですか?

f:id:cookie-box:20190101160814p:plain:w60

貼り合わせた紙は、まあ紙なんだから普通に座標がかけるけど、普通の座標の他に U_1 って座標と U_2 って座標もかける。U_1 って座標は、貼り合わせた紙の原点の近くにぎゅっと座標が寄せ集められた、貼り合わせた紙からみればゆがんだ座標をしている。…ということは、もし貼り合わせた紙の上に「結び目」があったら、そこにしわくちゃにしぼられた座標をあてがって、座標のしわを広げれば結び目がほどけるかもしれない…っていいたいんじゃないかな?

f:id:cookie-box:20190101155733p:plain:w60

本当にそういいたいんですかね!?

f:id:cookie-box:20190101160814p:plain:w60

91ページからの 4.2 節では特異点解消定理が出てくるけど、92ページをみるとこのテキストで出てくる特異点解消定理では特異点がなくなるわけではないとあるね。「特異点が正規交差だけになる」とある。

f:id:cookie-box:20190101155733p:plain:w60

え、特異点がなくなるわけではないんですか? タイトル詐欺ですね…。

f:id:cookie-box:20190101160814p:plain:w60

92ページに「 |g'(u)|=0 となるような u の集合は \mathcal{M} の中で体積が 0 の集合である」とあるけど、これは、 |g'(u)|=0 となるような u の集合はパラメータ空間 W 上で体積が 0 になるという意味だね。体積というより確率といった方がわかりやすいかもしれない。

もう少しつづけたい

雑記: 反復法の話

おかしい点がありましたらご指摘いただけますと幸いです。

※ キャラクターは架空のものです。
f:id:cookie-box:20190101155733p:plain:w60

連立一次方程式の数値解法にヤコビ法ってありますよね。

f:id:cookie-box:20190101160814p:plain:w60

連立一次方程式を解くアルゴリズムの中でも反復法といわれるものだね。

f:id:cookie-box:20190101155733p:plain:w60

Ax=b の右辺を A の対角成分だけ取り残して移項して  Dx = - (L + U)x + b とし、さらに D^{-1} をかけて  x = - D^{-1}(L + U)x + D^{-1}b として、これを漸化式に見立て  x^{(k+1)} = - D^{-1}(L + U)x^{(k)} + D^{-1}b としてしまう。適当な初期値 x^{(0)} から出発して、もし値がほぼ変化しなくなったらそれが解である…。

ヤコビ法A = L + D + UD は対角行列,L は狭義下三角行列,U は狭義上三角行列.)
 x^{(k+1)} = - D^{-1}(L + U)x^{(k)} + D^{-1}b
手続きは理解できますが、なぜこうしなければならなかったのでしょう。下三角行列 L と上三角行列 U に取り残されてしまった対角行列 D が不憫ではないですか?

f:id:cookie-box:20190101160814p:plain:w60

そ、そうかな…。

f:id:cookie-box:20190101155733p:plain:w60

それに、反復法といいますけど、別に反復をしたくてしているわけでもないはずなんです。連立一次方程式を解きたいのなら、いま手元にある適当な x\Delta x を足して本当の解との誤差を埋めたいのですよね。であれば、x から進むべき \Delta x は理想的には \Delta x = -x + A^{-1}b = A^{-1}(-Ax+b) であるはずです。

f:id:cookie-box:20190101160814p:plain:w60

そりゃ本当の解が  A^{-1}b だからね。

f:id:cookie-box:20190101155733p:plain:w60

ええ、 A^{-1} が求まるなら反復する必要なんてないわけです。A^{-1} を求めることを回避して \Delta x に近いものを得たいんです。そこで、\Delta x = A^{-1} (-Ax +b) \fallingdotseq D^{-1} (-Ax + b) という雑な近似をしたわけです。「逆行列求めるの面倒だから対角成分だけの行列の逆行列でいいや」ということですね。こうすれば、

ヤコビ法にたどり着くまで(?)
 \begin{split} x + \Delta x &= x + A^{-1}( -Ax + b) \\ &\fallingdotseq x + D^{-1} (-Ax +b) \\ &= x - D^{-1} (L + D + U) x + D^{-1}b \\ &= - D^{-1} (L + U) x + D^{-1}b \end{split}
と、ヤコビ法に一致するわけです。副部長、どうですか? この私の推理―。

f:id:cookie-box:20190101160814p:plain:w60

いや、推理とかじゃないからね。

f:id:cookie-box:20190101155733p:plain:w60

ガウス・ザイデル法は下三角行列と対角行列を取り残して (D+L)x = - Ux + b としてこれを漸化式に見立てたものなんですね。

ガウス・ザイデル法
 x^{(k+1)} = - (D+L)^{-1}Ux^{(k)} + (D+L)^{-1}b
ヤコビ法と下三角行列の部分が異なりますが、これは、「xi 番目の成分を更新するとき、i-1 番目までの成分は既に更新後のものが計算されているはずだから、もう更新後のものを使ってしまおう」というものなのですよね。なので、ヤコビ法よりも小さいステップで収束することが期待されますが、i-1 行目の更新を終えないと i 行目の更新ができないために並列計算できなくなっているデメリットもあります。
ヤコビ法  Dx^{(k+1)} = - (L + U)x^{(k)} + b
ガウス・ザイデル法 Dx^{(k+1)} = - L x^{(k+1)} - Ux^{(k)} + b
ガウス・ザイデル法にたどり着くまで」は「ヤコビ法にたどり着くまで」の \fallingdotseq のところで A^{-1}D^{-1} に取り換えるのではなく (D+L)^{-1} に取り換えるという違いだけなので省略しますね。
ガウス・ザイデル法にたどり着くまで(?) ヤコビ法と同様なので省略。
  x + \Delta x \fallingdotseq - (D+L)^{-1}Ux + (D+L)^{-1}b

f:id:cookie-box:20190101160814p:plain:w60

手抜きだな…。

f:id:cookie-box:20190101155733p:plain:w60

SOR法は、一度ガウス・ザイデル法に照準を定めておいて、そちらの方向へ加速パラメータ \omega で近づくというものですね。

ヤコビ法  Dx^{(k+1)} = - (L + U)x^{(k)} + b
ガウス・ザイデル法 Dx^{(k+1)} = - L x^{(k+1)} - Ux^{(k)} + b
SOR法 \begin{cases} D\tilde{x}^{(k+1)} = - L x^{(k+1)} - Ux^{(k)} + b \\ x^{(k+1)} = x^{(k)} + \omega (\tilde{x}^{(k+1)}  - x^{(k)}) \end{cases}
ただ \omega で加速させる部分に  x^{(k+1)} が含まれていますから、 x^{(k+1)} について解くとややこしい形になりますね。ただ \omega=1 のときはガウス・ザイデル法に一致します。SOR法をそのように決めたので当然ですね。
SOR法
 \begin{split} Dx^{(k+1)} &= Dx^{(k)}  + \omega (- L x^{(k+1)} - Ux^{(k)} + b  - Dx^{(k)}) \\ (D + \omega L) x^{(k+1)} &= \bigl( (1 - \omega)D - \omega U \bigr) x^{(k)}  + \omega b \\ x^{(k+1)} &= (D + \omega L)^{-1} \bigl( (1 - \omega)D - \omega U \bigr) x^{(k)}  + \omega (D + \omega L)^{-1}  b \end{split}
「SOR法にたどり着くまで」は「ヤコビ法にたどり着くまで」において \Delta x\omega で加速させて、\fallingdotseq のところで A^{-1} (D + \omega L)^{-1} に取り換えると得られますね。単純に  (D + L)^{-1} に取り換えるのではない点に注意です。下三角行列 L は既に \omega で加速して更新されているから、といったイメージでしょうか。
SOR法にたどり着くまで(?)
 \begin{split} x + \omega \Delta x &=  x + \omega A^{-1} (-Ax + b) \\ &\fallingdotseq x + \omega (D + \omega L)^{-1} (-Ax + b) \\ &= x - \omega (D + \omega L)^{-1} (D + L + U)x + \omega(D+\omega L)^{-1}b  \\ &= (D + \omega L)^{-1} \bigl( D - \omega D - \omega U \bigr)x + \omega(D+\omega L)^{-1}b \end{split}

つづかない

雑記: システムの可制御性・可観測性の話

おかしい点がありましたらご指摘いただけますと幸いです。

参考文献

  1. 線形システム論
    • 可制御性・可観測性の講義資料がありました。
  2. 可制御性・可観測性 - 初級Mathマニアの寝言
    • この方の記事のように正準分解形までいきたかったのですがはるか手前で力尽きました。


突然ですが、A \in \mathbb{R}^{n \times n}, \, t\in \mathbb{R} に対し、 \exp(At) を以下のように定義することにします。つまり、 \exp(At) \in \mathbb{R}^{n \times n} です。At に依存しないことにします。
  \displaystyle \exp(At) \equiv I + At + \frac{1}{2} A^2 t^2 + \frac{1}{3!} A^3 t^3 + \cdots + \frac{1}{k!} A^k t^k + \cdots
するとこうなります。\mathcal{o}(\cdot) はスモールオーで、R(t) は各成分が t より速く 0 に収束する n \times n 行列です。
  \displaystyle \exp \bigl(A(t_0 + t)\bigr) = I + A(t_0 + t) + \frac{1}{2} A^2 (t_0 + t)^2 + \frac{1}{3!} A^3 (t_0 + t)^3 + \cdots+ \frac{1}{k!} A^k (t_0 + t)^k + \cdots
  \displaystyle = \exp(At_0) + At + \frac{1}{2} A^2 (2 t_0 t + t^2) + \frac{1}{3!} A^3 (3 t_0^2 t + 3t_0 t^2 + t^3) + \cdots + \frac{1}{k!} A^k \bigl(k t_0^{k-1} t + \mathcal{o}(t) \bigr) + \cdots
  \displaystyle = \exp(At_0) + A \exp(At_0) t + R(t)
なので、\exp(At_0) という行列の各成分の値は、t_0 の部分を t_0 からほんの少しの t だけずらすと、ずらした分の  A \exp(At_0) (の同じ成分)倍だけ値がずれます(微分)。各成分の微分を束ねてしまってこうかきます。
   \displaystyle \frac{d}{dt} \exp(At) =  A \exp(At)
このことを利用すると、もし下のようにひとりで勝手に変化していく x(t) \in \mathbb{R}^n があったとき、その正体が  x(t) = \exp \bigl( A(t-t_0) \bigr) x_0 であるとわかります(ただし、初期状態が x(t_0) = x_0 であったとしました)。
ひとりで勝手に変化していく x(t)
 \displaystyle \; \; \frac{d}{dt}x(t) = A x(t)
しかし、これからやりたいことは、x(t) が勝手に変化するのを放っておくのではなく、これに何かを入力したり、何か出力を取り出したりすることです。特に、入力 u(t) を加えて x(t) を思い通りに制御できるかとか、出力 y(t) を観測して x(t) を特定できるかとかに興味があります。
何かを入力すると何かが出力されるもののことを「システム」というらしいです。が、それだけだとシステムがどんな性質をもつかについて考察できないし、入力や出力とは何なのかもよくわからないので、ここではもっぱら方程式によるモデルのことをシステムと考えます。あと、ここで考えるシステムには何か放っておいてもひとりで勝手に変化していく「状態」というものがあって、この状態は「自身の現在の状態」の線形変換と「現在の入力」の線形変換を足し合わせた速度で変化します。そして状態の線形変換が出力されてきます。そういうシステムを考察することにします。逆に、勝手に変化していく「状態」を中で飼っていなければ明らかに好きなように制御できるのでそんなシステムを考察する必要はないわけです。
(線形で時不変な)連続時間システム
 \begin{cases} \displaystyle \frac{d}{dt}x(t) = A x(t) + B u(t) & \\ y(t) = Cx(t) & \end{cases}
ここで、x(t) \in \mathbb{R}^n, \, u(t) \in \mathbb{R}^r, \, y(t) \in \mathbb{R}^m, \, A \in \mathbb{R}^{n \times n}, \, B \in \mathbb{R}^{n \times r}, \, C \in \mathbb{R}^{m \times n} とし、x(t) を状態、u(t) を入力、y(t) を出力とよぶことにします。入力は状態そのものでなく状態の速度と線形の関係にありますが、現実ではこういうことはわりと(?)あります。コンデンサにある電位差を生じさせたいときにどう電流を流せばいいかや、ダンパを介してぶら下がった重りをある高さまで変位させるのにどう力を加えればいいかといったケースがそうです。そんな風に状態をぬるっと変えることができずじわじわ変えていくしかない場合はあります。
なお、入力 u(t) がある場合の状態を解くと以下のようになります(証明略)。
   \displaystyle x(t) = \exp \bigl( A(t-t_0) \bigr) x_0 + \int_{t_0}^t \exp \bigl(A(t - \tau)\bigr) Bu(\tau)d\tau

ここから本題ですが、システムの「可制御性」と「可観測性」は以下のように定義されます(お手元の本により異なる可能性があります)。
可制御性
任意の時刻 t_0, \; t_1 \, (t_0 < t_1) 及び任意の状態 x_0, \; x_1 に対して、x(t_0)=x_0 であったときに x(t_1) = x_1 に到達させる入力 u(t)\, (t_0 \leqq t \leqq t_1) が存在するならば、このシステムは可制御であるという。
可観測性
任意の時刻 t_0, \; t_1 \, (t_0 < t_1) に対して、入力 u(t)\, (t_0 \leqq t \leqq t_1) 及び出力 y(t)\, (t_0 \leqq t \leqq t_1) が与えられたとき、初期状態 x(t_0)=x_0 を一意に特定できるならば、このシステムは可観測であるという。
可観測性は状態 x(t)\, (t_0 \leqq t \leqq t_1) を一意に特定できる、といっても同じですが、それは初期状態 x(t_0)=x_0 を一意に特定できることと同じです。
可制御性や可観測性がそう定義されるのはいいんですが、どんなときにシステムが可制御や可観測になるのかよくわかりません。先に結論を述べると、可制御性については以下が成り立ちます。
可制御性の必要十分条件
以下の4つの条件は同値である。
  1. システムが可制御である。
  2.  \displaystyle V \equiv \Bigl[ B \; AB \; A^2 B \; \cdots \; A^{n-1} B \Bigr] なる  n \times nr 行列 V のランクが n(フルランク)である。
  3.  \displaystyle W(t_0, t_1) \equiv \int_{t_0}^{t_1} \exp (-At) B B^\top \exp (-A^\top t) dt なる行列 W(t_0, t_1) が任意の t_0, \; t_1 \; (t_0 < t_1) で正則である。
  4.  V^\ast(\lambda_i) \equiv \Bigl[ \lambda_i I - A \; B\Bigr] なる  n \times (n+r) 行列 V^\ast(\lambda_i) のランクが n(フルランク)である。
上の V を可制御性行列、W(t_0, t_1) を可制御性グラミアンというらしいです。
これを証明します。ここで、時刻 t_1 における状態は以下のようにかけることに注意します。システムが可制御であるということは、都合のいい u(t) を選べばこの式を任意の値にできるということです。
   \displaystyle x(t_1) = \exp \bigl( A(t_1-t_0) \bigr) x_0 + \exp(A t_1) \int_{t_0}^{t_1} \exp (- A\tau) Bu(\tau)d\tau
W(t_0, t_1)u(t)=B^\top \exp (-A^\top t) x_0 を入力したとき  x(t_1) = \exp \bigl( A(t-t_0) \bigr) x_0 + \exp(A t_1) W(t_0, t_1) x_0 となるような量になっているとわかります。3. はこの W(t_0, t_1)逆行列があるといっているわけです。
また、t についての積分と行列の積は交換することに注意します(行列やベクトルにうつす関数であっても積の微分公式は成り立つので、部分積分から示せます)。となると、直ちに以下が示せます。
可制御性 3. ⇒ 1.
任意の x_1 に対し \displaystyle u_1(t) \equiv B^\top \exp(-A^\top t) W(t_0, t_1)^{-1} \Bigl( \exp(-At_1)x_1 - \exp(-At_0) x_0 \Bigr) とすれば、
 \displaystyle x(t_1) = \exp \bigl( A(t_1-t_0) \bigr) x_0
   \displaystyle + \exp(A t_1) \int_{t_0}^{t_1} \exp (- A\tau) B B^\top \exp(-A^\top \tau) d\tau \cdot W(t_0, t_1)^{-1} \Bigl( \exp(-At_1)x_1 - \exp(-At_0) x_0 \Bigr)
     = \exp \bigl( A(t_1-t_0) \bigr) x_0 + \exp(A t_1) \Bigl( \exp(-At_1)x_1 - \exp(-At_0) x_0 \Bigr) = x_1
W(t_0, t_1)逆行列さえあれば x(t_1) を好きな値にできるわけです。この逆も示せます。つまり、好きに制御できるなら、W(t_0, t_1) は正則であるということです。正則でないと仮定して矛盾を導きます。
可制御性 1. ⇒ 3.
ある t_0, \; t_1 \; (t_0 < t_1) W(t_0, t_1) が正則でないと仮定すると、 \exp(At_0)W(t_0, t_1) \exp(A^\top t_0) も正則でないので、 \exp(At_0)W(t_0, t_1) \exp(A^\top t_0) x_0 = \vec{0} を満たす非ゼロベクトル x_0 \in \mathbb{R}^n が存在する。 x_0^\top \exp(At_0)W(t_0, t_1) \exp(A^\top t_0) x_0 = 0 より、 \displaystyle \int_{t_0}^{t_1} x_0^\top \exp \bigl(-A(t-t_0) \bigr) B B^\top \exp \bigl(-A^\top (t-t_0) \bigr) x_0 dt = \int_{0}^{t_1 - t_0} \bigl\| B^\top \exp \bigl(-A^\top (t-t_0) \bigr) x_0 \bigr\|^2 dt = 0 なので、 t_0 \leqq t \leqq t_1B^\top \exp \bigl(-A^\top (t-t_0) \bigr) x_0 は恒等的にゼロである。ここで、いま可制御なので、時刻 t_0x_0 であったときに時刻 t_1\vec{0} に到達させる入力 u_0(t) が存在する。よって、 \displaystyle \vec{0} = \exp \bigl( A(t_1-t_0) \bigr) x_0 + \exp(A t_1) \int_{t_0}^{t_1} \exp (- A\tau) Bu_0(\tau)d\tau より、 \displaystyle x_0 = -\int_{t_0}^{t_1} \exp \bigl( -A(\tau - t_0) \bigr) Bu_0(\tau)d\tau とかくことができる。ここで、 \displaystyle \|x_0\| = x_0^\top x_0 = -x_0^\top \int_{t_0}^{t_1} \exp \bigl(-A(\tau - t_0) \bigr) Bu_0(\tau)d\tau = \int_{t_0}^{t_1} \Bigl( - B^\top \exp \bigl( -A^\top (\tau - t_0) \bigr) x_0 \Bigr)^\top u_0(\tau)d\tau となるが、B^\top \exp \bigl(-A^\top (\tau-t_0) \bigr) x_0 は恒等的にゼロなのでこの式はゼロとなり、x_0 が非ゼロベクトルであることに矛盾。よって、任意の t_0, \; t_1 \; (t_0 < t_1)W(t_0, t_1) は正則である。
条件 2. からも W(t_0, t_1) が正則であることが示せます。
可制御性 2. ⇒ 3.
ある t_0, \; t_1 \; (t_0 < t_1) W(t_0, t_1) が正則でないと仮定すると  W(t_0, t_1) x_0 = 0 を満たす非ゼロベクトル x_0 \in \mathbb{R}^n が存在して、B^\top \exp (-A^\top t) x_0 \; (\ast) は恒等的にゼロである(1. ⇒ 3. の証明と同様)。
 (\ast)t=0 を代入して、B^\top x_0 = \vec{0}
 (\ast)1微分t=0 を代入して、-B^\top A^\top x_0 = \vec{0}
 (\ast)2微分t=0 を代入して、B^\top (A^\top)^2 x_0 = \vec{0}
 (\ast)n-1微分t=0 を代入して、(-1)^{n-1} B^\top (A^\top)^{n-1} x_0 = \vec{0}
これらの転置を横に並べて  x_0^\top \Bigl[ B \; AB \; A^2 B \; \cdots \; A^{n-1} B \Bigr] = \vec{0}^\top \; \Leftrightarrow \; x_0^\top V = \vec{0}^\top だが、x_0 は非ゼロベクトルなので、V はフルランクでない。いま、3. の否定から 2. の否定が示されたので、対偶をとると、2. から 3. が示される。
この逆も示せます。ケーリー・ハミルトンの定理を使います。
 {\rm det}(sI-A) = s^n + \alpha_1 s^{n-1}+ \cdots + \alpha_n = 0 \; \Rightarrow \; A^n + \alpha_1 A^{n-1}+ \cdots + \alpha_n I = 0
可制御性 3. ⇒ 2.
V がフルランクでないとすると、 x_0^\top \Bigl[ B \; AB \; A^2 B \; \cdots \; A^{n-1} B \Bigr] = \vec{0}^\top を満たす非ゼロベクトル x_0 \in \mathbb{R}^n が存在する。つまり、B^\top x_0 = 0, \;B^\top A^\top x_0 = 0, \; \cdots, B^\top (A^\top)^{n-1} x_0 = 0 。また、ケーリー・ハミルトンの定理より、A^nI, \; A, \; \cdots, A^{n-1} の線形結合でかけるので、
B^\top \exp(-A^\top t)x_0 = \displaystyle B^\top \left( I - A^\top t + \frac{1}{2}(A^\top)^2 t^2 - \cdots \right) x_0 = 0 となる。よって、
 \displaystyle \int_{t_0}^{t_1}\bigl\| B^\top \exp(-A^\top t)x_0 \bigr\| dt = 0 \; \Leftrightarrow \; x_0^\top W(t_0, t_1) x_0 = 0 となるが、x_0 は非ゼロベクトルなので、W(t_0, t_1) は正則ではない。いま、2. の否定から 3. の否定が示されたので、対偶をとると、3. から 2. が示される。
(可制御性の残りの ⇒ 関係の証明と、可観測性の証明は未完です。)
可観測性の必要十分条件
以下の4つの条件は同値である。
  1. システムが可観測である。
  2.  \displaystyle N \equiv \begin{bmatrix} C \\ CA \\ \vdots \\ CA^{n-1} \end{bmatrix} なる  mn \times n 行列 N のランクが n(フルランク)である。
  3.  \displaystyle V(t_0, t_1) \equiv \int_{t_0}^{t_1} \exp (-A^\top t) C^\top C \exp (-A t) dt なる行列 V(t_0, t_1) が任意の t_0, \; t_1 \; (t_0 < t_1) で正則である。
  4.  N^\ast(\lambda_i) \equiv \begin{bmatrix} \lambda_i I - A \\ C \end{bmatrix} なる  n \times (n+r) 行列 N^\ast(\lambda_i) のランクが n(フルランク)である。
上の N を可観測性行列、V(t_0, t_1) を可観測性グラミアンというらしいです。

雑記: 1の分割の話

お気付きの点がありましたらご指摘いただけますと幸いです。全体的に参考文献 3. がないと(あっても)意味がわかりません。
参考文献

  1. 1の分割 - Wikipedia
  2. パラコンパクト空間 - Wikipedia
  3. 多様体の基礎 (基礎数学) | 松本 幸夫 |本 | 通販 | Amazon

※ キャラクターは架空のものです。
f:id:cookie-box:20190101155733p:plain:w60

「1の分割」というものがあるらしいんですが…。

f:id:cookie-box:20190101160814p:plain:w60

導入が雑すぎる…。

f:id:cookie-box:20190101155733p:plain:w60

そういわれても…じゃあ真面目に説明しますね。


ベイズ統計の理論と方法の4章では、真の分布 q(x) と確率モデル p(x|w) の関係に(「相対的に有限な分散をもつ」ということ以外は)何も仮定がない場合を扱うんですが、平均誤差関数を標準形にするために、パラメータを適当な多様体上の局所座標に変換してしまうみたいなんです。こうして得た「パラメータ改」が [0, 1]^d の有限和でかけるものとしてよいとするのに、「1の分割」なるものが存在するという定理を利用するようなんですが(厳密には「1の分割」そのものではなく同様の手続きということなんですが)…。
…という導入であればモチベーションがわかりやすいでしょうか?

f:id:cookie-box:20190101160814p:plain:w60

わかりやすくはない…。

f:id:cookie-box:20190101155733p:plain:w60

どうしろと…。

f:id:cookie-box:20190101160814p:plain:w60

ともかく、定理の主張はつかめたの?

f:id:cookie-box:20190101155733p:plain:w60

はい。調べたのですが、「1の分割」というのはある位相空間に対して指定の条件を満たす関数族(関数の集合)のことのようですね。

定義.1の分割
\mathcal{M}位相空間とする.\{\varphi_\alpha(p)\}_{\alpha \in A}\varphi_\alpha: \mathcal{M} \to [0, 1] であるような連続関数の集合とする.\{\varphi_\alpha(p)\}_{\alpha \in A} が任意の  p \in \mathcal{M} について以下の2つの条件を満たすとき,\{\varphi_\alpha(p)\}_{\alpha \in A}\mathcal{M} の1の分割という.
  1. p を元として含むある開集合 V が存在して,\{\varphi_\alpha(p)\}_{\alpha \in A} から任意の p \in V\varphi_\alpha(p)=0 になる元を除くと,有限集合になる( \{\varphi_\alpha(p)\}_{\alpha \in A} のうち V 内のどこかで 0 より大きい値をとるようなものは有限個である).
  2.  \sum_{\alpha \in A} \varphi_\alpha(p) = 1 である.
特に,\mathcal{M}開被覆  \{U_\alpha\}_{\alpha \in A} に対して,\varphi_\alpha(p) = 0, \, p \notin U_\alpha であるような1の分割 \{\varphi_\alpha(p)\}_{\alpha \in A}開被覆  \{U_\alpha\}_{\alpha \in A} に従属する1の分割という.
関数族の元は無限にあっても構わないようですが、位相空間内の各点の周りだけに注目したときは有限個を除いてゼロでなければならないようですね。また、位相空間の任意の点で関数族の値の和は1でなければなりません…関数族が1を分け合うことから「1の分割」と名付けられたのでしょうか。また、位相空間開被覆―開集合族であって、和集合がその位相空間を覆いつくすものですね―及び開被覆と同じ添え字をもつ1の分割があるとき、1の分割の各元が同じ添え字の開集合の外では常にゼロであるならば、その1の分割はその開被覆に従属するというようです。それで、ベイズ本の文脈では、開被覆の方が先に決まっていて、それに従属する1の分割がほしいはずなんです。しかし、一般の位相空間では任意の開被覆に1の分割が存在するわけではありません。調べたところによると、「ハウスドルフ性」をもつ位相空間が「パラコンパクト性」をもつとき、またそのときに限り、その位相空間は任意の開被覆に従属な1の分割をもつそうです。
定理.1の分割の存在
\mathcal{M}ハウスドルフ空間とする.\mathcal{M} がパラコンパクトであることと,\mathcal{M} の任意の開被覆が従属な1の分割をもつことは同値である.
このことはウィキペディアパラコンパクト空間に証明がのっているんですが、ちょっと日本語と英語が混ざったルー大柴状態で読みづらく…。

f:id:cookie-box:20190101160814p:plain:w60

いや、いうほど混ざってもないしルー大柴は「局所有限開被覆」とかいわないと思う…。そもそも英語版を参照すればいいんじゃ…でも、この証明は別の補題を利用していて追いかけづらいのかな。難しかったらいきなりパラコンパクトハウスドルフ空間における証明を目指すんじゃなくて、証明しやすい場合で証明すればいいんじゃない? 以下の本の186ページに、まずコンパクトな微分可能多様体における「1の"2"分割」の存在の証明があるよ。その後190ページにσコンパクトな微分可能多様体の任意の開被覆の細分に対する1の分割の存在の証明、198ページにはσコンパクトな微分可能多様体の任意の有限開被覆に従属する1の分割の存在の証明があるね。


多様体の基礎 (基礎数学)

多様体の基礎 (基礎数学)

f:id:cookie-box:20190101155733p:plain:w60

え、えっと、「パラコンパクト性」の他に「コンパクト性」「σコンパクト性」というのもあるのですか? ご兄弟がいらっしゃったのですね…。あと、「1の分割」は位相空間に対する概念ではなかったのですか? 位相空間ではなくて多様体なんですか?

f:id:cookie-box:20190101160814p:plain:w60

いや、多様体ってハウスドルフ性(任意の異なる2つの元に対してそれぞれを元として含む共通部分のない開集合がとれるという性質)と地図帳をもってる位相空間のことだからね(注: 単に多様体といったときの定義は文献によります)。

f:id:cookie-box:20190101155733p:plain:w60

私は地理選択ではないので地図帳はもっていませんね。

f:id:cookie-box:20190101160814p:plain:w60

位相空間開被覆  \{U_\alpha\}_{\alpha \in A} があって、それぞれの  U_\alpha から \mathbb{R}^m の開集合への同相写像  \varphi_\alpha があれば、 \{ (U_\alpha, \varphi_\alpha) \}_{\alpha \in A} は地図帳(アトラス; m 次元座標近傍系)だね。この地図帳があれば、位相空間の任意の点に対してどこかの \alpha ページに m 次元ベクトルの住所がかいてある。

f:id:cookie-box:20190101155733p:plain:w60

なるほど…でも、その点で開被覆  U_{\alpha_0} , \, U_{\alpha_1} が重なっているような点だと、 \alpha_0 ページと \alpha_1 ページに異なる住所がかいてあるようなことになりませんか?

f:id:cookie-box:20190101160814p:plain:w60

 \alpha_0 ページで住所が m 次元ベクトル x_0 であるような点は、 \alpha_1 ページでの住所に直すと  \varphi_{\alpha_1}  \circ \varphi_{\alpha_0}^{-1}(x_0) だね。もっとも、U_{\alpha_0}U_{\alpha_1} の共通部分に属する点については、ということだけどね。この写像  \varphi_{\alpha_1}  \circ \varphi_{\alpha_0}^{-1} を座標変換といって、任意の「重なりがあるページ」間の座標変換が  C^r 級なら、そんな地図帳をもっている多様体m 次元 C^r微分可能多様体C^r多様体)というよ。

f:id:cookie-box:20190101155733p:plain:w60

あるページにおける住所表示から別のページにおける住所表示への変換が滑らかなら C^r多様体ということでしょうか。確かに、地図帳のあるページにあった公園が、別のページでは2つに引き裂かれていたら嫌かもしれないですね。そういうことがない地図帳ということですね。

f:id:cookie-box:20190101160814p:plain:w60

まあこの「地図帳が C^r 級である」というのはこれを仮定しないと1の分割ができないわけじゃないはずなんだけど(実際、一般の1の分割の存在定理は多様体を仮定してなかった=地図帳を仮定してなかったしね)、仮定するのが証明しやすいんだと思う。あ、あと 186 ページの証明では地図帳が  C^r 級であることの他に、位相空間自体に「コンパクト性」も要るね。任意の開被覆が有限部分開被覆をもつ(開被覆の有限個の部分集合だけで位相空間を覆いつくせる)という性質だね。

f:id:cookie-box:20190101155733p:plain:w60

「コンパクト性」ですか…よくわかりませんね。だから何といった感じなんですが。1の分割をするのになぜそんな性質が必要なんです?

f:id:cookie-box:20190101160814p:plain:w60

位相空間をコンパクト集合で覆いたいからかな。コンパクト性がないとそれが保証されない。1の分割って各点で有限個の関数さんたちに1を分け合ってほしいんだよね。逆にいうと、ある点でどの関数さんも分け前をもらっていってくれなかったら(どの関数の値もゼロだったら)困るよね。だから、位相空間をコンパクト集合で覆って、関数さんたちに「担当するコンパクト集合内では必ず正の値をとってね」って指示したいんだよね。まあ詳しくはおいおいかな。


具体的に、186 ページにある1の分割の最初の一歩はこうだね。
定理.コンパクト微分可能多様体を覆う2つの開集合に従属する1の分割
\mathcal{M} をコンパクト  C^r多様体とし,開集合 U, V \subset \mathcal{M}U \cap V = \mathcal{M} を満たすものとする.このとき,以下の3つの条件を満たす \mathcal{M} 上の  C^r 級関数 f: \mathcal{M} \to \mathbb{R}g: \mathcal{M} \to \mathbb{R} が存在する.
  1.  0 \leqq f \leqq 1 0 \leqq g \leqq 1
  2.  {\rm supp}(f) \subset U {\rm supp}(g) \subset V
  3.  f + g \equiv 1

f:id:cookie-box:20190101155733p:plain:w60

はあ…ん? 副部長、誤植がありますよ。{\rm supp} じゃなくて {\rm sup} です。

f:id:cookie-box:20190101160814p:plain:w60

それは {\rm supp} で合ってるよ。 {\rm supp}(f) \equiv {\rm cl} \{q \in \mathcal{M} \, | \, f(q) \neq 0 \} で、日本語でいうとサポートとか台だね。関数の値がゼロでない点の集合の閉包のことだよ。てか {\rm sup} じゃ意味通んないでしょ。

f:id:cookie-box:20190101155733p:plain:w60

なるほど。しかし、「このような関数たちが存在する」ということの証明はどうやるのでしょう? やり方が思い付きません…。

f:id:cookie-box:20190101160814p:plain:w60

実際に構成できるんだよ。上の定理の証明の流れはこうだね。

  1.  \mathcal{M} のコンパクト部分集合 K, \, L であって  K \subset U, \, L \subset V かつ  K \cup L = \mathcal{M} となるものが存在する(これにコンパクト性が必要)。
  2.  \mathcal{M} の任意の点とその開近傍 p, \, U に対して、次のような  C^r 級関数 \varphi が存在する;U に包含されるある開近傍の閉包 {\rm cl} W 内では1をとり、 U \setminus {\rm cl} W では0以上1未満の値をとり、 \mathcal{M} \setminus U では0をとる(証明は、\varphi を実際につくることによる)。
  3. 1. の  K の各点  p に対して、p, \, U に 2. を適用すると  \varphi_p, \, W_p をとれる。また、K はコンパクトなので有限個の W_p で覆うことができる。この有限個に対応する  \varphi_p を足し上げたものを  h_K とする。1. の L に対しても同様に h_L を得る。f = h_K / (h_K + h_L), \, g = h_L / (h_K + h_L) が題意を満たす。

f:id:cookie-box:20190101155733p:plain:w60

流れだけかかれても…。

f:id:cookie-box:20190101160814p:plain:w60

証明かくのしんどいからね。

つづかない