Smile Engineering Blog

ジェイエスピーからTipsや技術特集、プロジェクト物語を発信します

Amazon Honeycodeを使ってみた(その1)

はじめに

コードをまったく書かずにウェブ・モバイルアプリを構築することができるという「Amazon Honeycode」のベータ版が公開されました。
どんなものなのか興味があり、無料で試せるということで少し触ってみようと思います。

続きを読む

PyTorchで学ぶ『平均』と『分散』と『BatchNormalization』

ところでBatchNormalizationってなんだっけ?

深層学習でモデル構築をしていると、よくお見かけするのがBatchNormalizationと呼ばれるもの。

・・・はい。よく見かけますよね?

・・・・・・・・・。

ところで、結局それってなんでしたっけ?

「平均を0、分散を1」という説明はよく聞きますけど、それは結局どういうことなのか?
というのが今日のお題です。

ちなみにですけど、この記事を書いてる人間は、本ブログで度々統計のことについて語っていらっしゃる統計学スペシャリストとは別の人間です。どちらかというと統計学は素人に近い(?)ので、『え、そこから???』などと言わず、温かい目で読んでいただけたらと思います。
(使用しているのがNumpyではなくPyTorchという辺りがお察しですね・・・)

続きを読む

GitHub Wiki でのファイル添付

はじめに

みんな大好き GitHub。issue や PR に補足資料としてパワポやエクセルのファイル、イメージを張り付けるなんてことは良くやります。この場合、Edit 欄にファイルを Drag & Drop するだけで自動的にアップロードしてリンク作成されるのですが、同じノリで Wiki ページにも貼り付けようとすると、、これができません。

さてどうすれば?

続きを読む

FIRフィルタを作って周波数特性を検証

適応フィルタを作ってみる では、サンプルコードを紹介しましたが、実際に動かしてみたいと思います。そこで適応フィルタの前に、まずはシンプルに固定フィルタを検証してみます。

  • FIRフィルタ
    • サンプルコード
  • 検証用のコード
    • サンプルコード
  • フィルタスルーで動作確認
    • Audacityで正弦波を作ってフィルタに入力
    • 実行方法
      • AudacityでPCMファイルの読み込み
  • ローパスフィルタを検証

FIRフィルタ

f:id:jspnet:20200306005824p:plain:right:w600 適応フィルタを作ってみる で使用したFIR【Finite Impulse Response】のサンプルコードを、まずは固定フィルタで検証してみます。

{
 y(n) = \sum_{k=0}^{N}h_k x(n-k)
}


続きを読む

The Continuing Story of Error Correction Code 3

ハミング距離

カルノー

カルノー図は論理式を簡略化するためなどに使用する図です。


\begin{aligned}
f&=\overline{A}\cdot\overline{B}\cdot C +\overline{A}\cdot B \cdot C+ A\cdot\overline{B}\cdot\overline{C}+A\cdot B \cdot\overline{C} \\\
&=\overline{A} \cdot C+ A \cdot \overline{C}
\end{aligned}

 
このような論理式の簡略化を図から容易に行うことができます。
が、ここでは論理式は扱いません。ハミング距離の理解のためだけにカルノー図を使います。

ハミング距離の説明でよく超立方体が使われていますが(ハミング距離 - Wikipediaでも4次元の超立方体が使われてますね)次数が上がると図が意味不明になるし、そもそもイメージしずらいのでここではカルノー図で押し通してみましょう。
では、8変数までのカルノー図の作り方のはじまりはじまり・・・

2ビットのカルノー

縦方向に b_{1}、横方向に b_{0}を割り当てて、各マスには b_{1} b_{0}の3ビットの値が書き込まれており、3ビットが取り得る値の一覧表になっています。 3ビットが取り得る値は 2^{2}=4で4通りなので4種類の値となります。

 0 1
 0 00 01
 1 10 11

2ビットのカルノー図はこれで完成です。
 
