Microsoft PowerPoint - 若手研究者のための2017_for_dist.pptx

Size: px

Start display at page:

Download "Microsoft PowerPoint - 若手研究者のための2017_for_dist.pptx"

がんまかわらい
4 years ago
Views:

1 スパース重ね合わせ符号の状況と課題竹内純一三村和史九州大学大学院システム情報科学研究院広島市立大学大学院情報科学研究科 27//28 若手研究者のための講演会 at 新潟県月岡温泉 Thanks to: 川喜田雅則, 高木美里, 武石啓成, 波多江優和, 宮本耕平 Special thanks to: 竹内啓悟

2 スパース重ね合わせ符号 (Sparse superposition codes; SS 符号 ) [Barron and Joseph 2] (ISIT2) ガウス通信路に直接適用される誤り訂正符号符号語が,ではなく実数値をとる符号語は辞書の列ベクトルのスパースな線形結合により構成辞書の例 AWGN 通信路容量を達成する

3 通信路容量を達成する符号通信路容量に近い伝送レートを達成し, かつ効率的に符号化復号が行える符号をつくりたい 993 年 : ターボ符号 [Berrou ら ] 従来と比べて格段に高い伝送レートを達成 29 年 :Polar 符号 [Arikan] ( 離散入力通信路 ) 2 年 : 空間結合 LDPC 符号 [Kudekar et al.] 24 年 : スパース重ね合わせ符号 [Joseph &Barron] AWGN 通信路容量を達成 3

4 SS 符号のブロック誤り確率の上界通信路容量 C, レート R, 符号長 n, 平均誤り確率 p e 最尤復号のとき [Joseph and Barron 2()] 効率的復号のとき [Joseph and Barron 4()] 4

5 ガウス通信路を用いた通信目標 :,,, メッセージ : 一様分布送信側受信側メッセージ符号語受信語復号結果符号化ガウス通信路復号伝送レート : 通信路容量 : 5

6 平均パワー制約符号語ガウス通信路受信語は各次元独立に, にしたがう ( 平均, 分散の正規分布 ) 符号語の平均電力制限 : 6

7 ガウス通信路の通信路容量平均電力制限のもとでの通信路容量通信路符号化定理 [Shannon 948] によると, これを達成するのは, 符号語 c が各次元独立ににしたがうとき 7

8 スパース重ね合わせ符号対写像の数はちょうど個 ( スパース ) 辞書 8

9 符号化対写像辞書の数はちょうど個 ( スパース ) 9

10 分割重ね合わせ符号辞書個のセクションに分けるこちらの方が符号化の設計が簡単今後はこれを前提として議論

11 各パラメータの関係全てのメッセージの数と全ての符号語の数は等しいので伝送レートより, の決め方に自由度があるはからまで取り得る

12 セクションサイズ率 a セクションサイズと分割数の関係辞書サイズ ( : セクションサイズ率 ) を大きくするとはスパースになる性能を保証するためには, がある程度大きくなければならない 2

13 辞書 X の作り方各要素それぞれ独立にこれにより, 符号語の平均電力制約が満たされる符号語は各次元独立に, にしたがうこれはガウス通信路の通信路容量を達成する分布であるで生成ただし, 現実のデバイスで厳密に正規乱数を実装することはできない乱数値がバウンドされない乱数値の表現に無限の精度が必要

14 復号受信語と辞書が与えられたもとでスパースなベクトルを推定圧縮センシングと同様の枠組み CDMA 通信との類似性最小二乗復号 ( 計算量無視 ) と効率的復号アルゴリズムについて後に紹介 4

15 復号アルゴリズム最尤復号 [Barron & Joseph, Joseph & Barron 2] 誤り確率 O(exp(- (C-R) 2 n)) 適応的逐次復号器 [Barron & Joseph, Joseph & Barron 4] 誤り確率 O(exp(- (C M -R) 2 n)) power allocation simple 法と直交化付きの二種類受信語と辞書列の相関が閾値を超えたものを逐次復号ベイズ最適適応的逐次復号器 [Barron & Cho 2] 各列の事後確率を反復計算で求め, 最後にMAP 推定ベイズ最適 AMP [Barbier et al 4], [Rush & Venkataramanan 5] 空間結合 vs power allocation 5

