STEP 1736 — R(D~) v0.4 全 4,140 分割の Pareto + Blahut-Arimoto R(D) による反証テスト
2026-09-04 (JST) · rei-aios tab rei-aios-20 STEP 1736 land ·
Predecessor: STEP 1733 v0.3 ·
Sibling: STEP 1735 claim ledger ·
Spec: data/tabs/rei-aios-f9/quantum-frontier-spike/spec-v0.1.md
Land 内容:
v0.4 LAND
76/76 PASS
v0.3 1232/1232
v0.2 137/137
v0.1 63/63
FALSIFIABLE TEST PASS
Bell(8) = 4,140 分割を全列挙し、各点の (savings, E[d]) を計算。
加えて同じ情報源・同じ歪み行列で Blahut-Arimoto で R(D) を数値計算し、
全 4,140 の達成可能点が R(D) 曲線の上に乗ることを検証した。
v0.3 の「上界である」は disclaimer から 測定されたギャップ に昇格した。
1. Motivation — 「Pareto: yes」を 4 点相対から 4,140 点相対へ
v0.3 は 4 registered partition について「4 点集合内では 4/4 とも Pareto」と報告していた。
この「Pareto」は登録 4 点だけを見た局所判定であり、D-FUMT₈ の全 Bell(8) = 4,140 通り
の分割の中で真に非劣位かは分からなかった。
さらに v0.3 の outOfScope には
「達成可能点 = R(D~) の上界であって R(D~) ではない」 が disclaimer として書かれていた。
v0.4 は Blahut-Arimoto を数値実装して R(D) 曲線を引き、
全 4,140 点が曲線の上に乗ることを検証する。乗らなければ、
実装のどこか(RGS 列挙・optimal decoder・BA 反復)が間違っている
─ 反証可能なテストになる。
2. 追加した API
| API | 役割 |
|---|
allRestrictedGrowthStrings(n) | Bell(n) 個の分割を canonical RGS 形で列挙 (Bell(8)=4,140、Bell(6)=203 で確認済) |
allDFumt8Partitions() | D-FUMT₈ の 4,140 分割を配列で返す |
partitionRatePoint(partition, counts, distortion) | 単一分割について (savings, E[d]) を計算 (v0.3 の optimalDecoder 再利用) |
allPartitionRatePoints(counts, distortion) | 4,140 点全部を計算 (~30ms) |
paretoFrontier(points) | (E[d], R) 平面での Pareto 非劣位判定 (dominated iff 別点が両方向で ≤ かつ片方が strict) |
locateRegisteredPartitions(counts, distortion) | 4 registered partition の 4,140 中の rank + Pareto 位置 |
blahutArimotoAt(counts, distortion, s) | slope s での BA 1 point 解 (Cover-Thomas §10.8 Algorithm 10.4) |
blahutArimotoRDCurve(counts, distortion) | slope sweep で R(D) 曲線全体、endpoint 込み、pointwise lower envelope 保証 |
interpolateRateAt(curve, D) | 任意 D での R の線形補間 (凸曲線上の upper bound = 反証テスト strict 化) |
verifyPartitionsAboveRDCurve(counts, distortion) | 反証テスト本体: 全 4,140 点が R(D) の上にあるか + gap 統計 (min/median/max) |
3. 反証テスト — 全 4,140 点が R(D) の上に乗ることの実測
test §6 結果:
skewed [50,30,10,10,5,5,3,1] · 4,140 points · 0 violations · min gap = 0.000e+0 · median gap = 0.4839 bits · max gap = 1.0407 bits
uniform [1,1,1,1,1,1,1,1] · 4,140 points · 0 violations · min gap = 0.000e+0 · median gap = 1.2090 bits · max gap = 1.4036 bits
「gap」 = R_partition − R(E[d]_partition) = 決定的写像 code が真の R(D) より
どれだけ余計に rate を使っているか。
訂正 (2026-09-04, chat-Claude review 反映) — 「gap ≥ 0 を実測」は発見ではない。
R(D) の定義 =「全条件付き分布 p(x̂|x) にわたる min I(X;X̂)」で、決定的写像 + decoder は
そのうち一員なので、gap ≥ 0 は理論から要請される不等式。破れれば実装バグ。
つまり本テストは 「反証可能な実装正当性テスト」 であり、それが 4,140 全点で通ったこと
─ とりわけ 両端が厳密に 0 で刺さったこと (identity 分割 rate = H(X) = R(0)、trivial 分割
rate = 0 = R(D_max)) ─ が BA + RGS enumerator + optimal decoder の 4 独立実装が
互いに矛盾しない証拠。情報を持つのは gap の 大きさ (median 0.48 bits) と両端一致。
反証テストが失敗する条件 (仮定法) — もし 1 点でも gap < 0 (許容 1e-4 bits) なら:
(a) RGS 列挙が duplicate や missing を生む・(b) optimal decoder が最適でない・(c) BA が発散/収束バグ・(d) 数値誤差の集中 — のいずれか。
現在の実装は全 4,140 で 0 violations。
chat-Claude 独立再現 (2026-09-04) — Python 別実装 (TypeScript とは無関係) で
4,140 分割列挙 + Blahut-Arimoto を書き直し、全数字一致確認済。特に identity 分割 (8 singleton) は
rate = H(X) = 2.2380 = R(0) で gap = 0.000000、trivial 分割 (1 class) は rate = 0 = R(D_max)
で gap = 0.000000 ─ 両端刺さりで BA 実装の正当性が独立に verify された。
4. 4 registered partition の 4,140 中の位置
spec §5.6 が v0.3 で報告した「4 partition 内では 4/4 Pareto」に対する v0.4 の答え:
4,140 中では 4/4 とも Pareto ではない。
| partition |
classes |
R = H(X/~) |
E[d] |
Pareto (4,140) |
D rank |
R rank |
slack vs R(D) |
| v01_polar |
4 |
1.2766 |
0.4035 |
no |
3787 / 4140 |
1033 / 4140 |
1.0348 bits |
| conservative |
4 |
1.8404 |
0.1667 |
no |
1893 / 4140 |
3553 / 4140 |
0.7101 bits |
| bivalent_only |
6 |
1.6113 |
0.1754 |
no |
1895 / 4140 |
2480 / 4140 |
0.5242 bits |
| self_fixed |
5 |
0.7596 |
0.4386 |
no |
3968 / 4140 |
136 / 4140 |
0.5964 bits |
Distribution: [50, 30, 10, 10, 5, 5, 3, 1], distortion: 0-1 Hamming.
Rank 0 = smallest.
4.1 何が言えて、何が言えないか
言えること
- 4 partition はいずれも 意味論的 commitment (spec §4 の polarityGloss) を明示する分割であり、Pareto 最適性を主張するものではなかった。v0.4 でその期待が数値化された。
- self_fixed の R rank 136/4140 は「情報捨てに関しては 4,140 中トップ 3.3%」だが、E[d] rank は 3968/4140 (下から 4.1%) = 情報消去代償が対応する。
- conservative は R rank 3553/4140 (上から 14%) で「情報を残す」寄り、対応して E[d] rank 1893/4140 (中央付近) = 忠実度上位群。
- 全 4 とも slack > 0.5 bits = 決定的写像は情報論的最適から少なくとも 0.5 bit 離れている。
言えないこと
- Pareto でないから 「悪い分割」ではない。dominance は情報論的な rate/distortion 座標のみで判定しており、
polarityGloss (意味論的 commitment) は含まれない。「意味を保つ」ことに payoff がある用途では、
Pareto 上の分割が意味的に不適切ということが十分にあり得る。
- Pareto 上の 4,140 中の分割は 意味論的に無名のものが大半 — v01_polar のような polar-role の対応や、
bivalent_only のような分類軸を持たない。partition による意味論的解釈 = registered 4 の目的、
Pareto 最適性 = R(D) の目的、この 2 つは別の目的関数。
- slack > 0 は 決定的写像の限界であり、確率的 code (stochastic reconstruction) を許すと gap は縮小し得る。
Blahut-Arimoto はまさに確率的 code を扱う。
5. Blahut-Arimoto の実装詳細
Cover & Thomas Elements of Information Theory 2nd ed. §10.8 Algorithm 10.4 (Blahut 1972 / Arimoto 1972) をそのまま。
各 Lagrange slope s ≤ 0 で:
iterate:
w(y|x) ∝ q(y) · exp(s · d(x, y)) [normalize over y for each x]
q(y) = Σ_x p(x) · w(y|x)
until |I(X;Y)| converges (tolerance 1e-9 bits)
then:
D(s) = Σ_{x,y} p(x) w(y|x) d(x, y)
R(s) = Σ_{x,y} p(x) w(y|x) log₂(w(y|x) / q(y))
Endpoints は解析値を追加:
- (D_min = 0, R = H(X)) — lossless (identity mapping)
- (D_max = min_y Σ_x p(x) d(x, y), R = 0) — best constant reproduction
Slope sweep = 400 point の quadratic ramp (s = 0 で密、s → -50 で粗)。
数値誤差から生じる 微小な単調性違反は pointwise lower envelope
(running-min from the left, sorted by D asc) で厳密に修正。
これは R(D) の 下からの近似を保つので、
「partition R ≥ interpolated R(D)」 テストは strict な必要条件のまま。
5.1 数値検証
s = 0: R ≈ 0 (0-based 収束、Δ < 1e-6) ✓s = -30: R → H(X), D → 0 (両方 5% 以内) ✓D = 0 補間: R = H(X) ✓D = D_max 補間: R = 0 ✓- 単調性 (D asc で R non-increasing): pointwise lower envelope で保証 ✓
6. 反証性を強化する「injected wrong point」テスト
§7 では、実 partition の一つを取り、その rate を人為的に 0.5 bits 下げた
「架空の code」を作って反証テストに掛ける。すると:
fake point has gap −0.5000 < 0 (correctly under the curve) ✓
= もし本当に間違った実装があったら、テストは検出することの実演。
真の 4,140 点が全て gap ≥ 0 なのは、実装が正しいからと言える (test §6)。
7. Anti-hill-climb discipline (spec §7 Pattern L 遵守)
v0.4 での Pattern L (savings 単独報告への回帰) 予防
- 本 site page は table の全行で R (=quotient bits)、E[d]、Pareto、rank、slack vs R(D) の 5 columns を並記。savings 単独 column は敢えて置いていない。
MODULE_V04_INFO.name = 'r-d-tilde-exhaustive-frontier' は "R(D~)" を title に含まない — spec §7 Pattern L の「§5.3 の 4 項目が入るまで」を、v0.4 でも保守的に維持 (v0.3 で 4 項目は入ったが、"exhaustive-frontier" は「R(D~) の全計算をした」 とは主張しない)。- test §9 で
MODULE_V04_INFO.name に best / optimal_partition / the_right が含まれないことを assert。
MODULE_V04_INFO.outOfScope に「stochastic reconstruction codes」「the true infimum R(D~)」「SEED_KERNEL exhaustive」「Blau-Michaeli R(D,P)」「operational codec」の 5 項目を明示。falsifiabilityNote: 「BA-vs-partitions テストは 失敗し得る — 実装が間違っていれば」を module metadata に固定。
8. Honest scope
- これは R(D~) の全計算ではない — v0.4 は「R(D) 曲線 + 全達成可能 deterministic 点」を計算しただけ。R(D~) は partition ~ を固定した後の商空間 上の rate-distortion function であり、~ を変えるごとに別の R(D~) が定義される。「4,140 点全てが R(D) の上」 = 一つの source 上の全 deterministic code が R(D) の上、という当然の結果。
- SEED_KERNEL は exhaustive にできない — Bell(299) は astronomical。SEED_KERNEL に対しては v0.3 の hammingRatePoint / seedKernelRatePoint で per-cluster 点は測れるが、全分割 sweep は不可能。
- 確率的 code (stochastic reconstruction) は含まれない — R(D) は infimum over ALL codes (deterministic + stochastic)。BA が到達するのは stochastic 一般解。決定的写像が Pareto から外れていることは stochastic code が strict に良いことの帰結。
- Blau-Michaeli R(D, P) の perception 軸は未実装 — v0.5+ backlog。
- Optimal decoder は per-class argmin — class 独立なので局所解 = 全体解、これは 0-1 でも polarity でも成立。異なる structure (e.g. Bregman divergence) を入れると local ≠ global になる。
- 反証テストは PASS したが、これは「実装が正しい」の必要条件であって十分条件ではない — 全ての実装バグが gap < 0 で発現するわけではない。gap > 0 でも実装が subtle に間違っている可能性は残る。
9. Cross-references
10. External references
- Blahut, R. E., Computation of channel capacity and rate-distortion functions, IEEE Trans. IT (1972)
- Arimoto, S., An algorithm for computing the capacity of arbitrary discrete memoryless channels, IEEE Trans. IT (1972)
- Cover, T. M. & Thomas, J. A., Elements of Information Theory, 2nd ed., §10.8 Algorithm 10.4
- Berger, T., Rate Distortion Theory (1971) — quotient RD framework
Test: test/step1736-r-d-tilde-v04-exhaustive-frontier-test.ts · 76/76 PASS ·
Regression: v0.3 1232/1232, v0.2 137/137, v0.1 63/63 all clean.