「で、カルノー図って一体なんなんだよ!!」 はい、そうでしたね。ではカルノー図が一体何なのかは3ビットのカルノー図で説明しましょう。

3ビットのカルノー

縦方向に b_{2} b_{1}、横方向に b_{0}を割り当てて、各マスには b_{2} b_{1} b_{0}の3ビットの値が書き込まれており、3ビットが取り得る値の一覧表になっています。 3ビットが取り得る値は 2^{3}=8で8通りなので8種類の値となります。

 0 1
 00 000 001
 01 010 011
 10 100 101
 11 110 111

この表、縦方向の b_{2} b_{1} 00 01 10 11という順番に割り振ってありますが最後の2つ黄色の塗りつぶしの部分の順番を入れ替えて 00 01 11 10としてみます。 このようにして作られた表には面白い性質があります。

 0 1
 00 000 001
 01 010 011
 11 110 111
 10 100 101

 000からスタート、一つ下に進むと 010になり 000と比べると b_{1}だけが 0から 1に変化します。
 010から更に一つ下に進むと 110になり 010と比べると b_{2}だけが 0から 1に変化します。
 110から更に一つ下に進むと 100になり 110と比べると b_{1}だけが 1から 0に変化します。
更に一つ下に進めてみようかな、と思ったのですがもうこれ以上、下はないので先頭の行に戻ると 000になり 100と比べると b_{2}だけが 1から 0に変化します。 ここでは上下に移動しましたが、左右の移動も変化するビットは1ビットだけになっています。
最初の表では 010の下は 100ですから b_{2} 0から 1 b_{1} 1から 0に変化しているので2ビット変化していますね。

このように上下左右とは1ビットしか異ならないように値を並べた表を「カルノー図」と呼びます。

表のはじまで行ったとき反対側に移動するのが面倒なら表自体を上下左右に伸ばして更に続きがあるんだ、と考えると簡単です。 下の表は中央、青塗りつぶしのまわりに同じ表をつなげてみました。

 0 1 0 1 0 1
 00 000 001 000 001 000 001
 01 010 011 010 011 010 011
 11 110 111 110 111 110 111
 10 100 101 100 101 100 101
 00 000 001 000 001 000 001
 01 010 011 010 011 010 011
 11 110 111 110 111 110 111
 10 100 101 100 101 100 101
 00 000 001 000 001 000 001
 01 010 011 010 011 010 011
 11 110 111 110 111 110 111
 10 100 101 100 101 100 101

2ビットでは隣との違いは必ず1ビットとなるのでマトリクスにすると自然とカルノー図になっているんですね。

4ビットのカルノー

4ビットのカルノー図は横方向も2ビット割り当てます。
値の並びは縦方向と同じく隣同士が1ビット違いになるようにします。
上下左右に移動したとき変化するビットは1ビットのみになっていますね。

 00 01 11 10
 00 0000 0001 0011 0010
 01 0100 0101 0111 0110
 11 1100 1101 1111 1110
 10 1000 1001 1011 1010

5ビットのカルノー

4ビットまでのカルノー図は上記のとおり容易に作成できますが、更にビット数を増やそうとするとちと面倒なことが起こります。 縦方向は 000 001 011 010 110 111 101 100と1ビットづつ変化するように配置して以下のような表ができます。 なにか、上手いことできているように見えますが黄色のセルを見てください。
 01100 11100なので1ビットしか変化していないのですが、隣同士ではないんです。 5ビットになると変化するビットは5個、移動方向も5個ないといけないのですが、移動方向は上下左右の4通りなのですからもう一つ、新しい移動方向を考える必要があるのです。黄色のセルはこの新しい移動方向で隣同士になる、ということになります。

 00 01 11 10
 000 00000 00001 00011 00010
 001 00100 00101 00111 00110
 011 01100 01101 01111 01110
 010 01000 01001 01011 01010
 110 11000 11001 11011 11010
 111 11100 11101 11111 11110
 101 10100 10101 10111 10110
 100 10000 10001 10011 10010

