概要

情報技術の基礎として理解しておきたい情報理論について、情報量、ハフマン符号、オートマトン、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\) のマッピングが出来上がり、圧縮 / 解凍（復元）が可能となる。

オートマトン

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

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

  • 例 : 入力記号が \(\{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\) に遷移

    • 状態遷移図で表現
      

      　

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

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

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

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

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

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

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

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>

計算量

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

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

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

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

• \(O\ (log\ n)\)
  対数時間：実行単位で処理対象が減るアルゴリズム。
  データ量が増えても計算時間がほとんど増えない。
  ※ 使用例：ソート済み配列の二分探索 等
  （対数の底が異なっても定数倍の差となるため、\(O\) 記法では通常、底を省略する。）

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

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

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

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

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

  • 教師データがない学習
    

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

  • 教師データがある学習
    

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

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

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

まとめ

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

参考文献

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