16 復号誤りの定義 : 真の : 復号結果ブロック誤り : : 誤って復号されたセクションの数セクション誤り率実はスパース重ね合わせ符号単体では高い確率でが小さいことしか言えない 6

17 RS 符号との組み合わせリードソロモン符号 (RS 符号 )[Reed and Solomon 96] を外符号 (outer code) として組み合わせて用いる小さいブロック誤りの確率を実現通信路符号化 (RS 符号 ) 符号化 ( 重ね合わせ符号 ) 復号 ( 重ね合わせ符号 ) 復号 (RS 符号 ) inner code outer code 7

18 最小二乗復号の誤り確率 [Joseph & Barron 22] A. Joseph and A. R. Barron, Least squares superposition codes of moderate dictionary size are reliable at rates up to capacity, IEEE Trans. Inf. Theory, vol. 58, no. 5, pp , May 22. 8

19 最小二乗復号最小二乗復号 : 最尤復号の意味で最適だが, 計算量的に困難 ( 再構成 ) 9

20 セクションサイズ率 a セクションサイズと分割数の関係辞書サイズ ( : セクションサイズ率 ) を大きくするとはスパースになる性能を保証するためには, がある程度大きくなければならない 2

21 定理 [Joseph and Barron 22] は各要素独立にから生成する. とし, セクションサイズ率はを満たすものとする. このとき, に対して, が成り立つ. ただし, である. 注意 : 確率変数は, ノイズだけでなく, 辞書も含めて考えている 2

22 a v のグラフ (L = 64) [Joseph and Barron 22] より 22

23 効率的復号アルゴリズム [Barron &Joseph ][Joseph & Barron 4] [] A. R. Barron and A. Joseph, Towards fast reliable communication at rates near capacity with Gaussian noise, Proc. IEEE. Int. Symp. Inf. Theory, Austin, Texas, June 3 8, 2, pp [2] A. Joseph and A. R. Barron, Fast Sparse Superposition Codes Have Near Exponential Error Probability for R < C, IEEE trans. IT, Feb

24 効率的復号アルゴリズム OMP (Orthogonal Matching Pursuit) に似た繰り返しアルゴリズムで動く ( 並列処理必要 ) ただし外符号のリードソロモン符号の計算に多項式時間くらいかかる 24

25 power allocation( の各成分を可変に ) 辞書個のセクションに分ける 25

26 との作り方各要素それぞれ独立にで生成が満たされるようにする平均電力制約を満たすためとするのが最も簡単しかしこれでは通信路容量を達成できない 26

27 電力割り当て P (l) :Capacity 2 : 小さい正定数はより少しだけ大きいがに近いところでは, は一定になる 2 の方が少し性能が良くなる 27

28 Step とするに対して, となるがあれば, それを復号結果とするの最適値は約 (SN 比が小さくないとき ) 出力 : このステップで復号されたの集合 28

29 Step 2, に対して, となるがあれば, それを復号結果とする出力 : このステップで復号されたの集合 29

30 Step k, に対して, となるがあれば, それを復号結果とする出力 : このステップで復号されたの集合 3

31 終了条件復号されたの数がになったとき閾値を超えるが一つもなかったとき 3

32 直交化付きアルゴリズムを別の統計量に変える方法 32

33 Step ( 前と同じ ), とするを計算となるがあれば, それを復号結果とする出力 : このステップで復号されたの集合 33

34 Step 2, : のに対する直交成分を計算を計算となるがあれば, それを復号結果とする出力 : このステップで復号されたの集合 34

35 Step, : のに対する直交成分を計算を計算となるがあれば, それを復号結果とする出力 : このステップで復号されたの集合 35

36 直交成分の作り方シュミットの直交化法により行うただし 36

37 復号のペースを制限する方法 37

38 の作り方の変更 ( ) :step において閾値を超えたの集合をに入れていくがを超えないような制限の元で, できるだけ多く入れるは指定しておく 38 (にするととなる )

39 終了条件復号されたの数がになったとき閾値を超えるが一つもなかったときが以上になったとき 39