新しい移動方向は

  • 2行目と7行目
  • 3行目と6行目

になります。
でも、なんか分かりづらいですね・・・
ということで少し考え方を変えてみましょう。上下左右の移動は2次元平面での移動ですから移動方向を増やしたければ3次元にしてやればよいのでは?

ということで、3次元バージョンの5ビットカルノー図です。 5ビットでは4ビットのカルノー図を2階建にします。移動方向は上下左右に加えて1階、2階を行き来できます。
5ビットの b_{4} b_{3} b_{2} b_{1} b_{0} b_{4}を1階、2階に割り当てて以下のようにしましょう。
1階  b_{4}=0

 00 01 11 10
 00 00000 00001 00011 00010
 01 00100 00101 00111 00110
 11 01100 01101 01111 01110
 10 01000 01001 01011 01010

2階  b_{4}=1

 00 01 11 10
 00 10000 10001 10011 10010
 01 10100 10101 10111 10110
 11 11100 11101 11111 11110
 10 11000 11001 11011 11010

先ほど、隣同士になっていなかった 01100 11100も1階と2階で隣どうしになれました。これで5ビットすべて隣は1ビット違いとなりました。

6ビットのカルノー

ここまでの流れを考えれば6ビットは簡単ですね。
そうです、4階建てにします。

1階  b_{5}b_{4}=00

 00 01 11 10
 00 000000 000001 000011 000010
 01 000100 000101 000111 000110
 11 001100 001101 001111 001110
 10 001000 001001 001011 001010

2階  b_{5}b_{4}=01

 00 01 11 10
 00 010000 010001 010011 010010
 01 010100 010101 010111 010110
 11 011100 011101 011111 011110
 10 011000 011001 011011 011010

3階  b_{5}b_{4}=11

 00 01 11 10
 00 110000 110001 110011 110010
 01 110100 110101 110111 110110
 11 111100 111101 111111 111110
 10 111000 111001 111011 111010

4階  b_{5}b_{4}=10

 00 01 11 10
 00 100000 100001 100011 100010
 01 100100 100101 100111 100110
 11 101100 101101 101111 101110
 10 101000 101001 101011 101010

7ビット、8ビットのカルノー

最後、7ビットと8ビット。7ビットなら移動方向は7種類、8ビットなら移動方向は8種類必要になります。
上下左右に上の階、下の階と3次元の移動方向は使い果たしてしまいました。 そこで建物を増築します。1号館、2号館と2棟構成にしたのが7ビット、1号館から4号館の4棟構成にしたのが8ビットのカルノー図になります。
移動方法は・・・、空間移動です。とある部屋から別の棟の同じ位置の部屋に移動することができます。
 
7ビットの棟構成
1号棟  b_{6}=0
2号棟  b_{6}=1
 
8ビットの棟構成
1号棟  b_{7}b_{6}=00
2号棟  b_{7}b_{6}=01
3号棟  b_{7}b_{6}=11
4号棟  b_{7}b_{6}=10
 
ここまでくると、論理式の簡略化としての用途には使いずらくなってきます。まぁ、頑張ればできますが普通は6ビットぐらいまででしょうか。
しかし、ここではハミング距離のイメージを掴むためにカルノー図を用いるので、このワンフロア16部屋、4階建て、4棟構成のカルノー図でも十分に使うことができます(たぶん・・・)

ハミング距離はどうしたんだよ・・・

はい、おまたせしました。
やっとここからがハミング距離の説明です!!

エラー検出・訂正で使用するハミング距離とは2つの値の異なるビットの数となります。
そしてカルノー図上では異なる部屋の間の距離となります。
この距離とは一般的な距離の測り方とは少し異なります。とある部屋から1ビットしか異ならない部屋への移動を1として最短で何部屋移動するか、が距離となります。 4ビットのカルノー図で考えてみましょう。

  1. 黄色の部屋 0101と緑色の部屋 0100のハミング距離は1
  2. 黄色の部屋 0101と青色の部屋 1111のハミング距離は2
  3. 緑色の部屋 0100とオレンジ色の部屋 0110のハミング距離は1
 00 01 11 10
 00 0000 0001 0011 0010
 01 0100 0101 0111 0110
 11 1100 1101 1111 1110
 10 1000 1001 1011 1010

