概要

情報技術の基礎として理解しておきたい 情報理論 について、情報量、ハフマン符号、オートマトン、BNF記法、計算量、機械学習の基礎を整理する。

符号を元に戻す手順、状態遷移、スタックの中身を順番に追い、定義が実際の処理へどうつながるかを確かめる。比較回数を数えて計算量の式を読む練習も行う。

この記事の構成

• 情報量
  情報量：事象の起こりにくさを示す尺度のこと。
• ハフマン符号
  頻度から符号木を作り、区切りなしで復元できる理由と符号長を確認。
• オートマトン
  オートマトン：入力から出力に至る過程（状態遷移）をシステムモデル化したもの。
• 走査順と逆ポーランド表記法
  走査順：グラフ理論の木構造においてそれぞれのノード（節点）を評価する順番のこと。
• BNF記法
  BNF記法（Backus-Naur Form）：文法等を形式定義するために用いられる言語のことでプログラミング言語の定義にも利用される。
• 計算量
  組合せの比較回数を数え、処理回数の式からオーダーを読み取る。
• 機械学習とディープラーニング
  AI（人工知能）：人間と同様の知能をコンピュータ上で実現させるための技術や分野のこと。

情報量

• 情報量
  事象の起こりにくさを示す尺度のこと。
  （その事象が稀である程情報量が多くなる。）

• 選択情報量（自己情報量）
  ある特定の事象が起こるときの情報量のこと。

  選択情報量は次の式で表現できる。
  事象が起こる確率：\(P\) と置くと
  \(- \log_2 P\ bit\)

  • 例 : ある事象が起こる確率 \(50%\) である場合の選択情報量
    \(- \log_2 0.5\) \(= - \log_2 2^{-1} = 1\)
    よって、選択情報量は \(1\ bit\)

• 平均情報量（エントロピー）
  起こりうる各事象の選択情報量を生起確率で重み付けした平均（期待値）のこと。

  平均情報量は次の式で表現できる。

  各事象が起こる確率：\(P_i\)、起こりうる事象数：\(n\) と置くと

  \[ \displaystyle H = -\sum_{i=1}^n P_i \log_2 P_i\ bit \]

  • 例 \(1\) : 事象 \(3\) つが起こる確率がそれぞれ\(25%\)、\(25%\)、\(50%\)である場合の平均情報量
    \(= - \log_2 0.25\) \(\times 0.25\) \(- \log_2 0.25 \times 0.25\) \(- \log_2 0.50 \times 0.50\)
    \(= - \log_2 2^{-2}\) \(\times 0.25\) \(- \log_2 2^{-2} \times 0.25\) \(- \log_2 2^{-1} \times 0.50\)
    \(= 2 \times 0.25 + 2\) \(\times 0.25 + 1 \times 0.50\)
    \(= 1.50\ bit\)

  • 例 \(2\) : \(4\) つの記号にビット列 \(0,\ 10,\ 110,\ 111\) を割り当て、出現頻度がそれぞれ \(50%\)、\(30%\)、\(10%\)、\(10%\) であるときの平均符号長
    → 各ビット列の桁数は符号長であり、出現確率で重み付けした平均が平均符号長となる。
    \(L = 1 \times 0.5 + 2 \times 0.3 + 3 \times 0.1 + 3 \times 0.1 = 1.7\) bit/記号

    一方、この確率分布の平均情報量（エントロピー）は
    \(H = -0.5 \log_2 0.5 - 0.3 \log_2 0.3 - 0.1 \log_2 0.1 - 0.1 \log_2 0.1 \fallingdotseq 1.685\) bit/記号となり、平均符号長とは異なる。

ハフマン符号

• エントロピー符号
  目的に沿ってより簡単な表現となるように、事象の出現確率を考慮し、事象ごとに長さの符号を割り当てる考え方。