40 指定すべきパラメータ電力割り当て 2 復号のペース制限 3 のパラメータを構成するため 4

41 update function ただし, 率, は標準正規分布の上側確辞書のサイズと通信路 ( 決まる ), 閾値を設定すると 4

42 g L (x) によるペースの観察 [Barron and Joseph 2] より 42

43 の設定を用意で設定のとき 2 のとき 43

44 ベイズ最適適応的逐次復号 [Barron and Cho 2] 初期ステップ各列,2,, と各セクション,2,, に対して以下を計算,,,,,,,,,, Barron and Cho, ``High rate sparse superposition codes with iteratively optimal estimates." Proc. of IEEE Intl. Symp. on Inform. Theory. Cambridge, MA, July 22, pp

45 ベイズ型アルゴリズム ( 続き ) 第ステップ以下を計算,,,,,,,, 規定の回数反復した後, 最終的なから台を求めて終了 (MAP) 45

46 ベイズ型アルゴリズムの特徴, が第ステップの時点で列が正しい列であるという事後確率は,, で各成分対応する列の事後確率で決まるステップが進むにつれがに近づくの期待値は第ステップの時点で正しく推定できるセクション数の割合の期待値と一致するLemma2, [Barron and Cho 22] AMP の t 状態発展式の役割に類似. 46

47 E の振る舞いは g で分かる [Barron & Cho 22] より 47

48 実験各アルゴリズムによる復号を行ってセクション誤り率をみる : 誤って復号されたセクション数 : 列が復号されなかったセクション数 48

49 復号実験パラメータ snr=7 レート R =.3C,.4C,.5C. 各アルゴリズムで各設定回ずつ実験ビット誤り率 < q となる回数を計測 (q=.~.5) 使用環境 R on Linux, Intel(R) Xeon(R) CPU 2.9GHz 逐次復号アルゴリズムについて閾値 2log. 49

50 達成可能レート宮本らによる実験で,Joseph & Barron アルゴリズムで R =.4C, ベイズ最適化で,R =.5C 程度参考 ([Barron & Cho 22] の図 ) 5

51 考察 at ISIT22 (Boston) LDPC 符号 MAP 復号で C 達成 BP による効率的復号では C までギャップ空間結合で効率的復号で C 達成. 圧縮センシング (Bayes 最適 AMP) L 再構成で情報理論的限界達成 L 再構成は性能のギャップあり. 空間結合で L と同等の性能 [Donoho et al. 23] スパース重ねあわせ符号最尤復号で C 達成効率的復号では大きなレートドロップ LDPC 符号と圧縮センシングの状況から類推して, 空間結合でレートドロップを改善できないか? 5

