情報量下界・query符号設計

概要

応答alphabetとquery回数から識別可能状態数の下界を出し、その下界に一致するcodeword割当と復号を構成する。

考え方

候補数M、一回の返答が最大r通りなら、区別には少なくともlog_r M回の情報が必要になる。この下界を目安に、返答の組が候補を一意に識別する符号としてqueryを設計する。

返答がr≥2通りでquery数を最悪qに抑えるなら、決定木の葉は高々r^q個なのでM候補の区別にはq≥ceil(log_r M)が必要。下界に一致する構成ができる模型として「queryで任意の部分集合を選び、隠れた候補が含まれるかを返す」を考える。M候補へ長さq=ceil(log₂M)の相異なる二進codewordを割り当て、bit jが1の候補集合をquery jにする。返答列がそのままcodewordとなり、整数IDへ復号できる。実際のquery制約が任意の部分集合を許さない場合は、この構成の各集合が合法であることを別に示す。

成立条件と計算量

下界だけでは構成の存在は示せない。返答同士の依存、誤り、同じqueryに許される制約を確認し、衝突しない符号かを検証する。適応的なqueryでは決定木の深さ、非適応的なら符号の長さを数える。

問題一覧

各問題の解説は問題ごとの本文として執筆します。各項目には主題・追加で学ぶ技能・既習技能の役割を示します。

前提・学習成果・出典

習得対象の目安: 水色(1200–1599)。応答で区別できる状態数を数え、bit符号化と復号を設計する。

対象色の読み方は本書の読み方を参照してください。

概念上の親: モデル変換とアルゴリズム設計。問題へ進む前に、下記の直接前提のうち未習得の単元を確認する。

Canonical taxonomy: FinalTaxonomyBuild final-taxonomy-build-initial digest f1ae39bc7201c3374c108e800284e1e0068ce6f7a57f15b2a9e5219616e3c4fe / LearningUnit unit-information-theoretic-query-design

情報量下界・query符号設計

習得する技能

  • 応答列の総数からquery数の下界を証明し、それに一致するcodeword割当と復号を構成できる。

前提と範囲

共通前提: prereq-abc-advanced-v1 (1.0.0)。

直接の前提単元: なし。

このUnitを直接前提とする単元: なし。

応答alphabetとquery回数から識別可能状態数の下界を出し、その下界に一致するcodeword割当と復号を構成する。その発動条件と正当化原理を比較可能な独立教材として学ぶ。

このUnitでは扱わないもの

  • 情報量下界・query符号設計の発動条件・不変量を使わず、実装部品だけを偶然共有する解法。

根拠