• ハフマン符号
  エントロピー符号の一つで、\(2\) 分岐構造を利用した元情報へ復元可能な可逆圧縮技術の代表例。

  • 例 : 文字列"\(abababcdaa\)"のハフマン圧縮
    → 文字列"\(abababcdaa\)"の出現頻度はそれぞれ \(a = 50%\)、\(b = 30%\)、\(c = 10%\)、\(d = 10%\)

    この文字列をより少ない情報で表現するために \(2\) 分岐構造を用いて出現頻度が高い方からより少ないビット数を割り当てる。
    → \(a = 0,\ b = 10\) \(,\ c = 110,\ d = 111\)

    このとき \(2\) 分岐構造により可逆（復元可能）となるため、文字列 \(a,\ b,\ c,\ d\) とビット \(0,\ 10,\ 110,\ 111\) のマッピングが出来上がり、圧縮 / 解凍（復元）が可能となる。

• 短い符号でも区切りなしで復元できる理由
  例の頻度では最小の10%と10%をまとめて20%、次に20%と30%をまとめて50%、最後に50%と50%をまとめる。これがハフマン木を下から作る手順である。左右への0と1の割当てによって符号自体は変わるが、この例の符号長は1、2、3、3となる。

  0 、 10 、 110 、 111 のどれも別の符号の先頭部分にはなっていない。この 接頭語のない性質 により先頭から葉に到達するたびに一文字を確定できる。例えば 010110 は 0 | 10 | 110 と読め、 abc に戻る。単に二分木を使うだけでなく、記号を葉に割り当てることが大切になる。

  abababcdaa の符号本体は \(5\times1+3\times2+1\times3+1\times3=17\) bit。4種類を一律2 bitで表す20 bitより短い。ただし、符号表を伝える情報などは含めていないため、この短い文字列をファイル化して必ず小さくなるとは限らない。

オートマトン

• オートマトン
  入力に応じて状態が移り変わる仕組みをモデル化したもの。
  一般的に状態遷移図や状態遷移表で表現される。

  オートマトンのうち状態の集合が有限であるものを有限オートマトンという。入力列を受理する有限オートマトンは、状態集合、入力記号の集合、遷移規則、初期状態、受理状態の集合によって定義される。

  • 例 : 入力記号が \(\{0,\ 1\}\) で状態集合が \(\{a,\ b,\ c,\ d\}\) である有限オートマトンの遷移規則を状態遷移表と状態遷移図で表現する。ここでは初期状態と受理状態を指定していないため、入力列を受理するかどうかではなく遷移規則だけを示す。

    • 状態遷移表

      	\(0\)	\(1\)
      \(a\)	\(a\)	\(b\)
      \(b\)	\(c\)	\(d\)
      \(c\)	\(a\)	\(b\)
      \(d\)	\(c\)	\(d\)

    • 状態遷移表の見方

      	\(0\)	\(1\)
      \(a\)	\(a\) \(a\) に \(0\) を入力 → \(a\) に遷移	\(b\) \(a\) に \(1\) を入力 → \(b\) に遷移
      \(b\)	\(c\) \(b\) に \(0\) を入力 → \(c\) に遷移	\(d\) \(b\) に \(1\) を入力 → \(d\) に遷移
      \(c\)	\(a\) \(c\) に \(0\) を入力 → \(a\) に遷移	\(b\) \(c\) に \(1\) を入力 → \(b\) に遷移
      \(d\)	\(c\) \(d\) に \(0\) を入力 → \(c\) に遷移	\(d\) \(d\) に \(1\) を入力 → \(d\) に遷移

    • 状態遷移図で表現
      

      　

• 同じ遷移表から入力列の受理を判定する
  上の表に 初期状態はa、受理状態はdだけ という条件を追加してみる。入力 1011 を一文字ずつ読むと、a→b→c→b→dとなり、読み終えた状態がdなので受理する。

  一方、入力 100 はa→b→c→aとなり、受理しない。途中でどの状態を通ったかだけでなく、入力をすべて読んだ時点の状態で判定する。このように遷移表だけでは足りなかった初期状態と受理状態を指定することで、入力列を判別する仕組みになる。

走査順と逆ポーランド表記法

• 走査順
  グラフ理論の木構造においてそれぞれのノード（節）をたどる順番のこと。