52 圧縮センシングとは (/2) 問題設定次元ベクトル, 観測行列 (, A によって次元ベクトルが次のように与えられているとする A~N, : ( ) スパースなベクトル圧縮率信号密度圧縮センシングでは非零要素の位置が未知である場合の復元をどの程度までが小さい範囲で行えるかを問題とする [5] 田中利幸, `` 圧縮センシングの数理,'' IEICE Fundamentals Review, Vol.4, No., pp.39 47,2 年. 52

53 圧縮センシングとは (2/2) 右に示す 3 種類のノルムを用いるノルム : ノルム : ノルム : ( ユークリッドノルム ) ノイズなし再構成 : arg min.. 再構成 : arg min.. ノイズあり ( 計算困難 ) で復元可能 ( 効率的 ) ( 弱しきい値 ) で復元可能また, 各要素が N, σ に従うノイズ W があると再構成 : arg min.. ( 計算困難 ) 再構成 : arg min.. ( 効率的 ) arg min λ ( ラグランジュ未定乗数法による ) 53

54 圧縮センシングの再構成アルゴリズム Approximate Message Passing (AMP) 再構成のアルゴリズムのつで理論的によいとされている条件 ( 残差のノルムが一定値以下, 反復回数が一定回数以上等 ) を満たすまで次の反復式を用いて未知ベクトルを推定 ( : 反復回数 ),λ η,λ [5] 田中利幸, `` 圧縮センシングの数理,'' IEICE Fundamentals Review, Vol.4, No., pp.39 47,2 年. 54

空間結合圧縮センシング空間結合手法特徴観測行列を帯対角の形にすることによって, 計算量を低く保ったまま復元限界を改良するというアイデア Bayes 最適 AMP と呼ばれるアルゴリズムを用いる未知ベクトルの事前分布をとすると, 復元可能なの下限はによって決まり, その値をとする [] Donoho, Javanmard, and

55 空間結合圧縮センシング空間結合手法特徴観測行列を帯対角の形にすることによって, 計算量を低く保ったまま復元限界を改良するというアイデア Bayes 最適 AMP と呼ばれるアルゴリズムを用いる未知ベクトルの事前分布をとすると, 復元可能なの下限はによって決まり, その値をとする [] Donoho, Javanmard, and Montanari, "Information theoretically optimal compressed sensing via spatial coupling and approximate message passing," IEEE transactions on information theory 59. (23):

56 空間結合圧縮センシングのアイデア空間結合の構造を, 単純化した例を使って説明する. もし,,, が推定できたとすると連鎖的に他の要素も決定する. 56

57 空間結合圧縮センシングの再構成アルゴリズム Bayes Optimal AMP 観測行列は行列によって決まる. : 観測行列 A の要素のインデックスを, 対応するブロックのインデックスに写す関数未知ベクトルについて事前分布を既知としている AMP はアダマール積を表す Bernoulli Gussian 事前分布の場合 [] Donoho, Javanmard, and Montanari, "Information theoretically optimal compressed sensing via spatial coupling and approximate message passing," IEEE transactions on information theory 59. (23):

58 スパース重ね合わせ符号における空間結合 [Barbier et al. 4] は Γ Γ のブロックに分けられる. インデックスを, とし, 各ブロックを, とする. 即ち, /Γ 列, /Γ 行となる. ここで /Γ, /Γ とする. 帯の幅を決定する, 行列の要素の値を決定する関数を導入. Γ, 2 とすると. において, は, と正規化し,, の各要素は N,, に従うシェイプマトリックス, [2] Barbier, Dia, and Macris, "Proof of Threshold Saturation for Spatially Coupled Sparse Superposition Codes," arxiv preprint arxiv:63.87 (26):

59 Replica 解析 : AMP vs 適応的逐次復号 [Barbier & Krzakala 24] Barbier and Krzakala, ``Replica analysis and approximate message passing decoder for superposition codes,'' in Proc. IEEE ISIT

60 空間結合 AMP 復号器の大極限理論保証 [Barbier, Dia, & Macris 6] 定理 6.2 孤立系理論限界と空間結合系 AMP 閾値の関係シェイプマトリックスが非常に大きいとき孤立系理論限界通信路符号化定理 : C lim セクションサイズが大通信路容量達成 Barbier, Mohamad, & Macris, "Proof of Threshold Saturation for Spatially Coupled Sparse Superposition Codes," arxiv preprint arxiv:63.87 (26):

61 実験 ( 波多江ら ): 孤立系 SS 符号の復号 ( 反復回で復元 ) 信号密度. のときの孤立系 AMP の限界.2385 であることがわかっている. 具体的な値は下表に示す. 符号長 75 ベクトルの次元 5 セクションサイズ圧縮率.35 信号密度. SN 比 5 伝送速度.7343C < 孤立系の実験設定 > 6

62 実験 2( 波多江ら ): 空間結合系 SS 符号の復号 ( 反復 63 回で復元成功 ) シェイプマトリックスを無限に大きくしたときの伝送速度をとするシェイプマトリックスのサイズは 55*5, 帯の幅は 6 としたブロックの符号長 2 ブロックのベクトル次元符号長 55 ベクトルの次元 5 セクションサイズ圧縮率.2 信号密度. SN 比 8 伝送速度.4537C 伝送速度.745C < 空間結合系の実験設定 > /2 /2 /3 /3 /3 /4 /4 /4 /4 /5 /5 /5 /5 /5 /5 /6 /6 /6 /6 /6 /6 /6 /6 /6 /6 /6 /6 /6 /6 O O < デザインマトリックスの構造 > /3 /3 /3 /2 /2 62

63 [Donoho, Javanmard, Montanari 3] のシミュレーションの追試 [ 大浦 6] [ 大浦 6] 大浦聡一郎, 状態発展式による空間結合圧縮センシングの解析, 九州大学工学部卒業論文, 26 年 2 月 63 で

64 [Donoho, Javanmard, Montanari 3] のシミュレーションの追試 2 [ 大浦 6] 64

65 実験 3( 波多江ら ): 空間結合系 SS 符号の復号 ( 復元不可能 ) 実験 2 の設定において帯の幅を変えずにシェイプマトリックスを大きくしたデザインマトリックスのサイズは 55*5 から 75*7 へとしたブロックの符号長 2 ブロックのベクトル次元符号長 575 ベクトルの次元 7 セクションサイズ圧縮率.2 信号密度. SN 比 8 伝送速度.4537C 伝送速度.745C < 空間結合系の実験設定 > /2 /2 /3 /3 /3 /4 /4 /4 /4 /5 /5 /5 /5 /5 /5 /6 /6 /6 /6 /6 /6 /6 /6 /6 /6 /6 /6 /6 /6 O O < デザインマトリックスの構造 > /3 /3 /3 /2 /2 65

66 power allocation AMP 復号器の理論保証 [Rush & Venkataramanan 7] AMP 反復式誤り確率の上界 66

67 ベイズ最適 AMP 復号器のシミュレーション [Rush, Greig, Venkataramanan 7] power allocation with Bayes 最適 AMP, ただし, 辞書はアダマール行列 v = 5 C = 2 n = 6582 for R =.6C, n = 52 for R =.9C 67

68 ベイズ最適 AMP の最新のシミュレーション ( 波多江ら ) n =35, L =, M =3, N =3, v =, R =.8C power allocation あり : ビット誤り率平均 7% 程度 68

69 ベルヌーイ辞書を用いたスパース重ね合わせ符号 [Takeishi, Kawakita, and Takeuchi 2] [Takeishi & Takeuchi 6] [] Y. Takeishi, M. Kawakita, and J. Takeuchi, "Least squares superposition codes with Bernoulli dictionary are still reliable at Rates up to Capacity," IEEE Trans. Inform._ Theory, vol. 6, no. 5, pp , May 24. [2] Y. Takeishi and J. Takeuchi, "An improved upper bound on block error probability of least squares superposition codes with unbiased Bernoulli dictionary," Proc. of 26 IEEE Intl. Symp. on Inform. Theory, pp , Barcelona, Spain, July 5,

70 Barron and Joseph による予想 (2) ベルヌーイ辞書を用いた場合でも通信路容量を達成できるベルヌーイ辞書 : で生成この場合も, 符号語の平均電力制約は満たされる符号語は各次元独立に, にしたがう分布に近づく ( 中心極限定理 ) 本研究ではこの予想を確かめた 7

71 定理 ( ベルヌーイ辞書のときの最尤復号 ) は各要素独立に確率 /2で, 確率 /2でとして生成する. とし, セクションサイズ率はある条件を満たすものとする. このとき, に対して, が成り立つ. ただし, である. 7

72 補題 7( 簡略版 )[Takeishi, Kawakita, Takeuchi 4] 以上の任意の自然数に対して, が成り立つ. 72

73 まとめ適応的逐次復号器は速いが,.4C 程度が限界 Bayes 法で.5C 程度までいくが遅くなる符号長程度では, レートドロップは大きい /(log n) なので, かなり問題. ベイズ最適 AMPでは,n = 4くらいで復号可能. 空間結合は使えない可能性が高い Bernoulli 辞書にしてもシミュレーションでの性能はほとんど変わらない. 73

スライド 1

スライド 1 1 非対称通信路の通信路容量を達成する符号化法に関する最近の進展東京大学大学院新領域創成科学研究科複雑理工学専攻講師本多淳也情報理論研究会 2018/5/18 概要 2 非対称通信路の符号化 polar 符号を用いる方式無歪み圧縮を用いた符号化法の一般的な枠組み Miyake-Muramatsuの方式連鎖構造に基づく方式無歪み圧縮の逆操作について通信路符号化 3 ノイズを含む通信路を用いて情報を伝送したい