概要

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

この分野は、データをどれだけ効率よく表せるか、処理の流れをどうモデル化するか、アルゴリズムの効率をどう評価するかを扱う。
用語だけでなく、簡単な例で意味を結び付けると理解しやすい。

この記事で扱うこと

• 情報量と平均情報量の考え方。
• ハフマン符号が出現頻度に応じて符号長を変える理由。
• 有限オートマトンと状態遷移の読み方。
• BNF記法で文法を表す考え方。
• 計算量をオーダー記法で比較する見方。

理解しておきたい要点

情報量

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

• 選択情報量（自己エントロピー）
  ある特定の事象が起こるときの情報量のこと。

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

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

• 平均情報量（自己エントロピー）
  起こりうる事象の平均情報量のこと。

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

  事象が起こる確率：\(P\)、起こりうる事象数：\(i = 1,2,3, \cdots n\) と置くと

  \[ \displaystyle = \sum_{i=0}^n ( - \log_2 P) \times 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%\) である時の平均情報量
    → すでにビットで表現されているため、各ビットの桁数が選択情報量となる
    よって
    \(1 \times 0.5\) \(+ 2 \times 0.3\) \(+ 3 \times 0.1\) \(+ 3 \times 0.1\)
    \(= 0.5 + 0.6\) \(+ 0.3 + 0.3\) \(= 1.7\)
    \(= 1.7\ 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)\)
  線形時間：データ量と時間が比例し、for文等のループだけで処理が終わるようなアルゴリズム。
  ※ 使用例：非ソート配列の探索 等

• \(O\ (log\ n)\)
  対数時間：実行単位で処理対象が減るアルゴリズム。
  データ量が増えても計算時間がほとんど増えない。
  ※ 使用例：ソート済み配列の二分探索 等
  （低の大小による差は微々たるものなので低は省略。）

• \(O\ (n\ log\ n)\)
  線形対数時間：線形時間 \(O\ (n)\) と 対数時間 \(O\ (log\ n)\)を掛け合わせたアルゴリズム。
  ※ 使用例：クイックソート、マージソート、ヒープソート 等の高速ソート

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

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

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

• 機械学習
  AI技術の一つで教師データがない学習と教師データがある学習で、以下のような特徴・アルゴリズムがある。

  • 教師データがない学習
    

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

  • 教師データがある学習
    

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

• ディープラーニング（深層学習）
  隠れ層（人間の神経回路網をモデルにしたニューラルネットワーク内の信頼性を高める情報伝達層）を複数層とすることで、より複雑な学習を可能とした学習モデル。
  

  また、ディープラーニングに用いられているアルゴリズムには、画像解析など用いられる畳込ニューラルネットワーク（CNN）や文章の翻訳や生成などの自然言語処理などで用いられる再帰型ニューラルネットワーク（RNN）などがある。

違いを整理する

実務とのつながり

• 情報量
  データ圧縮や通信量の見積もりの基礎になる。

• ハフマン符号
  圧縮アルゴリズムの考え方を理解する入口になる。

• オートマトン
  入力検証、状態遷移、プロトコル設計の理解に役立つ。

• 計算量
  実装した処理がデータ増加に耐えられるかを判断する材料になる。

まとめ

• 情報理論では、情報の量、表現、状態遷移、処理効率を数学的に扱う。
• ハフマン符号は、出現頻度に応じて符号長を変える可逆圧縮の代表例となる。
• 計算量は、アルゴリズムの効率を比較するための重要な指標となる。

参考文献

• 瀬戸 美月（\(2020\)）『徹底攻略 応用情報技術者教科書』株式会社インプレス