1はすぐ隣なので 0101から左に行って 0100で1、2は 0101から右に行って 0111、下に行けば 1111なので2、これはいいですね。
3は 0100から右に行って 0101、更に右に行って 0111、もひとつ右に行って 0110だから3じゃないの・・・?と思うかもしれませんがカルノー図は左端と右端は繋がっているので 0100から左に行って 0110だから1になります。 この決まりは階の間の移動でも、棟間の移動でも同じです。

2階建ての5ビットカルノー図で試してみましょう。 黄色の部屋 00000から緑色の部屋 11111までの距離は 00000から1階を右に行って 00001、更に右に行って 00011、下に行って 00111、もひとつ下に行って 01111、2階に上って 11111でハミング距離5となります。どのような経路を辿ってもこれより短い経路はありません。 実際にカルノー図を辿ってみてくださいね。

1階  b_{4}=0

 00 01 11 10
 00 00000 00001 00011 00010
 01 00100 00101 00111 00110
 11 01100 01101 01111 01110
 10 01000 01001 01011 01010

2階  b_{4}=1

 00 01 11 10
 00 10000 10001 10011 10010
 01 10100 10101 10111 10110
 11 11100 11101 11111 11110
 10 11000 11001 11011 11010

 
5ビットで全ビットが0だったのが全ビット1になったのだから異なるビットは5個でハミング距離は5、と見ただけでわかりますがこの後カルノー図を使ってエラー検出できる、できない、エラー訂正できる、できない、エラー検出・訂正ができるなら何ビットまでできるのか、の考察を行うので頭の中でカルノー図とハミング距離をイメージできるようにしておきましょう。

余談と次回予告

マンハッタン距離

カルノー図上でのハミング距離を数学用語で言うと『マンハッタン距離』となります。
一般の距離は『ユークリッド距離』と言って2点間を直線でつないだときの直線の長さとなります。これに対して『マンハッタン距離』は各座標軸での距離の和となります。マンハッタンの碁盤の目のような道路を進んでいったときの距離って感じですかね。斜めにショートカットすれば近いんだけどもそれはできない、碁盤の目を右に左に行った時の距離ということです。
ただ、マンハッタンの道路の右端と左端は繋がっていませんがカルノー図の右端と左端、上端と下端は繋がっているので計算するときはこれを考慮に入れる必要がありますね。

グレイコード

3ビットのカルノー図を作る際に 00 01 11 10という並びを使用しました。隣同士が1ビットしか変化しない並びです。
このようなコードをグレイコードと呼びます。5ビットのカルノー図を作る際に最初に考えた 000 001 011 010 110 111 101 100という並びも隣同士は1ビットしか変化しないのでグレイコードですね。
ソフトウェアではあまりお目にかかりませんがハードウェアではよく使う手法となります。 一度に複数のビットが変化すると回路を構成する部品の微妙な動作時間の違いから本来出力されるべきではないコードが一瞬みえてしまい、これが誤動作の引き金になったりします。ここでグレイコードを使うと変化するのは必ず1ビットですから部品の動作時間のバラツキに関わらず正しいコードしか出力されないことになります。
一見、複雑そうなコードの並びですが信頼性を上げる重要な手法なんですね。

超立方体