• 走査順の種類
  二分式木を深さ優先でたどる代表的な順序には、以下 \(3\) 種類がある。式木では演算子とオペランドを取り出す順序によって前置・中置・後置の各表記を得られる。

  • 先行順
    → 親ノードを左右の子ノードより先にたどる。式木では演算子を先に取り出す前置表記法またはポーランド表記法となる。
    ※ \(A\)と\(B\)の加算は\(+ AB\)という表現となる。

  • 中間順
    → 左の子、親、右の子の順にたどる。式木では演算子をオペランドの間に置く中置表記法となる。
    ※ \(A\)と\(B\)の加算は\(A + B\)という表現となる。

  • 後行順
    → 左右の子ノードを親ノードより先にたどる。式木では演算子を最後に取り出す後置表記法または逆ポーランド表記法となる。
    ※ \(A\)と\(B\)の加算は\(AB +\) という表現となる。

  • 例 : \(Y = (A + B)\)\(\times (C - (D \div E))\)の逆ポーランド表記法
    → \(YAB + CDE\) \(\div - \times =\)

• スタックを使って逆ポーランド式を計算する
  逆ポーランド式 2 3 + 4 * は、数値ならスタックに積み、演算子なら二つ取り出して計算する。

  読んだ要素	操作後のスタック（右が先に取り出される側）
  2	[2]
  3	[2, 3]
  +	[5]
  4	[5, 4]
  *	[20]

  演算に必要な値が先に積まれているので、括弧なしで \((2+3)\times4=20\) を計算できる。減算と除算では順序に注意する。 8 2 - は先に取り出した2を右辺、次の8を左辺にして \(8-2=6\) とする。

BNF記法

• BNF記法（Backus-Naur Form）
  文法等を形式定義するために用いられる言語のことでプログラミング言語の定義にも利用される。
  繰返し表現に 再帰 を使う。

  • 例 : 識別子（identifier）は先頭が英字でそれ以降が任意個の英数字である。
    この時次の定義下において識別子（identifier）をBNFで定義。
    <digit> \(::= 0\ |\ 1\ |\ 2\ |\ 3\ |\) \(\cdots |\ 9\ \)
    <letter> \(::= A\ |\ B\ |\ C\ |\) \(\cdots |\ Z\ |\ a\ |\ b\ |\ c\ |\) \(\cdots |\ z\)

    識別子（identifier）の定義は
    <identifier>\(\ ::=\ \)<letter>\(\ |\ \)<identifier><digit>\(\ |\ \)<identifier><letter>

• 再帰する規則と再帰を終える規則
  例の規則では <identifier> を <letter> に置き換えれば、 a という識別子を作れる。さらに <identifier><digit> という選択肢によって a7 、 <identifier><letter> によって a7B を作れる。

  再帰する選択肢はすでに作れる識別子の 末尾 に文字を足している。基礎となる最初の一文字は必ず英字なので、 7a は導出できない。また、 <letter> に置き換える選択肢がなければ再帰を終えられず、有限長の識別子を作れない。再帰規則と終了できる規則は組として読む必要がある。

計算量

• 計算量（オーダー）
  アルゴリズムの実行時間を入力データを基準に増加量で表したもの。
  計算量は\(O\) - 記法という表記法で \(O\)（オーダー）と呼ばれる概念を用いる。
  \(O\) - 記法は入力データが十分に大きいときのステップ数を大雑把に見積もることができ、アルゴリズムの評価（性能の良さ）を計る場合に用いる。

以下、代表的な \(O\)（オーダー）達。

• \(O\ (1)\)
  定数時間：データ数 \(n\) に依存しない定数個のステップで実行できるアルゴリズム。1ステップだけとは限らない。
  ※ 使用例：配列要素への添字アクセス、ハッシュ表の平均的な検索 等。衝突の状況や実装によってハッシュ表の最悪計算量は \(O(n)\) となる。

• \(O\ (n)\)
  線形時間：データ量と時間が比例し、for文等のループだけで処理が終わるようなアルゴリズム。
  ※ 使用例：非ソート配列の探索 等

