次世代 AI アクセラレータに向けた誤り訂正復号法

次世代 AI アクセラレータに向けた誤り訂正復号法 名古屋工業大学 和田山 正 本研究は科研費基盤 (A)JP22H00514 「深層展開に基づく信号処理アルゴリズム構築論の深化と展開」 によりサポートされています． 1 / 59

自己紹介 和田山 正 (わだやま ただし) 名古屋工業大学大学院工学研究科 教授 (情報工学科） 専門分野: 符号理論，機械学習と信号処理, 無線通信工学 研究上の興味: LDPC 符号，圧縮センシング，深層学習 著書: 「モデルベース深層学習と深層展開」(2023)，誤り訂正技術の基礎 (2010) 「低密度パリティ検査符号とその復号法」 (2002)，その他 2 / 59

“Coding is dead”？ “Coding is dead” と昔から 10 年ごとぐらいに言われてきた．いまの状況は？ 符号理論 (誤り訂正符号) のひとつの大目標は，現実的な計算量で通信路容量を達成する こと．言い換えると「計算量の保証がついた通信路符号化定理」を見出すこと 1 ． 2010 年以降，ポーラー符号，空間結合 LDPC 符号などの符号系において，シャノン限界 の達成が証明されてきている． その意味では，符号理論の「大目標は成就されてしまった」→ 時代の節目 1 ただし「数学としての符号理論」， 「計算機科学的観点からの符号理論」の方向性は異なる． 3 / 59

今度こそ “Coding is dead”? → いえいえ，Coding is still alive! 誤り訂正符号への現実世界からの強い期待 新世代無線通信システム (6G) ▶ ▶ 多様な要求条件 (極小遅延，AI との親和性の高いシステム) 基地局における信号処理の省電力化・高スループット化 ストレージシステム ▶ ▶ 積層フラッシュメモリの台頭 高密度化による記録品質劣化への対応 量子誤り訂正符号 ▶ ▶ 表面符号から量子 LDPC 符号への流れ US の符号理論業界では復号アルゴリズムの開発が注目されている 社会からの強いニーズ → 各研究者が各自の「大目標」を掲げ，進む時代に 4 / 59

本講演の目標 1 符号理論研究者として講演者の現状の「大目標」をご紹介する． 2 その目標に向かって過去３年，どのような方向性で研究を進めててきたのかご紹介する 3 今後の研究の展開方向についてもお話をさせていただく． 本ワークショップ全体の趣旨にあっているか若干の不安もありますが，符号理論研究の動向 も含めて，広い分野の方に楽しんでいただけるように準備してまいりましたのでよろしくお 願いします！ 5 / 59

私自身の「符号理論研究上の大目標」 1. 進化する AI ハードウェアに適合する復号法 AI アクセラレータ等のプログラマブル高速計算デバイスの発展が見込まれる． そのようなハードウェアに適した復号アルゴリズムの開発の重要性が高まる． 2. 通信路モデルのない世界へ 通信システムへの AI コンポーネント組み込みは不可避． 通信路モデルがない通信路に対して，学習に基づく符号化システムを構成 3. NP 困難問題への挑戦 一般の線形符号の最大事後確率復号問題は NP 困難 多項式時間の厳密アルゴリズムの構成は不可能 近似アルゴリズムの可能性の追求は終わっていない 6 / 59

本日の講演の流れ 1. 進化する AI ハードウェアに適合する復号法 Gradient Flow (GF) 復号法 2. 通信路モデルのない世界へ スコアベース生成モデルに基づく通信路学習 3. NP 困難問題への挑戦 勾配ベースマルコフ連鎖モンテカルロ法の復号問題への応用 7 / 59

本日の講演の流れ 1. 進化する AI ハードウェアに適合する復号法 Gradient Flow (GF) 復号法 8 / 59

次世代の復号アルゴリズムに求められもの テンソル計算フレンドリ 行列・ベクトル積演算 (より一般にはテンソル積計算) がメイン 要素ごとの非線形演算を含む 多様なテンソル計算デバイスへの対応 GPGPU/AI アクセラレータ プログラマブル光計算回路 ▶ RRAM(resistive random-access memory) に基づく行列ベクトル積回路 ▶ ▶ AI フレンドリ 機械学習との親和性が高い 学習可能コンポーネントを導入可能 すべてのサブブロックが微分可能 (微分可能プログラミング) 9 / 59

テンソル計算可能なアルゴリズム IEEE ISIT 2024, W and Wei: 「テンソル計算可能性」の概念の提唱 テンソル計算可能性 (1)テンソル積計算(行列ベクトル積など） (2)テンソル和計算(ベクトル和, 行列和など） (3)スカラ関数適用 GPGPU 光計算回路 RRAM回路 により表現されるアルゴリズム テンソル 計算 テンソル 計算 テンソル 計算 スカラー関数適用 入力 テンソル テンソル計算ブロックにあらわれるテンソルサイズが小さいほど実装面で有利 10 / 59

用語の定義: LDPC 符号 LDPC 符号 2 元疎検査行列 H ∈ Fm×n で定義される LDPC 符号は 2 C̃ (H) ≡ {x ∈ Fn2 | Hx = 0} と定義される． n: 符号長 m: パリティシンボル数 H = {Hij } ∈ Fm×n : 検査行列 (スパース 2 元行列) 2 パリティ検査条件 (バイナリ版): Hx = 0 A(i) ≡ {j | j ∈ [n], Hij = 1}(i ∈ [m]): 非ゼロ列インデックス B(j) ≡ {i | i ∈ [m], Hij = 1}(j ∈ [n]): 非ゼロ行インデックス 11 / 59

用語の定義: バイポーラ LDPC 符号 バイポーラ LDPC 符号 バイポーラ LDPC 符号を C (H) ≡ {β(x) | x ∈ C̃ (H)} と定義する．ここでバイナリーバイポーラ変換は β(0) = 1, β(1) = −1 と定義される． パリティ検査条件 (バイポーラ版) 任意の x ∈ C (H) と任意の i について Y xj = 1 (1) j∈A(i) が成立． 12 / 59

MAP 復号による LDPC 符号の復号 p(y |x): 通信路に対応する条件付き確率密度関数 MAP 復号則 最大事後確率復号則 (MAP 復号則) は x^ ≡ argmaxx∈Rn p(y |x)p(x) (2) となる．ここで p(x) は符号 C (H) により定まる事前確率密度関数: p(x) ≡ X 1 δ(x − c). |C (H)| (3) c∈C (H) δ はディラックのデルタ関数. 一種の組合せ最適化問題 → 符号長 n について多項式時間での正確な計算は絶望的． 13 / 59

LDPC 符号の復号問題 LDPC 復号問題は，一種の組合せ最適化問題 単位時間当たり最も大量に解かれている組合せ最適化問題 (例えば日米間のネットトラ フィックをほぼ収容している海底光ファイバ通信は LDPC 符号化を利用している) MAP 復号は計算量的に実現不可能 → ビリーフプロパゲーション法 (BP 法) が実用的に よく利用されている BP 法はメッセージパッシングに基づくビット単位事後確率の近似アルゴリズム ベイズ推論的考え方 14 / 59

LDPC 符号の復号法の系譜 ビットフリップ型アルゴリズム （局所探索）．．．回路が小さくて済む Gallager-A, Gallager-B Bit-flipping algorithm Gallager (1963) Feldman LP decoding (2003) BP decoding GDBF WBF algorithm algorithm Noisy GDBF (2010) ADMM decoding 最適化ベース (2013) アルゴリズム MacKay によるBP再定式化(2000) (2014) 強い関連性 提案法は ここ！ min-sum algorithm ベイズ推論的アルゴリズム 現代のデファクトスタンダード 15 / 59

緩和復号問題を考える: ギブス型事前分布の導入 (W & Takabe, 2021) 負対数尤度関数: L(x; y ) ≡ − ln p(y |x) ギブス型事前分布: p̃(x) ≡ 1 exp (−γh(x)) Z ここで，ポテンシャルエネルギー関数 h(x) として h(x) = 0, x ∈ C (H) > 0, otherwise となる関数を取ると γ → ∞ のとき X 1 1 p̃(x) = exp (−γh(x)) → δ(x − c). Z |C (H)| (4) (5) c∈C (H) 実際には，有限の γ を利用して近似: p(x|y ) ∝ p(y |x)p(x) ≃ p(y |x)p̃(x) = exp (−L(x; y ) − γh(x)). 16 / 59

近似 MAP 復号法 近似 MAP 復号則 (W & Takabe, 2021) x^ ≡ argminx∈Rn [L(x; y ) + γh(x)] (6) 復号問題の連続最適化問題への帰着の一種 Feldman らの帰着 (2010) では線形計画問題 (凸計画問題) に帰着させているが，この帰 着では非凸問題に帰着 負対数尤度関数 L(x; y ) の部分を取り替えることでさまざまな通信路に適用可能 利用する最小化技法には選択の自由度がある ▶ ▶ 近接勾配法 (proximal decoding, W & Takabe, 2021) 勾配降下法 (gradient flow decoding, W & Wei, 2022, 2023) 17 / 59

ポテンシャルエネルギー関数 ポテンシャルエネルギー関数の選択には任意性があるが，本研究では以下の関数に着目: 符号ポテンシャルエネルギー関数 (ISIT, W & Takabe, 2021) hα,β (x) ≡ α n X (xj2 − 1)2 + β j=1 | {z } bipolar constraint | m X i=1   Y  2 x j  − 1 j∈A(i) {z parity constraint (7) } 第一項はバイポーラ制約に対応 第二項はパリティ制約に対応 符号語で値 0 を与えるペナルティ関数と見ることができる． GDBF 復号法 (Wadayama et al., 2010) の目的関数から発想を得ている． ∀x ∈ Rn , h(x) ≥ 0. 等号成立条件は x ∈ C (H). 18 / 59

勾配流復号法 (Gradient Flow Decoding) GF 復号法は次の微分方程式で定義される: GF 復号法 (ISTC2023, ISIT2024) dx = −(∇L(x; y ) + γ∇hα,β (x)) dt (8) minx∈Rn L(x; y ) + γhα,β (x) (9) 最小化問題 に対して，勾配流力学系 (Gradient flow dynamics) を適用 離散時間系における勾配降下ダイナミクスに相当 連続時間ダイナミクスとして「復号アルゴリズム」を定式化 19 / 59

勾配流力学系 (Gradient flow dynamics) 勾配流力学系 AA decoding problem is formulated a minimization problem of decoding problem is formulated a minimization problem of a apotential function potential function dx(t) of gradient flow dynamics minimizing the introduction = of −∇f (x(t)),flow dynamics minimizing the introduction gradient potentialdtfunction (10) potential function Potential energy (objective function) に基づく凸関数 f (x) の最小化過程． x(t) function は勾配流力学系の解 (状態点の軌跡) であり，f の Potential energy function (objective function) 最小点の探索過程にもなっている．凸関数の場合，最小点が平衡点となる． f (x) ≡ "y −x"2 +α n ! j=1 f (x) ≡ "y −x"2 +α 2 2 m !   2 "      − 1 (1) 2 x" m j ! (xnj −1) +β ! (xj2 −1)2 i=1 +β Gradient flow dynamics j=1 Gradient flow dynamics dx(t) dt  j∈A(i) i=1 j∈A(i) = −∇f (x(t)) dx(t) dt x = −∇f (x(t)) i.e., gradient descent method in continuous-time. xj  − 1 (1) (2) (2) 2 x1 i.e., gradient descent method in continuous-time. 20 / 59

なぜ微分方程式に基づく定義となっているのか 実装面の柔軟性: アナログ回路実装，デジタル回路実装，プログラム実装のいずれにも 対応できる ▶ アナログ実装: 微分方程式に対応するアナログ回路を組めばよい．積分器と行列ベクトル乗 算器，加算減算器，非線形素子 (指数関数，対数関数など) を基礎ブロックとする． ▶ デジタル実装・プログラム実装: 微分方程式を離散時間化して得られる離散反復式を実装． 理論解析における柔軟性: ランジュバン方程式 (確率微分方程式) の線形近似に基づく理 論解析 (ISIT2022, W)，フォッカー・プランク方程式に基づく解析 (with 三村先生) 21 / 59

アナログ回路による実装 JOURNAL OF LATEX CLASS FILES, VOL. 18, NO. 9, SEPTEMBER 2020 AWGN 通信路の場合， ∇L(x; y) = x −theyapproximate となる．復号微分方程式は : by ne the gradient flow, we need an appropriate potential Hence, MAP rule considered here is given nction. The code potential energy function for C(H) left box represents an analog circuit evaluating the value variate polynomial defined as x̂ ⌘ argmin (15) of dx x2Rn L(x; y) + h↵, (x). (x = y+ rh↵, (x)). A similar optical circuit implementing 00 1 12 −(x − y + γ∇h (x)) α,β n m X X Y an machine with feedback loop was reported in [9]. dtIsing Generalized GF decoding @@ ⌘↵ (x2j 1)2 + xj A 1A , InB.principle, an optical implementation of the analog circuit (11) JOURNAL OF LTEX CLASS FILES, VOL. if NO. 9,gradient SEPTEMBERpart 2020 depicted Fig.2subsection, would bethepossible the In the in previous concept of18,an approximate (8) (x rule y +wasrh implemented optical MAP introduced. The be objective function with to be an miniIntegrator ↵, (x)) can = (x1 , . . . , xn ) 2 R . The parameters ↵ 2 R+ and mized is circuit. ontrol the strength of the constraints. left box represents an analog circuit evaluating the value of A tensor-friendly of the optical circuitcircuit evaluating de potential energy h↵, (x) is inspired by the non(x y+implementation rh↵, (x)). A similar implementing Fbe(x) ⌘ L(x; y) hfeedback discussed in+Subsection ↵, (x). IV-B. arity constraint function used in the GDBF objec- rh↵, (x) is antoIsing machine with loop was(16) reported in [9]. ion [?]. The sum-of-squares form directly implies In principle, an optical implementation of the analog circuit many possibilities optimization methods. For gradient part important property of h↵, (x), i.e., the inequality There are depicted in Fig.2 of would be possible if the proximal is to solve this continuous 例えば，フィードバックのある光回路として (原理的に ) 実装可能 0 holds for any x 2 Rn . The equality holds if and example, the(x y + decoding rh implemented with an optical Integrator ↵, (x)) can be minimization problem by using a proximal gradient descent 2 C(H). circuit. method [][]. In following, weimplementation will solve this minimization Fig. 3. Heat map of hrep (x) A the tensor-friendly of the circuit evaluating G RADIENTポテンシャル勾配の計算部分の主要計算は，行列ベクトル積となる．その部分は光ス FLOW DECODING FOR GENERAL problem byrh using (x) the gradient flow. is to be discussed in Subsection IV-B. ↵, MEMORYLESS CHANNELS The ODE for the generalized(GF decoding is) given by イッチや MZI ベース行列・ベクトル積回路にて 原理的に 実装可能． ximate maximum a posteriori (MAP) decoding The heatmap represen Fig. 2. Analog circuit for generalized GF decoding corresponding to the re briefly discuss the approximate MAP decoding GF-ODE (15). dx = (rL(x; y) + rh (x)) (17) 超高速計算，超低消費電力性が期待される． Integrator hrep (x) is shown in F ↵, dt d in the paper of proximal decoding []. Assume that seen that the function x(0) = x0 . (18) transmits a codeword of C(H) to a given channel. locationsFig.of3. the Heatcodewo map of nel is defined by a probability density function (PDF), / 59 of the function 22 hrep (x) j=1 i=1 T n j2A(i) A

補足情報: アナログ回路に基づく信号処理 微分方程式により定義される連続時間「信号処理アルゴリズム」 MIMO 信号検出: A. Nakai-Kasai and T. Wadayama, “Ordinary Differential Equation-based MIMO Signal Detection,” IEEE Transactions on Signal Processing, to appear, 2024. スパース信号再現: T. Wadayama and A. Nakai-Kasai, “Continuous-Time Sparse Signal Recovery,” IEEE Access, Vol.12, pp. 118141-118153, 2024. 意外と連続系のほうが解析がしやすいというメリットもある． 23 / 59

復号微分方程式の離散時間化 微分方程式の数値的解法であるオイラー法の考え方を適用して離散時間化→ (離散時間)GF 復号法の復号反復式 s (k+1) = s (k) − η(∇L(s (k) ; y ) + γ∇hα,β (s (k) )), k = 0, 1, . . . , (12) 勾配降下型アルゴリズム (gradient descent) GPGPU や CPU による実行に向いている サブブロックすべてが微分可能であり， 「微分が通る」→ 学習パラメータや学習可能コン ポーネントの埋め込みに適した AI フレンドリなアルゴリズム 24 / 59

小さい例を観察する (1) 符号長 2 の繰り返し符号 Crep を例に取る． Crep ≡ {(1, 1), (−1, −1)}. (13) hrep (x) = (x12 − 1)2 + (x22 − 1)2 + (x1 x2 − 1)2 , (14) このとき，ポテンシャル関数は となる (α = β = 1 と置いた)． hrep (x) は符号語において値 0 を取り，その他で非負の値を与えるペナルティ関数 ただし，符号語以外にも停留点 (勾配がゼロとなる点) がある 25 / 59

小さい例を観察する (2) Crep ≡ {(1, 1), (−1, −1)}. (15) ポテンシャル関数 hrep (x) のヒートマップ表示 左下角と右上角が符号語に対応 26 / 59

小さい例を観察する (3) AWGN 通信路を仮定する (∇L(x; y ) = x − y ) 送信語 x = (1, 1) 受信語 y = (0.6027, 0.8244)  dx1    x1 − 0.6027 + 4x1 (x12 − 1) + 2(x1 x2 − 1)x2 dt =− . dx2 x2 − 0.8244 + 4x2 (x22 − 1) + 2(x1 x2 − 1)x1 dt 1 0 1 1 0 1 中心の白丸が初期値，赤線が解，黒丸が平衡点． 27 / 59

解の軌跡 (符号長 204) 符号長 204, パリティシンボル数 102 の (3, 6) 正則 LDPC 符号における解曲線 (オイラー法による数値計算による) 28 / 59

ビット誤り率の比較 (AWGN 通信路) 100 GF (n = 96) GF (n = 204) GF (n = 504) GF (n = 1008) BP (n = 96) BP (n = 204) BP (n = 504) BP (n = 1008) Bit Error Rate 10 1 10 2 ' $ Presented at ISTC 2023 n = 204, m = 102, BPSK BP には少し負ける 10 3 ビットフリップ復号法と似た 性能 10 4 AWGN 性能は伸びしろが残る 10 5 & 0 1 2 3 Eb/N0 (dB) 4 5 6 29 / 59 %

符号ポテンシャル勾配のテンソル計算可能性 (1) 符号ポテンシャル関数 hα,β (x) ≡ α n X (xj2 − 1)2 + β j=1 m X   i=1  Y 2 xj  − 1 (16) j∈A(i) 符号ポテンシャルの一次導関数 ∂ hα,β (x) = 4α(xk − 1)(xk + 1)xk + 2β ∂xk 勾配 ∇hα,β (x)  ∇hα,β (x) ≡ X i∈B(k)   Y   x j  − 1  j∈A(i) T ∂ ∂ hα,β (x), . . . , hα,β (x) . ∂x1 ∂xn Y  xj  . j∈A(i)\{k} (17) → テンソル計算可能か？ 30 / 59

符号ポテンシャル勾配のテンソル計算可能性 (2) テンソル計算可能か？ → 可能である テンソル計算可能性 (ISIT2024, W & Wei) 勾配 ∇hα,β (x) は ∇hα,β (x) = 4α exp (z−1 + z + z+1 ) + 2β exp (w − z) (18) と評価できる．ここで中間変数 z, z−1 , z+1 , w は下記の通り定義される: z ≡ ln(x), (19) z−1 ≡ ln(x − 1), (20) z+1 ≡ ln(x + 1), (21) w ≡ ln(H (exp(2Hz) − exp(Hz))) (22) T ただし，x ̸= 0 である． 31 / 59

GF 復号の実装例 JOURNAL OF LATEX CLASS FILES, VOL. 18, NO. 9, SEPTEMBER 2020 9 Algorithm 1 GF decoding with trainable parameters problem for future wireless systems such as beyond-5G/6G systems. ' $ Let A 2 RN ⇥n be a channel matrix. Suppose that a received TensorFlow などを word y 2 RN is PyTorch, given by 1: s(0) := x0 2: for k := 0 to U 1 do 3: Set the following variables: 利用して GPGPU 計算が容 (53) y = Ax + w, z := ln(s(k) ), z 1 := ln(s(k) 1), z+1 := ln(s(k) + 1), w := ln(H T (exp(2Hz) g := rL(s (k) exp(Hz))), ; y) 4: h := 4↵(k) exp (z 1 + z + z+1 ) + 2 (k) exp (w 5: s(k+1) := s(k) ⌘ (k) (g + (k) h) 6: end for 7: x̂ := sign(s(U ) ) 8: Output x̂ z) F. Multi-stage decoding To enhance the throughput of the GF decoding process, where w 2 RN 易に実行できる is a Gaussian noise vector, the components of which follow an i.i.d. Gaussian distribution. The channel input vector x isミニバッチ計算が可能 assumed to be a codeword of C(H), which implies that we assume BPSK modulation. In this problem setting, the PDF representing the channel is 学習可能パラメータを容易 given by に組み込める (深層展開 ) 2 p(y|x) ⌘ a exp & bky Axk , (54) % where a and b are real constants. Our objective function for the approximate MAP rule can be expressed as 1 (55) FMIMO (x) ⌘ ky Axk2 + h↵, (x). 2 Corollary 1: rFMIMO (x) is tensor-computable. (Proof) The gradient of the first term of FMIMO : 32 / 59

深層展開の考え方 (Gregory & LeCun, 2010) 深層展開は、反復アルゴリズムの内部構造に学習可能なパラメータを埋め込むことで、 柔軟で学習可能なアルゴリズムを作成することを目的としている．多くの事例で，収束 基盤となる技術：深層展開 (DU, Deep Unfolding) 加速が観測されている． 入力 y ラベル x <latexit sha1_base64="0GqaQ/oynV6W7A7yIesrqqNX60U=">AAACcHichVG7SgNBFD1ZXzG+ojaChdGgiEWYiC+sgjaWmhgNxCC7m4kOmX24uwnE4A/4AxY2KoiIn2HjD1j4CWJnBBsLbzYLokG9y849c+aeO2dmNFsK12PsKaR0dHZ194R7I339A4ND0eGRHdeqODrP6pa0nJymulwKk2c94Umesx2uGprku1p5vbm+W+WOKyxz26vZvGCoB6YoCV31iCrsaZYsujWDUqy2H42zBPMj1g6SAYgjiE0reoM9FGFBRwUGOEx4hCVUuPTlkQSDTVwBdeIcQsJf5zhBhLQVquJUoRJbpvGAZvmANWne7On6ap12kfQ7pIxhmj2yW9ZgD+yOPbOPX3vV/R5NLzXKWkvL7f2h07HM+78qg7KHwy/Vn549lLDiexXk3faZ5in0lr56fNbIrKan6zPsir2Q/0v2xO7pBGb1Tb/e4ulzROgBkj+vux3szCeSS4nFrYV4ai14ijDGMYVZuu9lpLCBTWRp3yOc4QKXoVdlTJlQJlulSijQjOJbKHOfQvWPLg==</latexit> 入力 y <latexit sha1_base64="0GqaQ/oynV6W7A7yIesrqqNX60U=">AAACcHichVG7SgNBFD1ZXzG+ojaChdGgiEWYiC+sgjaWmhgNxCC7m4kOmX24uwnE4A/4AxY2KoiIn2HjD1j4CWJnBBsLbzYLokG9y849c+aeO2dmNFsK12PsKaR0dHZ194R7I339A4ND0eGRHdeqODrP6pa0nJymulwKk2c94Umesx2uGprku1p5vbm+W+WOKyxz26vZvGCoB6YoCV31iCrsaZYsujWDUqy2H42zBPMj1g6SAYgjiE0reoM9FGFBRwUGOEx4hCVUuPTlkQSDTVwBdeIcQsJf5zhBhLQVquJUoRJbpvGAZvmANWne7On6ap12kfQ7pIxhmj2yW9ZgD+yOPbOPX3vV/R5NLzXKWkvL7f2h07HM+78qg7KHwy/Vn549lLDiexXk3faZ5in0lr56fNbIrKan6zPsir2Q/0v2xO7pBGb1Tb/e4ulzROgBkj+vux3szCeSS4nFrYV4ai14ijDGMYVZuu9lpLCBTWRp3yOc4QKXoVdlTJlQJlulSijQjOJbKHOfQvWPLg==</latexit> Process A <latexit sha1_base64="vTluDkO8bc8Fzi3+w3Nks63Dawo=">AAACoXichVFNSxtRFD2O1aZpq2ndFNwEg8VFCXdEbJEuQrvRXRIbFRIJM5OX+PDNB/MRjEP+QP+Ai64MlCL+jG7ctuDCnyBdKnTTRe9MBkoV9Q7z7n3n3XPeee+ZnpJBSHQxoU0+mpp+nHuSf/rs+cxs4cXLrcCNfEs0LFe5/o5pBEJJRzRCGSqx4/nCsE0lts39j8n6dl/4gXSdT+HAE7u20XNkV1pGyFC78L7VEV3mpkqxIf2uy8KmisQw9nvmMNbfFKm8vDIeh/mW6apOMLA5FQ/ahRKVKY3i7ULPihKyqLqFb2ihAxcWItgQcBByrWAg4K8JHQSPsV3EjPlcyXRdYIg8cyPuEtxhMLrPY49nzQx1eJ5oBinb4l0U/z4zi1ikczqhKzqjU7qkP3dqxalG4mXA2Rxzhdee/fxq8/eDLJtziL1/rHs9h+jiXepVsncvRZJTWGN+//DoanOtvhi/phH9Yv/HdEHf+QRO/9r6WhP1L8jzA+g3r/t2sbVc1lfLq7WVUuVD9hQ5zGMBS3zfb1HBOqpo8L4jnOEHfmolbUOravVxqzaRcebwX2jNv76+oI0=</latexit> Mini batches ↵ x̂ <latexit sha1_base64="CxhCYEXas1BmijUkc6sYpkr8MIo=">AAACeHichVG7SgNBFD1ZXzE+Ek0j2ASDryZMgi+sgjaWiRoVkhB21zFZsi92J8EY8gP+gIWFKIgGP8PGH7DwE8RSQRALbzYLoqLeZeeeOXPPnTMziq1rrmDsISD19Pb1DwQHQ0PDI6PhyNj4jmvVHJXnVEu3nD1FdrmumTwnNKHzPdvhsqHofFeprnfWd+vccTXL3BYNmxcNuWxqB5oqC6JKkWhBsfR9t2FQahYqsogdtkqROEswL2I/QdIHcfiRsSJXKGAfFlTUYIDDhCCsQ4ZLXx5JMNjEFdEkziGkeescLYRIW6MqThUysVUayzTL+6xJ805P11OrtItOv0PKGKbZPWuzZ3bHbtgje/+1V9Pr0fHSoKx0tdwuhY8ntl7/VRmUBSqfqj89CxxgxfOqkXfbYzqnULv6+tHJ89bq5nRzhl2wJ/J/zh7YLZ3ArL+ol1m+eYoQPUDy+3X/BDupRHIpsZhdiKfX/KcIYhJTmKP7XkYaG8ggR/s2cIZrtANvUkyalea7pVLA10TxJaTUB/Hpkis=</latexit> <latexit sha1_base64="CKO5UUyEUOslOhYAvO3T0LDEP9o=">AAACaXichVHLSgMxFD0dX7W+qm5EN8WiuCoZ8YUr0Y3LPmwVVMrMmNbodGaYSQu1+AOu3Im6UhARP8ONP+CinyBdVnDjwtvpgGhRb0hycnLPzUmiO6bwJGP1kNLV3dPbF+6PDAwODY9ER8dynl12DZ41bNN2d3TN46aweFYKafIdx+VaSTf5tn680drfrnDXE7a1JasO3y9pRUsUhKFJonJ7mukcavlonCWYH7FOoAYgjiCSdvQeeziADQNllMBhQRI2ocGjtgsVDA5x+6gR5xIS/j7HKSKkLVMWpwyN2GMai7TaDViL1q2anq826BSTukvKGGbYC3tgTfbMHtkr+/i1Vs2v0fJSpVlva7mTHzmbyLz/qyrRLHH4pfrTs0QBK75XQd4dn2ndwmjrKycXzcxqeqY2y25Zg/zfsDp7ohtYlTfjLsXT14jQB6g/n7sT5OYT6lJiMbUQX1sPviKMKUxjjt57GWvYRBJZOvcI57jEVaihjCoTymQ7VQkFmnF8CyX+CY6njB4=</latexit> A <latexit sha1_base64="j+cxzZhVCbNbXib5gpZSypq1LGY=">AAACaHichVHLLgRBFD3T3uMxjQViIzMZsZpUi1eshI0lRjMJk0l3K6OiX+mumYSJH7CxRKxIRMRn2PgBC5+AJYmNhTs9nQiCW6mqU6fuuXWqyvRtEUrGHhJKU3NLa1t7R7Kzq7snpfb2rYVeJbC4bnm2FxRMI+S2cLkuhbR5wQ+44Zg2Xzd3F+r761UehMJzV+Wez4uOUXbFtrAMSZS+aXJplNQMy7EoRn4CLQYZxLHkqVfYxBY8WKjAAYcLSdiGgZDaBjQw+MQVUSMuICSifY4DJElboSxOGQaxuzSWabURsy6t6zXDSG3RKTb1gJQjyLJ7ds1e2B27YY/s/ddatahG3csezWZDy/1S6nAw//avyqFZYudT9adniW3MRF4Fefcjpn4Lq6Gv7h+/5GdXsrVRdsGeyf85e2C3dAO3+mpdLvOVMyTpA7Tvz/0TrI3ntKnc5PJEZm4+/op2DCONMXrvacxhEUvQ6VyBI5zgNPGkqMqAMtRIVRKxph9fQkl/AJMoi6o=</latexit> Process B B C A (1) ↵(T ) B C Loss 時間方向に展開 <latexit sha1_base64="NGVgRi7/QrXgXZiqLLLRjwFlFE8=">AAACaXichVG7SgNBFD1Z3/GRRBvRRgwRqzArvrASbSw1MQ9IguyuYxyzL3YnAQ3+gJWdqJWCiPgZNv6AhZ8glgo2Ft5sFkRFvcPMnDlzz50zM7prCl8y9hhROjq7unt6+6L9A4NDsXhiOO87dc/gOcMxHa+oaz43hc1zUkiTF12Pa5Zu8oJeW23tFxrc84Vjb8p9l1csrWqLHWFokqh8uapZlrYVT7I0C2LiJ1BDkEQY6078GmVsw4GBOixw2JCETWjwqZWggsElroImcR4hEexzHCJK2jplccrQiK3RWKVVKWRtWrdq+oHaoFNM6h4pJ5BiD+yGvbB7dsue2PuvtZpBjZaXfZr1tpa7W7Gj0ezbvyqLZondT9WfniV2sBh4FeTdDZjWLYy2vnFw8pJdyqSaU+ySPZP/C/bI7ugGduPVuNrgmXNE6QPU78/9E+Rn0up8em5jNrm8En5FL8YxiWl67wUsYw3ryNG5ezjGKc4iz0pCGVXG2qlKJNSM4EsoyQ+InYwb</latexit> Process C <latexit sha1_base64="m5xr0gNRbxRT/QPADKr10cehi9c=">AAACtHichVHLShxBFD22eeiYxFE3gpvBwWAgDLdFRnElunHnc1SwzVDd1kwK+0V3z4A2/QP+gAtXCiLi2i9wkx/IQrLVhbhUcOPCOz0NITGaW1TVqVP33DpVZfq2CiOiyw6t883bd++7unM9Hz5+6s339a+GXiOwZMXybC9YN0UobeXKSqQiW677gRSOacs1c3u2tb/WlEGoPHcl2vHlpiPqrqopS0RMVfPzxpassTatFAsV1DwubNoNmcRB3Uxi/WuBSmPj7THJGXXhOOJbbPxDMLryJanmi1SiNArPgZ6BIrJY8PInMLAFDxYacCDhImJsQyDktgEdBJ+5TcTMBYxUui+RIMfaBmdJzhDMbvNY59VGxrq8btUMU7XFp9jcA1YWMEI/6ZTu6Aed0Q09vlgrTmu0vOzwbLa10q/27g0uP/xX5fAc4ftv1aueI9QwmXpV7N1PmdYtrLa+ubt/tzy1NBJ/piO6Zf+HdEkXfAO3eW8dL8qlA+T4A/S/n/s5WB0r6eVSeXG8OD2TfUUXhjCMUX7vCUxjDguo8Lnn+IUrXGtlzdAsTbZTtY5MM4A/QnOfAJ08qOA=</latexit> <latexit sha1_base64="QylhaFuGqSm7D18V+PJ1AMPmS9c=">AAACtHichVHLShxBFD12HupE46ibQDaDg6Igw22RUVyJ2WQXX6OCrUN1WzMW1nQ33T0Dpukf8AdcZKUgQVznC9z4A1lItnEhWRrIxoV3ehqCj8RbVNWpU/fcOlVl+1qFEdFll/Hi5avX3T29uTd9/W8H8oNDa6HXDBxZcTztBRu2CKVWrqxEKtJyww+kaNhartt7H9r76y0ZhMpzV6N9X241RN1VNeWIiKlq/pO1I2usTSvFQgU1jwvbuimTOKjbSWxOFqg0Nd0Zk5wltL8rtmPrCcG4OZFU80UqURqFx8DMQBFZLHr5r7CwAw8OmmhAwkXEWEMg5LYJEwSfuS3EzAWMVLovkSDH2iZnSc4QzO7xWOfVZsa6vG7XDFO1w6do7gErCxil73RKN3RBZ3RNt/+sFac12l72ebY7WulXBw7erfx5VtXgOcLuX9V/PUeoYTb1qti7nzLtWzgdfevz4c3K3PJoPEbH9Iv9H9ElnfMN3NZv52RJLn9Bjj/AfPjcj8HaVMksl8pL08X5hewrevAeIxjn957BPD5iERU+9xt+4CeujLJhGY4hO6lGV6YZxr0w3DtdTqjA</latexit> <latexit sha1_base64="IChFqCDi6LkF4UsnpDAf3NuX75M=">AAACtHichVFNSxtBGH5cbWtjW6NeCr0EQ4pCCe+KpOJJ9NJbNTYacDXMrpM4uF/sbgK67B/wD3jwpFCKeO4v8OIf8BC82oP0aMFLD32zWSittr7DzDzzzPu888yM6dsqjIi6A9rg0JOnz4af50ZevHw1mh8bXwu9dmDJmuXZXlA3RSht5cpapCJb1v1ACse05bq5u9TbX+/IIFSe+yna8+WmI1quaipLREw18h+NbdlkbVopFipoelzYtNsyiYOWmcT6uwKVZ2b7Y5IzWsJxxFZsPCCY0qeTRr5IZUqjcB/oGSgii2Uv/wUGtuHBQhsOJFxEjG0IhNw2oIPgM7eJmLmAkUr3JRLkWNvmLMkZgtldHlu82shYl9e9mmGqtvgUm3vAygJKdEmndEsXdEY39POfteK0Rs/LHs9mXyv9xujB69W7R1UOzxF2fqv+6zlCE3OpV8Xe/ZTp3cLq6zv7h7er89VS/JZO6Dv7P6YunfMN3M4P6/OKrB4hxx+g//3c98HaTFmvlCsrs8WFxewrhvEGk5ji936PBXzAMmp87ldc4RrftIpmaJYm+6naQKaZwB+hub8AVvaovQ==</latexit> <latexit sha1_base64="c+g809yV4M2SUrv+Ki2sEQMrVZY=">AAACs3ichVFNSxtBGH5ctU1jW6NehF5Cg8VCCe+KRvEk9eKp+BUVEht2NpN0cL/YnQR02T/gH+jBkwUR6bX/wIt/wIO9thfxaKGXHvpmsyCt/XiHmXnmmfd555kZETgq0kRXA8bg0PCDh7lH+ZHHT56OFsbGtyK/E9qyavuOH+4IK5KO8mRVK+3InSCUliscuS32lnv7210ZRsr3NvV+IHddq+2plrItzVSj8KbelC3WppViS4UtnwsLpyOTOGyLJDZfFak8M9sfk3xdSG29jet/yJ82XyaNQonKlEbxPjAzUEIWq37hFHU04cNGBy4kPGjGDixE3GowQQiY20XMXMhIpfsSCfKs7XCW5AyL2T0e27yqZazH617NKFXbfIrDPWRlEVN0SWd0Sxf0ka7px19rxWmNnpd9nkVfK4PG6OHkxvf/qlyeNd7dqf7pWaOFhdSrYu9ByvRuYff13YP3txuL61PxC/pAN+z/mK7onG/gdb/ZJ2ty/Qh5/gDz9+e+D7ZmymalXFmbLS29zr4ih2d4jml+73ksYQWrqPK5n/AZX/DVmDNqhjCa/VRjINNM4Jcw3J9GA6hM</latexit> ↵(1) 出力 x̂ (1) <latexit sha1_base64="GP4S+X4neVuKBV5mZHq2tO/HCXs=">AAACs3ichVHLShxBFD22MerExFE3gpshg2IgDLfFF65EN1mJr1FhxgxdPTVjYb/orhnQpn/AH3DhykAI4tY/cJMfcKHbZBOyNJBNFrnT0yCJedyiqk6duufWqSoROCrSRLc9Ru+Tvqf9A4O5Z0PPXwznR0Z3Ir8V2rJs+44f7gkrko7yZFkr7ci9IJSWKxy5Kw5XO/u7bRlGyve29VEg912r6amGsi3NVC2/Vq3LBmvTSrGlwobPhYXTkkkcNkUSm68LVJqZ7Y5Jriqktt7G1T/kT2+/Smr5IpUojcJjYGagiCzW/fwHVFGHDxstuJDwoBk7sBBxq8AEIWBuHzFzISOV7kskyLG2xVmSMyxmD3ls8qqSsR6vOzWjVG3zKQ73kJUFTNINXdA9faRL+kI//lorTmt0vBzxLLpaGdSGT8a3vv9X5fKscfCg+qdnjQYWU6+KvQcp07mF3dW3j0/vt5Y2J+Mpekdf2f853dI138Brf7Pfb8jNM+T4A8zfn/sx2JkpmfOl+Y3Z4vJK9hUDmMBLTPN7L2AZb7COMp97hTt8wmdjzqgYwqh3U42eTDOGX8JwfwKMSahv</latexit> <latexit sha1_base64="oA2dknGci/Cw9Bwbz9Agx4MRB/I=">AAACtHichVHLShxBFD22JuqYxFE3gpshg8FAGG6LjCEr0Y07n6OCbYbqtmYsrOluunsGtOkf8AdcuFIQEdd+gZv8QBbiNlmELA24ySJ3ehqCGs0tqurUqXtunaqyfa3CiOi6y+juefGyt68/N/Dq9ZvB/NDwWug1A0dWHE97wYYtQqmVKyuRirTc8AMpGraW6/buXHt/vSWDUHnuarTny62GqLuqphwRMVXNL1jbssbatFIsVFDzuLCtmzKJg7qdxOaHApUmpzpjkrOE9nfE59j6h2Bi9X1SzRepRGkUHgMzA0Vksejlz2BhGx4cNNGAhIuIsYZAyG0TJgg+c1uImQsYqXRfIkGOtU3OkpwhmN3lsc6rzYx1ed2uGaZqh0/R3ANWFjBOX+mcbukLXdAP+v1krTit0fayx7Pd0Uq/OngwunL3X1WD5wg7f1XPeo5Qw8fUq2Lvfsq0b+F09K39w9uVT8vj8Ts6oZ/s/5iu6Ypv4LZ+OadLcvkIOf4A8+FzPwZrkyWzXCovTRVnZrOv6MMY3mKC33saM5jHIip87iVu8A3fjbJhGY4hO6lGV6YZwb0w3D+jlKjj</latexit> (T ) (T ) <latexit sha1_base64="CxhCYEXas1BmijUkc6sYpkr8MIo=">AAACeHichVG7SgNBFD1ZXzE+Ek0j2ASDryZMgi+sgjaWiRoVkhB21zFZsi92J8EY8gP+gIWFKIgGP8PGH7DwE8RSQRALbzYLoqLeZeeeOXPPnTMziq1rrmDsISD19Pb1DwQHQ0PDI6PhyNj4jmvVHJXnVEu3nD1FdrmumTwnNKHzPdvhsqHofFeprnfWd+vccTXL3BYNmxcNuWxqB5oqC6JKkWhBsfR9t2FQahYqsogdtkqROEswL2I/QdIHcfiRsSJXKGAfFlTUYIDDhCCsQ4ZLXx5JMNjEFdEkziGkeescLYRIW6MqThUysVUayzTL+6xJ805P11OrtItOv0PKGKbZPWuzZ3bHbtgje/+1V9Pr0fHSoKx0tdwuhY8ntl7/VRmUBSqfqj89CxxgxfOqkXfbYzqnULv6+tHJ89bq5nRzhl2wJ/J/zh7YLZ3ArL+ol1m+eYoQPUDy+3X/BDupRHIpsZhdiKfX/KcIYhJTmKP7XkYaG8ggR/s2cIZrtANvUkyalea7pVLA10TxJaTUB/Hpkis=</latexit> update 学習可能なパラメータ SGD 深層展開は反復アルゴリズムの収束速度と解の質を改善することができる． 33 / 59

深層展開の効果 (ISIT2024) GF 復号法 (AWGN 通信路)，符号長 204，(3,6) 正則 LDPC 符号 (a) Eb/N0=6dB (b) Iteration = 50 DGF DU-DGF DGF DU-DGF 10 1 Bit Error Rate Bit Error Rate 10 1 10 2 10 2 10 3 10 3 10 4 0 20 Iteration 40 10 4 0 2 4 Eb/N0 (dB) 6 34 / 59

テンソル計算型 BP と GF 復号法の比較 テンソル計算可能 AWGN 性能 行列サイズ テンソル計算型 BP YES Good #edges × n GF 復号法 YES Modest m×n #edges はタナーグラフに含まれるエッジの本数． GF 復号に関するコメント BP と比較して，GF 復号法で必要となる行列ベクトル積計算のサイズは小さい． GPGPU によるマルチスレッド計算において必要とされる計算リソースも少なく，物理 計算における必要回路サイズも小さい. 誤差逆伝播法や後ろ向き自動微分計算における計算負荷が低い． GF 復号法の AWGN ビット誤り率性能は，ビットフリップ型復号法に近い． 負対数尤度勾配 ∇L を取り替えるだけで様々な通信路に適用可能 → プラグ&プレイ 35 / 59

MIMO 通信路におけるビット誤り率特性 復号反復式: s (k+1) = s (k) − η(AT (As (k) − y ) + γ∇hα,β (s (k) )) ' $ ISIT 2024, W. and Wei Baseline (MMSE + BP) n = 204, m = 102, QPSK A は MIMO 通信路のチャネ ル行列 GF decoding w. Deep unfolding 既存方式 “BP+MMSE” を上 回る性能を達成 深層展開が性能改善に有効 & % 36 / 59

GF 復号に関するまとめ GF 復号法 テンソル計算可能: 次世代 AI アクセラレータによる計算に向いている プラグ&プレイ: 勾配 ∇L を取り替えるだけで色々な通信路に適用可能 連続&離散: アナログ実装・デジタル実装のどちらにも対応 AI フレンドリ: すべての部分プロセスが微分可能．アルゴリズム内部に AI コンポーネ ントを埋め込むことが容易 残された課題 AWGN 性能の向上 学習可能な負対数尤度勾配 ∇L 37 / 59

補足情報: AWGN 性能向上に関する関連研究 A.Tsouchlos, H.Jaekel and L. Schmalen, “List-based Optimization of Proximal Decoding for LDPC Codes,” Sep., 2024. https://arxiv.org/pdf/2409.07278 近接勾配復号法 (勾配法の代わりに近接勾配法を利用した関連アルゴリズム) にポストプ ロセスを追加することで，大幅に AWGN 復号性能が向上することを示した． ビットごとに信頼度を測定し，信頼度の低い N ビットを総当り探索 推定語のリストを出力 → AWGN 性能向上については現在，われわれも取り組んでいるものの，他グループに先行 されてしまっている状況．今後巻き返していきたい． 38 / 59

• https://arxiv.org/pdf/2409.07278

本日の講演の流れ 2. 通信路モデルのない世界へ スコアベース生成モデルに基づく通信路学習 39 / 59

モチベーション システム設計時に通信路モデルが陽に得られないとき システム設計時に通信路モデルが未知の場合には，復号アルゴリズムの設計は一般には 困難な問題となる． 通信路特性の時間的変化が顕著な通信路においては，正確な通信路モデルを設計時に仮 定するのが難しい場合もある． 多様な通信路環境をカバーするシステムを設計したいとき． 機械学習アプローチの登場 近年，機械学習技術により「通信路」を学習しようというアプローチも現れてきている． 通信路 LLR 関数の学習 2 ブラックボックス的に符号化器・通信路・復号器をひっくるめて学習 → まだ「決定打」となるアプローチは登場していない． 2 O.Shental and J.Hoydis, “Machine LLRning: Learning to Softly Demodulate,” arXiv:1907.01512, 2019. 40 / 59

われわれの方法論 GF 復号法を前提とする 負対数尤度勾配 ∇L を学習データから学習できれば十分 尤度関数 p(y |x) の学習よりそちらのほうが筋がよさそう 通信路により定義されるベクトル場そのものを学習 生成 AI 分野で注目されている「スコアマッチング学習」をほぼそのまま適用できる 方法論の概略 1 ∇L をニューラルネットワークでモデル化 2 スコアマッチング学習の技法に基づいて学習 3 GF 復号法の復号プロセスにおいて，学習された ∇L を利用 41 / 59

スコアベース生成モデル (Song et al. 2021) (1) 設定と目標 未知の確率密度関数 P(x): ターゲット分布 P に従う学習データ D ≡ {d1 , d2 , . . . , dD } が手元にある ここでの目標は P に従う新たなサンプル x ∗ ∼ P の生成 (サンプリング) スコア関数に基づくサンプリング (真のスコア関数が既知である場合) スコア関数を準備: s(x) ≡ ∇ ln P(x) (23) ランジュバンサンプリング: √ ϵ xt = xt−1 + s(st−1 ) + ϵzt , 2 により P に従うベクトルのサンプリングを行う． t = 1, 2, . . . , (24) 42 / 59

スコアベース生成モデル (Song et al. 2021) (2) 未知のスコア関数を学習する 真のスコア関数は未知．したがって，学習データ D からスコア関数を学習したい ニューラルスコア関数を sθ (x) とする． 雑音除去スコアマッチング (Denoising Score-Matching) 損失関数 " # 1 x̃ − x 2 E E sθ (x̃) + 2 2 x∼p(x) x̃∼N (x,σ I ) σ2 2 (25) を利用してニューラルスコア関数の学習を行う． Y. Song, J. Sohl-Dickstein, D. P. Kingma, A. Kumar, S. Ermon, and B. Poole, “Score-based generative modeling through stochastic differential equations,” in Proceedings of the 10th International Conference on Learning Representations (ICLR), pp. 399–406, 2021. この損失関数は何を意味しているのか？ 43 / 59

Tweedie’s formula と雑音除去スコアマッチング損失関数 Tweedie’s formula (Efron, 2011) x ∼ P, x̃ = x + e, e ∼ N (0, σ2 I ) であるとき， E[x|x̃] = x̃ + σ2 ∇P(x̃) P(x̃) (26) が成り立つ．ここで，E[x|x̃] は x の MMSE 推定値である． 式 (26) を変形することにより， E[x|x̃] − x̃ σ2 が得られる．雑音分散 σ2 が小さいときに E[x|x̃] ≃ x であり，式 (27) から， ∇ ln P(x̃) = x̃ − x σ2 雑音除去スコアマッチング損失関数の最小化 → sθ (x̃) ≃ s(x̃) s(x̃) = ∇ ln P(x̃) ≃ − (27) (28) 44 / 59

スコアベース通信路学習 (1) GF 復号法の反復中に利用される負対数尤度関数をスコアベース学習を利用して学習するこ とができれば，GF 復号法を通信路モデルが確定していない通信路にも適用することが可能． 議論の簡単化のための今回の仮定 加法的雑音通信路 (i.e., y = x + e) p(y |x) = Q(y − x) (29) となる確率密度関数 Q の存在を仮定する． セグメントワイズ独立同分布性を仮定する．セグメントワイズ独立同分布性を持つ通信 路では p(y |x) は下記のとおり分解される: p(y |x) = K Y i=1 p(yi′ |xi′ ) = K Y q(yi′ − xi′ ), (30) i=1 45 / 59

スコアベース通信路学習 (2) 負対数尤度勾配のニューラルモデル  −^ sθ (y1′ − x1′ ) ′ ′  −^   sθ (y2 − x2 )  ∇L(x; y ) = −∇x ln p(y |x) ≈ −  . ..   .  (31) −^ sθ (yK′ − xK′ ) ニューラルスコアモデル (L 層フィードフォワード型ネットワーク) s^θ (e ′ ) = hL , hi+1 = gi (Wi hi + bi ), ′ h1 = e . (32) i = 1, 2, . . . , L − 1, (33) (34) 46 / 59

スコアベース通信路学習の手順 学習可能パラメータ集合 θ 内のパラメータを初期化したのちに，下記の手順を反復する． 学習の手順 通信路モデルに従い，雑音サンプルを含むミニバッチ E ≡ {ed′ } を生成する． 雑音付加サンプルを ẽd′ = ed′ + nd として生成する．ここで，d ∈ [D] であり， nd ∼ N (0, σ2 I ) である． スコア適合損失関数を L(θ; E) ≡ ẽ ′ − e ′ 1 X s^θ (ẽd′ ) + d 2 d D σ D 2 d=1 2 . (35) と定義する． 自動微分 (もしくは，誤差逆伝播法) を実行し，損失関数 L の θ に関する勾配を求める． パラメータ集合 θ 内のパラメータを勾配に基づき更新する (SGD，ADAM などを利用)． 47 / 59

数値例: ２次元人工雑音 ' $ 2 次元相関性雑音 1000 サンプル (右図参照) ニューラルネットワーク 3 層のフィードフォワード型 ニューラルネットワーク ▶ 活性化関数として ReLU 関数を 利用 ▶ 隠れ層のサイズは 64 ▶ ミニバッチのサイズを 100 10, 000 回の訓練反復 ガウス乱数の標準偏差 σ = 0.3 & % 48 / 59

数値例: ２次元人工雑音 与えられた雑音サンプル (1000 サンプル) 学習されたベクトル場 雑音サンプルの密度の高い部分が引き込み領域 (Basin) となるベクトル場が学習されている． 49 / 59

数値例: GF 復号の復号過程 推定誤りビット個数を反復数の関数としたプ ロット (100 試行) ' $ n = 204，パリティシンボル数 m = 102 の (3, 6) 正則 LDPC 符号 GF 復号法の初期点としては， N (0, 0.12 I ) に従う乱数ベクトル α = β = 1, η = 0.05, γ = 1.0 & % 50 / 59

スコアベース通信路学習に関するまとめ 本日の話の詳細については，12 月開催の SITA2024 にて報告予定． 特徴 負対数尤度勾配 (ベクトル場) の学習: 尤度関数，対数尤度関数の学習よりも容易 スコアマッチング学習: 生成 AI に関する従前研究の知見を有効に活かせる 広い適用範囲: 無記憶性雑音だけではなく，記憶性の雑音も学習できる 残された課題 信号依存性雑音への対応: 現状では加法的雑音のみの取り扱い 難しいハイパーパラメータの決定: 特に学習の際に必要な付加雑音分散 σ2 の決定が難し い．生成 AI 分野で利用されるように σ2 のスケジューリングが必要かもしれない さらなる研究の積み上げが必要 51 / 59

本日の講演の流れ 3. NP 困難問題への挑戦 勾配ベースマルコフ連鎖モンテカルロ (MCMC) 法の復号問題への応用 52 / 59

勾配ベース MCMC 法へのモチベーション 勾配ベースマルコフ連鎖モンテカルロ法の利用を検討する動機 GF 復号プロセスの失敗ケース 符号語でない停留点の近辺で探索点がトラップされる → 復号プロセスの失敗 送信符号語とわずか数ビットの違いが残るケースが多い 近接勾配復号法の改良 (2024) においても「近傍探索」が性能向上の鍵となっている 理論分野・MIMO 信号推定分野における勾配ベース MCMC の台頭 論文 Y.-A. Ma, et al. “Sampling can be faster than optimization”,2018 において，非 凸関数最適化において，勾配ベース MCMC の有効性が理論的に証明された． 最近，MIMO 信号検出の分野で勾配ベース MCMC の利用が注目されている．例えば， X.Zhou, L.Liang, J.Zhang, C.-K. Wen, and S. Jin, “Gradient-Based Markov Chain Monte Carlo for MIMO Detection”, 2024 アイデア: GF 復号プロセスに勾配ベース MCMC を組み合わせることで，大きな性能向上が 得られるのではないか？→ サンプリングベースの復号アルゴリズム 53 / 59

メトロポリス法 (Metropolis, 1953) P(x) がサンプリングの目標分布となる．また，g (x) を P と比例関係にある既知の関数とす る．提案分布 Q(x|y ) を用意する．この提案分布はメトロポリス法の状態更新に利用する． 対称性 Q(x|y ) = Q(y |x) を仮定する． メトロポリス法の処理の流れ (t 回目の更新) 分布 Q(x|xt ) に従うサンプル x ∗ を生成． 採択率 α= P(x ∗ ) g (x ∗ ) = g (xt ) P(xt ) (36) を計算する． 閉区間 [0, 1] で値を取る一様乱数 u を生成する． u ≤ α であれば, 提案点を採択し，xt+1 = x ∗ とする． u > α であれば，提案点を棄却し，xt+1 = xt とする． 以上の手続きを十分な回数繰り返す． 54 / 59

勾配ベース MCMC 法 勾配ベース MCMC 法 (Y.-A. Ma et al. 2018) いま，ターゲット分布をギブス分布 P(x) = 1 exp (−f (x)) Z (37) であるとしよう．勾配ベース MCMC 法は，提案分布 Q(x ∗ |xt ) として，多次元ガウス分布 N (xt − ηt ∇f (xt ); σ2t I ) (38) を取る場合のメトロポリス法である． 多次元ガウス分布に基づく提案分布 P のモードと提案分布のモードを一致させるように勾配降下プロセスが提案分布に導入 されている 55 / 59

GF 復号法に勾配ベース MCMC を取り入れる (1) 離散時間 GF 復号法反復式: s (k+1) = s (k) − η(k) (∇L(s (k) ; y ) + γ∇hα,β (s (k) )) (39) ここで，この最小化に関する目的関数は， f (x) = L(x; y ) + γhα,β (x) (40) である．これは，近似事後確率分布 p̃(x|y ) = 1 exp (−f (x)) Z (41) の最大値 (f の最小値) を求めるための勾配反復と見ることもできる． → 近似事後確率分布からのサンプリングを考える! (最小化からサンプリングへ) → 提案分布を N (s (k) − η(k) (∇L(s (k) ; y ) + γ∇hα,β (s (k) )); (σ(k) )2 I ) (42) とする勾配ベース MCMC を考える． 56 / 59

GF 復号法に勾配ベース MCMC を取り入れる (2) 勾配ベース MCMC に基づく復号法 下記の手順を十分に反復する: ガウス乱数 r ∼ N (0, I ) を生成 s (prop) := s (k) − η(k) (∇L(s (k) ; y ) + γ∇hα,β (s (k) ) + σ(k) r 次の計算を行う: α= exp(−f (s (prop) )) exp(−f (s (k) )) 一様乱数 u ∼ U [0, 1] を生成 もし，u ≤ α ならば，s (k+1) = s (prop) . そうでなければ s (k+1) = s (k) 目的関数値の増加もある確率で許されることから，局所解・停留点からの脱出も可能となる 57 / 59

勾配ベース MCMC 復号法に関するまとめ 特徴 近似事後確率分布からのサンプリング: 推定候補 (リスト) の生成 停留点からの脱出: 停留点から脱出して広い領域の探索が可能 計算量 vs 精度のきめ細かいトレードオフ制御が可能 残された課題 実験の結果がでてくるのがこれから！ (風呂敷広げるだけ広げて，畳まずにすみません． ． ．) 58 / 59

全体のまとめ：AI・機械学習とともに進化する誤り訂正符号 本日の講演内容 進化する AI ハードウェアに適合する復号法: GF 復号法 通信路モデルのない世界へ: スコアベース通信路学習 NP 困難問題への挑戦: 勾配ベース MCMC 復号法 今後，AI・機械学習の進展・発展に伴って，時代に合わせた形で誤り訂正技術も進化し ていくものと予想しています． 59 / 59