2次元の座標で正方形を考えます。頂点が4個あってそれぞれの頂点からは2本の同じ長さの辺が出ており頂点で直角に交わっています。
では3次元の座標で立方体を考えます。頂点が8個あってそれぞれの頂点からは3本の同じ長さの辺が出ており頂点で直角に交わっています。
では4次元の座標だったら?
2次元から3次元に拡張したとこと同じように3次元から4次元に拡張すると頂点が16個あってそれぞれの頂点からは4本の同じ長さの辺が出ており頂点で直角に交わっている、そんな形になりそうです。
でもこれ、3次元の座標では作ることはできないですよね。頂点から4本の辺が出ていてそれぞれが直角に交わっている、この時点で3次元では実現できません。この4次元、あるいはそれ以上の次元での立方体を超立方体といいます。
4次元なので2次元や3次元で作ることはできませんが、条件をゆるめれば図にすることはできます。たとえば頂点で各辺が直角に交わっている、各辺の長さは同じ、という条件を外して書いたのがハミング距離 - Wikipediaの図になります。 実はカルノー図を7ビットに拡張するときにも4次元をどう扱うか、という問題に直面しています。この時は隣の棟に空間移動できる、というズルをして解決しましたね。

次回予告

さて、ハミング距離もわかってきたので次回はエラー検出・訂正とハミング距離について考えてみましょう。

思考のサルベージ(その8)

各工程で心がけたい思想を掘り起こしてみる

今回は、設計工程における「過剰設計」について考えてみます。対向装置の挙動が不透明な状態で設計をすすめると、「過剰設計」になることがあります。「過剰設計」とその弊害とは一体何でしょうか。

準正常系の設計

以前にもお話させていただきましたが、規格に準拠する設計では、正常系、異常系は規格に沿った設計をしていればまず間違いありません。ただし、準正常系では、各メーカに設計がゆだねられることが多いです。 例えば、規格で以下のシーケンスが規定されていて、装置Aの設計をするとしましょう。

装置Bから装置Aに「特定のアクセスが一定回数」続いたら、

  • 1.装置Aが装置Bにデータ取得指示を出す。
  • 2.装置Bは装置Aにデータ取得要求を出す。
  • 3.装置Aは装置Bにデータを送信する。

装置Aは装置Bがデータを取得したと認識する。

正常系の設計は明快ですね。装置A、装置Bの間でやり取りされるメッセージのプロトコル違反は異常系に落とし込めます。

では、「1」のシーケンスが動いた後、「2」のシーケンスが動かなかった場合はどうしましょう?一見すると、装置Bが規格に沿った動作をしないケースとなります。そのまま放置してもよさそうです。でも、装置Aからの取得指示が装置B届いてないケースもあり得ます。メッセージキューが詰まっていて、送信自体が出来ていないのかもしれません。

過剰設計はなぜうまれる?

ソフトウェア開発の現場では、対抗装置の挙動が不透明だったりすると、極力正常系に落とし込めるような設計にしたがる傾向があります。もちろん必要な設計である場合がほとんどでしょう。ただ、工程が進み対向装置の動作が明確になってくると、準正常系でのケアが不要だったことや、実は規格・機能の目的からい逸脱していることが発覚したりします。準正常系設計時にこそ、規格・機能の目的を把握していることが重要といえます。

過剰設計の弊害

とはいえ、準正常系を手厚くしただけ動作的には問題なさそうです。ただし、判定分、検索処理が多発することによるオーバーヘッドは確実に増加します。競合他社と処理速度を競うような装置の場合は、致命傷になりかねません。また、システムテストの立場では、あらゆるケースでの動作を反映したテストを実行しなければなりません。また、そこで不具合が発見されれば、複雑化した準正常系の処理を修正するために処理がさらに複雑化するかもしれません。対向装置に挙動が不透明ならば、「評価視点」を設計に加味してみるのもいいかもしれません。

何か掘り起こせた?

  • 準正常系こそ規格、機能の意図を正確に把握することが必要。
  • 評価視点を考慮した設計も必要。

過剰設計はある意味避けきれないのかもしれません。それでも、そのリスクを認識し、できうる限りシンプルな設計を目指したいですね。

おしまい

対向装置の動きが不明なまま設計を進めるなんて状況が回避できればなにも問題ないんですけどね、とか言ってもしかたあるまい。