• \(O\ (log\ n)\)
  対数時間：実行単位で処理対象が減るアルゴリズム。
  対象を毎回半分に絞る場合、データ量が2倍になるごとに絞り込む回数が約1回増える。
  ※ 使用例：ソート済み配列の二分探索 等
  （対数の底が異なっても定数倍の差となるため、\(O\) 記法では通常底を省略する。）

• \(O\ (n\ log\ n)\)
  線形対数時間：線形時間 \(O\ (n)\) と 対数時間 \(O\ (log\ n)\)を掛け合わせたアルゴリズム。
  ※ 使用例：マージソート、ヒープソート、平均的なクイックソート 等。クイックソートの最悪計算量は \(O(n^2)\) となる。

• \(O\ (n^2)\)
  二乗時間：線形時間 \(O\ (n)\) を二乗したアルゴリズムで単純な二重ループ等（各行各列を単純列挙など）が該当する。
  ※ 使用例：挿入ソート、バブルソート 等

• 処理回数の式からオーダーを読む
  全データの組を重複なく比較する場合、比較回数は \((n-1)+(n-2)+\cdots+1=n(n-1)/2\) となる。\(n=10\) で45回、\(n=20\) で190回であり、データ数が2倍になっても比較回数は2倍では済まない。

  式を展開すると \(n^2/2-n/2\)。大きな \(n\) では二乗の項が支配的になるため、\(O(n^2)\) と整理する。これは実行時間が常に正確に \(n^2\) 秒になるという意味ではない。実測時間の比較には一回の処理の重さや入出力の量も必要になる。

機械学習とディープラーニング

• AI（人工知能）
  人間と同様の知能をコンピュータ上で実現させるための技術や分野のことを指す。
  実用化の事例：画像認識、音声認識、テキスト翻訳 等

• 機械学習
  AI技術の一つ。代表的な学習方法として教師データがない学習と教師データがある学習には以下のような特徴・アルゴリズムがある。このほか、強化学習などの方法もある。

  • 教師データがない学習
    

    • 準備データ
      → 学習データのみ。
    • 可能な処理
      → クラスタリング（データ間の類似度に基づきデータ分類。）
    • 代表的なアルゴリズム
      → k-means、Ward法 等。

  • 教師データがある学習
    

    • 準備データ
      → 学習データと正解データ
    • 可能な処理
      → 分類、回帰
    • 代表的なアルゴリズム
      → サポートベクタマシン、ニューラルネットワーク、ディープラーニング 等。

• ディープラーニング（深層学習）
  複数の中間層を持つニューラルネットワークを用い、データから階層的な特徴表現を学習する機械学習の方法。層を増やせば常に精度や信頼性が高くなるわけではなく、データ量、モデル構造、学習方法などによって性能は変わる。
  

  代表的なニューラルネットワークの構造には画像処理などで用いられる畳み込みニューラルネットワーク（CNN）、系列データを扱う再帰型ニューラルネットワーク（RNN）、自然言語処理などで広く用いられるTransformerなどがある。

まとめ

• 特定事象の情報量が選択情報量、その期待値が平均情報量、割り当てた符号語長の期待値が平均符号長。
• 符号化は情報の表現を変換し、暗号化は秘匿を目的とする。ハフマン符号は出現頻度に応じて符号長を変える可逆圧縮の代表例。
• オートマトンは状態と入力による遷移を表し、BNFでは::=を定義、|を選択肢として読む。
• 計算量はアルゴリズムの効率を比較する指標で、O(n)とO(log n)ではデータ増加時の処理回数の伸び方が異なる。

• 復元できる符号には区切りを判断できる性質が必要になる。処理の効率を比べるときは具体的な回数から入力サイズに対する増え方を読み取る。

参考文献

• 瀬戸 美月（\(2020\)）『徹底攻略 応用情報技術者教科書』株式会社インプレス
• 情報通信研究機構 - 画像圧縮と情報量（日本語・エントロピーと符号化の公的解説）
• Claude E. Shannon, A Mathematical Theory of Communication（英語・情報理論の原論文）