早稲田大学大学院 理工学研究科
博士論文審査報告書
論 文 題 目
漸近正規性を用いた可変長無歪み情報源 符号化の性能評価に関する研究
A Study on Performance Evaluations of Variable-Length Source Coding Based on
the Asymptotic Normality
申 請 者
野村 亮
Ryo NOMURA
2007 年 12 月
1
携 帯 電 話 や イ ン タ ー ネ ッ ト に 代 表 さ れ る 今 日 の 情 報 化 社 会 に お い て ， 情 報 通 信 技 術 の 果 た す 役 割 は ま す ま す 増 大 し て い る ． ま た ， 近 年 美 術 館 や 博 物 館 等 の 文 化 財 を デ ジ タ ル 化 し て 保 存・ 公 開 す る「 デ ジ タ ル ア ー カ イ ブ 」「 ヴ ァ ー チ ャ ル ミ ュ ー ジ ア ム 」 構 想 な ど 大 容 量 デ ー タ を 保 存 す る 機 会 と 重 要 性 も 増 加 の 一 途 を 辿 っ て い る ． 本 論 文 で 扱 う 情 報 源 符 号 化 は こ れ ら デ ー タ の 記 憶 ・ 伝 送 を 数 理 モ デ ル 化 し た 情 報 工 学 の 重 要 な 一 分 野 で あ る ．
情 報 源 符 号 化 は ， 情 報 源 か ら 出 力 さ れ る 系 列 （ 情 報 源 系 列 ） の 冗 長 性 を 取 り 除 き ， よ り 短 い 系 列 （ 符 号 系 列 ） に 変 換 す る 技 術 で あ る ． こ の 変 換 操 作 を 符 号 化 と 呼 び ， 変 換 規 則 を 符 号 と 呼 ぶ ． ま た ， 記 憶 ・ 伝 送 さ れ た 符 号 系 列 を 情 報 源 系 列 に 復 元 す る 操 作 を 復 号 と 呼 ぶ ． 情 報 源 か ら 出 力 さ れ る 系 列 は あ る 確 率 分 布 に 従 い 確 率 的 に 発 生 す る と 仮 定 し ， こ の 確 率 分 布 が 既 知 の 場 合 と 未 知 の 場 合 の 双 方 の 問 題 設 定 が あ る ．
情 報 源 符 号 化 は さ ら に 無 歪 み 情 報 源 符 号 化 と 有 歪 み 情 報 源 符 号 化 の 二 つ に 大 別 で き る ． 無 歪 み 情 報 源 符 号 化 と は ， 符 号 系 列 か ら 情 報 源 系 列 が 完 全 に 復 元 可 能 な 符 号 化 （ お よ び 復 号 化 ） 技 術 で あ り ， プ ロ グ ラ ム フ ァ イ ル や 文 書 デ ー タ の 圧 縮 等 ， 可 逆 性 が 必 要 な 場 合 に 用 い ら れ る ． 一 方 ， 必 ず し も 可 逆 性 を 必 要 と し な い 画 像 や 音 声 等 の 圧 縮 に お い て は ， 有 歪 み 情 報 源 符 号 化 を 用 い る こ と が 多 い ． 本 論 文 で は 無 歪 み 情 報 源 符 号 化 を 取 り 扱 っ て い る ． ま た ， 本 論 文 で 対 象 と す る 可 変 長 符 号 化 と は 符 号 化 後 の 長 さ （ 符 号 長 と 呼 ぶ ） が 情 報 源 系 列 に 依 存 し て 変 化 す る こ と を 意 味 す る ．
デ ー タ の 効 率 的 な 記 憶 ・ 伝 送 と い う 視 点 か ら ， 情 報 源 符 号 化 の 目 的 は 符 号 長 を 短 く す る こ と と 言 え る が ， 無 歪 み と い う 制 約 の も と で ， 符 号 長 は ク ラ フ ト の 不 等 式 と 呼 ば れ る 制 約 条 件 を 満 た す 必 要 が あ る ． 情 報 源 符 号 化 の 問 題 と は こ の ク ラ フ ト の 不 等 式 を 満 た す と い う 条 件 の も と で ， 符 号 長 を 最 適 化 す る こ と で あ る ． 符 号 長 に 関 す る 代 表 的 な 評 価 基 準 と し て 次 の 3 つ が あ る ． 1 . 平 均 符 号 長 ： 符 号 長 を 情 報 源 系 列 の 出 現 確 率 で 平 均 化 し た 量 で 情 報 源 に
対 す る 符 号 の 平 均 的 な 性 能 を 示 し て い る ．
2 . オ ー バ ー フ ロ ー 確 率 ： 符 号 長 が あ る し き い 値 よ り 長 く な っ て し ま う 確 率 で あ る ． 実 用 上 は ， 符 号 化 後 に バ ッ フ ァ オ ー バ ー フ ロ ー が 生 じ る 確 率 を 表 す ．
3 . 最 大 符 号 長 ： 出 現 し う る 情 報 源 系 列 の 中 で 符 号 長 が 最 も 長 く な る 情 報 源 系 列 に 対 す る 符 号 長 で あ り ， 符 号 の 最 悪 の 場 合 の 性 能 を 表 し て い る ． こ の 問 題 設 定 の も と で ， 研 究 対 象 は ，
1 ) あ る 評 価 基 準 に お け る 限 界 （ 上 限 や 下 限 ） に 関 す る 研 究 2 ) 限 界 に 近 づ く 符 号 の 構 成 法 に 関 す る 研 究
の 2 つ が 考 え ら れ る ． あ る 評 価 基 準 に 関 す る 限 界 と は ， ど の よ う な 符 号 を 用 い て も そ の 限 界 を 越 え る （ 上 回 る あ る い は 下 回 る ） こ と は な い と い う 理 論 上 の 限 界 値 の こ と で ， 符 号 の 絶 対 的 な 評 価 基 準 と な る 重 要 な 量 で あ る ．1 9 4 8
年 に S h a n n o n に よ り 平 均 符 号 長 の 下 限 が 求 め ら れ て 以 来 ，情 報 源 を 一 般 化 し
2
た 上 で 平 均 符 号 長 の 下 限 を 求 め る 研 究 や 最 大 符 号 長 の 下 限 を 議 論 し た 研 究 が 報 告 さ れ て い る ． 特 に ， 平 均 符 号 長 に 対 し て は ， 情 報 源 の 確 率 分 布 が 既 知 の 場 合 ， 未 知 の 場 合 と も に 精 密 な 下 限 が 求 め ら れ て い る が ， 最 大 符 号 長 に 関 し て は 精 密 な 限 界 は 求 め ら れ て い な い ．
一 方 ， 符 号 の 構 成 法 に 関 す る 研 究 も 数 多 く 報 告 さ れ て い る ． 符 号 の 性 能 を 評 価 す る た め に は 複 数 の 基 準 が 考 え ら れ る が ，近 年 特 に 平 均 符 号 長 に 関 し て ， 従 来 よ り も 精 密 な 符 号 長 を 評 価 す る 研 究 が 多 く さ れ て い る ． こ れ は 符 号 の 性 能 を よ り 厳 密 に 評 価 す る た め に は ， 従 来 の 平 均 符 号 長 の 評 価 で は 不 十 分 で あ る こ と を 示 し て い る ． 一 方 で ， 最 大 符 号 長 に 関 し て も 同 様 に 精 密 な 評 価 が 考 え ら れ る が ， そ の よ う な 評 価 を し て い る 研 究 は 未 だ 存 在 し な い ．
ま た ， 実 装 の 面 か ら は 符 号 を 構 成 す る 際 の 計 算 量 や メ モ リ 量 の 評 価 も 重 要 な 意 味 を 持 つ ． 特 に ， 情 報 源 の 確 率 構 造 が 未 知 の 場 合 に お い て 平 均 符 号 長 を 評 価 し た 研 究 は 多 い が ， そ の メ モ リ 使 用 量 は 無 限 大 を 仮 定 し て い る こ と が 多 く ， メ モ リ 量 を 制 限 し た 上 で 平 均 符 号 長 を 評 価 し た 研 究 は ほ と ん ど な い ．
本 論 文 で は 漸 近 正 規 性 を 用 い る こ と に よ り ， 可 変 長 無 歪 み 情 報 源 符 号 化 の 性 能 評 価 に お い て ， 従 来 に 比 べ 精 密 な 結 果 を 与 え て い る ． 具 体 的 に は 下 記 の 問 題 に 対 し て 精 密 な 結 果 を 得 て い る ．
1 . 情 報 源 の 確 率 構 造 が 既 知 の 場 合 の 最 大 符 号 長 の 限 界 の 導 出
2 . 情 報 源 の 確 率 構 造 が 既 知 の 場 合 の 平 均 符 号 長 最 小 符 号（ シ ャ ノ ン 符 号 ）の 最 大 符 号 長 の 導 出
3 . 情 報 源 の 確 率 構 造 が 未 知 の 場 合 の 平 均 符 号 長 最 小 符 号（ ベ イ ズ 符 号 ）の メ モ リ 量 低 減 ア ル ゴ リ ズ ム の 提 案 と 平 均 符 号 長 の 導 出
次 に 本 論 文 の 各 章 の 概 要 を 述 べ る ．
第 1 章 で は ，本 論 文 の 序 論 と し て ，研 究 の 背 景・目 的 に つ い て 述 べ て い る ． 第 2 章 に お い て 本 論 文 の 対 象 と す る 情 報 ・ 通 信 シ ス テ ム の モ デ ル や 情 報 源 符 号 化 の 問 題 設 定 ， 代 表 的 な 評 価 基 準 等 に つ い て 述 べ て い る ．
第 3 章 で は 情 報 源 の 確 率 分 布 が 既 知 の 条 件 で ， 最 大 符 号 長 の 精 密 な 下 限 を 導 出 し て い る ． 従 来 ， 最 大 符 号 長 の 限 界 は 一 般 情 報 源 と い う 極 め て 広 い 情 報 源 の ク ラ ス に 対 し て 評 価 さ れ て い る ．ま た ，そ の 結 果 か ら 定 常 無 記 憶 情 報 源 ・ 定 常 エ ル ゴ ー ド マ ル コ フ 情 報 源 と い う 重 要 な ク ラ ス に お い て は 平 均 符 号 長 と 最 大 符 号 長 の 限 界 が 一 致 す る と い う こ と が わ か っ て い る ． し か し ， そ の 結 果 の 導 出 は 自 己 情 報 量 （ 情 報 源 の 性 質 を 表 す 量 ） に 関 す る 大 数 の 法 則 の 拡 張 が 基 礎 と な っ て お り ， 精 密 な 評 価 で は な い ． 第 3 章 で は ， こ れ に 対 し ， 自 己 情 報 量 の 漸 近 正 規 性 を 用 い た 解 析 を 行 っ て い る ． 自 己 情 報 量 の 漸 近 正 規 性 は 定 常 無 記 憶 情 報 源 ・ 定 常 エ ル ゴ ー ド マ ル コ フ 情 報 源 な ど に お い て も 成 立 す る 性 質 で ， 適 用 範 囲 も 十 分 広 い ． こ の 漸 近 正 規 性 を 用 い る こ と と 最 大 符 号 長 を 最 小 に す る 符 号 を 考 え る こ と に よ り ， 従 来 に 比 べ ， 精 密 に 最 大 符 号 長 の 限 界 を 評 価 し て い る ． ま た ， そ れ に よ り 従 来 の 結 果 で は 明 確 で は な か っ た 平 均 符 号 長 と 最 大 符 号 長 の 限 界 の 差 も 明 確 に し て い る ． 本 章 の 結 果 は ， 今 後 提 案 さ れ
3
る 様 々 な 符 号 を 評 価 す る た め の 指 針 に な る と い う 意 味 で 重 要 な 結 果 で あ る ． 第 4 章 で は 情 報 源 の 確 率 分 布 が 既 知 の 条 件 で ， 符 号 の 精 密 な 最 大 符 号 長 を 求 め て い る ． 情 報 源 の 確 率 分 布 が 既 知 の 場 合 ， 平 均 符 号 長 を 最 小 に す る 符 号 は シ ャ ノ ン 符 号 と し て 知 ら れ て い る ． 第 4 章 で は シ ャ ノ ン 符 号 を 含 む 符 号 の ク ラ ス に 対 し て ， 符 号 長 の 漸 近 正 規 性 を 考 え る こ と に よ り ， そ の 符 号 の 最 大 符 号 長 を 精 密 に 評 価 し て い る ． ま た ， こ の 結 果 と 第 3 章 で 得 ら れ た 最 大 符 号 長 の 下 限 よ り ， シ ャ ノ ン 符 号 が 最 大 符 号 長 を 漸 近 的 に 最 小 に す る こ と が わ か る ． 符 号 を 多 角 的 に 評 価 す る と い う 意 味 で ， 平 均 符 号 長 最 小 符 号 の 最 大 符 号 長 の 解 析 に は ， 大 き な 意 味 が あ る ． シ ャ ノ ン 符 号 は 実 用 上 極 め て 重 要 な 符 号 で ， そ の 最 大 符 号 長 を 評 価 し た 本 章 の 結 果 は 理 論 上 価 値 の 高 い も の で あ る ． 第 5 章 で は 情 報 源 の 確 率 分 布 が 未 知 の 場 合 を 考 え て い る ． 情 報 源 の 確 率 分 布 が 未 知 の 場 合 に 平 均 符 号 長 を ベ イ ズ 基 準 の 意 味 で 最 小 に す る 符 号 は ベ イ ズ 符 号 と し て 知 ら れ て い る が ， ベ イ ズ 符 号 は 後 述 の 意 味 で 実 用 化 へ の 課 題 が 残 っ て お り ， 実 用 化 に 関 す る 研 究 が 望 ま れ て い る ． ベ イ ズ 符 号 に 関 す る 研 究 は
① 符 号 の 構 成 法 に 関 す る 研 究 ， ② 平 均 符 号 長 の 精 密 な 評 価 に 関 す る 研 究 の 2 つ に 大 別 で き る ． 前 者 に 関 し て は ， 計 算 量 を デ ー タ 長 の 多 項 式 オ ー ダ に 抑 え た も と で 厳 密 に ベ イ ズ 符 号 を 構 成 可 能 な ア ル ゴ リ ズ ム が 提 案 さ れ て い る ． し か し ， そ の 構 成 に 必 要 な メ モ リ 量 は デ ー タ 長 に 対 し て 指 数 的 に 増 加 す る こ と が 知 ら れ て い る ． 一 方 ， 後 者 に 関 し て は パ ラ メ ー タ に 関 す る 最 尤 推 定 量 の 漸 近 正 規 性 を 用 い る こ と に よ り 評 価 さ れ て い る が ， メ モ リ 量 を 無 限 に 使 用 で き る と 仮 定 し た 場 合 の 評 価 と な っ て い る ． こ れ に 対 し ， 第 5 章 で は 計 算 量 は 従 来 ア ル ゴ リ ズ ム と 同 等 と し ， 平 均 符 号 長 は 劣 化 す る が そ の メ モ リ 量 を 大 幅 に 低 減 可 能 な 近 似 ベ イ ズ 符 号 化 ア ル ゴ リ ズ ム を 提 案 し て い る ． さ ら に 提 案 ア ル ゴ リ ズ ム の 平 均 符 号 長 の 評 価 に お い て パ ラ メ ー タ に 関 す る 最 尤 推 定 量 の 漸 近 正 規 性 を 用 い る こ と に よ り そ の 符 号 長 を 評 価 し て い る ． 従 来 ， メ モ リ 量 を 制 限 し た 上 で 符 号 長 を 評 価 し た 研 究 は(ベ イ ズ 符 号 以 外 で も)ほ と ん ど 見 当 た ら な い ． 本 章 の 結 果 は ， 符 号 の 性 能 を 保 証 し つ つ ， 実 用 化 へ の 道 を 開 い た と い う 意 味 で 極 め て 重 要 な 結 果 で あ る ．
第 6 章 に お い て 以 上 の 成 果 を ま と め ， 結 論 と 今 後 の 課 題 を 述 べ て い る ． 以 上 を 要 す る に ， 本 論 文 は 漸 近 正 規 性 を 用 い ， 可 変 長 無 歪 み 情 報 源 符 号 化 の い く つ か の 問 題 に 対 し て ， 従 来 得 ら れ て い な い 精 密 な 結 果 を 与 え た も の で あ る ． そ の 結 果 ， 符 号 の 精 密 な 評 価 が 可 能 に な り ， 実 用 化 へ の 大 き な 示 唆 を 与 え て い る ． よ っ て 本 論 文 は 博 士 （ 工 学 ） の 学 位 論 文 と し て 価 値 の あ る 論 文 と 認 め る ．
2 0 0 7 年 1 0 月
審 査 員 （ 主 査 ） 早 稲 田 大 学 教 授 博 士 （ 工 学 ） 早 稲 田 大 学 松 嶋 敏 泰 早 稲 田 大 学 教 授 工 学 博 士 （ 早 稲 田 大 学 ） 大 石 進 一 早 稲 田 大 学 教 授 工 学 博 士 （ 大 阪 大 学 ） 平 澤 茂 一
