• 検索結果がありません。

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

N/A
N/A
Protected

Academic year: 2021

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

Copied!
73
0
0

読み込み中.... (全文を見る)

全文

(1)

スパース重ね合わせ符号の

状況と課題

竹内純一

三村和史

† † †

九州大学 大学院システム情報科学研究院

† †

広島市立大学 大学院情報科学研究科

2017/11/28  若手研究者のための講演会 at 新潟県月岡温泉

Thanks to: 川喜田雅則,高木美里,武石啓成,波多江優和,宮本耕平

Special thanks to: 竹内啓悟

(2)

スパース重ね合わせ符号

(Sparse superposition codes; SS符号) 

[Barron and Joseph 2010] (ISIT2010)

• ガウス通信路に直接適用される誤り訂正符号

→ 符号語が0,1ではなく実数値をとる

• 符号語は辞書の列ベクトルのスパースな線形結合に

より構成

• AWGN通信路容量を達成する

‐0.70 ‐0.47  0.99

0.69 ‐0.04  1.61

0.11  0.13 ‐1.12

辞書の例

(3)

通信路容量を達成する符号

• 1993年:ターボ符号

[Berrou ら]

• 2009年:Polar符号

[Arikan] (離散入力通信路)

• 2011年:空間結合LDPC符号

[Kudekar et al.] 

• 2014年:

スパース重ね合わせ符号

[Joseph & Barron]

通信路容量

に近い伝送レート

を達成し,かつ

効率的に符号化・復号が行える符号をつくりたい

 AWGN通信路容量を達成

 従来と比べて格段に高い伝送レートを達成

(4)

SS符号のブロック誤り確率の上界

通信路容量

C, レート R, 符号長 n,

平均誤り確率

p

e

• 最尤復号のとき [Joseph and Barron 12(10)]

(5)

ガウス通信路を用いた通信

• 目標:

ガウス

通信路

符号語

符号化

復号

受信語

伝送レート:

通信路容量:

メッセージ

復号結果

送信側

受信側

メッセージ

:一様分布

(6)

平均パワー制約

• 符号語の平均電力制限:

は各次元独立に,

にしたがう

(平均

,分散

の正規分布)

ガウス

通信路

符号語

受信語

(7)

ガウス通信路の通信路容量

• 平均電力制限

のもとでの通信路容量

• 通信路符号化定理[Shannon 1948]によると,

これを達成するのは,符号語

c が各次元独立に

にしたがうとき

(8)

スパース重ね合わせ符号

0

1

1

0

1

0

0

0

0

0

1

0

0

0

0

1

0

1

1

の数はちょうど 個

( スパース)

辞書

1対1写像

0

0

0

0

1

0

0

0

0

1

0

1

(9)

符号化

0

1

1

0

1

0

0

0

0

0

1

0

0

0

0

1

0

1

1

の数はちょうど 個

( スパース)

辞書

1対1写像

0

0

0

0

1

0

0

0

0

1

0

1

(10)

分割重ね合わせ符号

0

1

1

0

1

0

0

0

0

0

1

0

0

0

0

1

0

1

個の

セクション

に分ける

辞書

0

1

0

0

0

0

1

0

0

0

1

0

こちらの方が符号化の設計が簡単

→ 今後はこれを前提として議論

(11)

各パラメータの関係

• 全てのメッセージの数と

全ての符号語の数は等しいので

• 伝送レート

より

の決め方に自由度がある

→  は1から

まで取り得る

0

1

1

0

1

0

0

0

0

0

1

0

0

0

0

1

0

1

(12)

:セクションサイズ率)

セクションサイズ率

a

• セクションサイズ

と分割数

の関係

• 辞書サイズ

:セクションサイズ率)

0

0

0

0

1

0

0

0

0

1

0

1

を大きくすると

はスパースになる

性能を保証するためには, がある

程度大きくなければならない

(13)

辞書

Xの作り方

• 各要素それぞれ独立に

で生成

• ただし,現実のデバイスで厳密に正規乱数を実装

することはできない

 これにより,符号語の平均電力制約が満たされる

 符号語は各次元独立に,

にしたがう

→ これはガウス通信路の通信路容量を達成する

分布である

‐0.70 ‐0.47  0.99

0.69 ‐0.04  1.61

0.11  0.13 ‐1.12

 乱数値がバウンドされない

 乱数値の表現に無限の精度が必要

(14)

復号

→ 受信語

と辞書

が与えられたもとでスパースな

ベクトル

を推定

• 最小二乗復号(計算量無視)と効率的復号アルゴリ

ズムについて後に紹介

 圧縮センシングと同様の枠組み

 CDMA通信との類似性

(15)

復号アルゴリズム

• 最尤復号 [Barron & Joseph 10, Joseph & Barron 12]

• 誤り確率 O(exp(- (C-R)

2

n))

• 適応的逐次復号器[Barron & Joseph 10, Joseph & Barron 14]

• 誤り確率 O(exp(- (C

M

-R)

2

n))

• power allocation

• simple法と直交化付きの二種類

• 受信語と辞書列の相関が閾値を超えたものを逐次復号

• ベイズ最適適応的逐次復号器[Barron & Cho 12]

• 各列の事後確率を反復計算で求め,最後にMAP推定

• ベイズ最適AMP [Barbier et al 14], [Rush & Venkataramanan 15]

• 空間結合 vs power allocation

(16)

復号誤りの定義

:真の

:復号結果

• ブロック誤り:

: 誤って復号されたセク

ションの数

• セクション誤り率

0

1

0

0

0

0

0

1

0

0

0

1

0

1

0

0

0

0

0

1

0

0

0

1

→ 実はスパース重ね合わせ符号単体では

高い確率で

が小さいことしか言えない

(17)

RS符号との組み合わせ

• リード・ソロモン符号(RS符号)

[Reed and Solomon 1960]

を外符号(outer code)として組み合わせて用いる

• 小さいブロック誤りの確率を実現

符号化

(RS符号)

復号

(RS符号)

符号化

(重ね合わせ

符号)

復号

(重ね合わせ

符号)

inner code

通信路

(18)

最小二乗復号の誤り確率

[Joseph & Barron 2012]

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. 2541‐2557, May 2012.

(19)

最小二乗復号

• 最小二乗復号:

• 最尤復号の意味で最適だが,計算量的に困難

再構成)

(20)

:セクションサイズ率)

セクションサイズ率

a

• セクションサイズ

と分割数

の関係

• 辞書サイズ

:セクションサイズ率)

0

0

0

0

1

0

0

0

0

1

0

1

を大きくすると

はスパースになる

性能を保証するためには, がある

程度大きくなければならない

(21)

定理1

[Joseph and Barron 2012]

は各要素独立に

から生成する.

とし,セクションサイズ率

を満たすものと

する

.このとき,

に対して,

が成り立つ.ただし,

である.

注意:確率変数は,ノイズ

だけでなく,辞書

も含めて

考えている

(22)

a

v

のグラフ (L = 64)

(23)

効率的復号アルゴリズム

[Barron & Joseph 10][Joseph & Barron 14]

[1] 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  13‐18, 2010, pp. 315‐319. [2] A. Joseph and A. R. Barron, “Fast Sparse Superposition Codes Have Near  Exponential Error Probability for R < C,”  IEEE trans. IT, Feb 2014.

(24)

効率的復号アルゴリズム

• OMP (Orthogonal Matching Pursuit)に似た繰り返し

アルゴリズム

で動く(並列処理必要)

→ ただし外符号のリード・ソロモン符号の計算に多項式

時間くらいかかる

(25)

power allocation

の各成分を可変に)

0

1

1

0

1

0

個の

セクション

に分ける

辞書

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

(26)

の作り方

• 各要素それぞれ独立に

で生成

が満たされるようにする

とするのが最も簡単

→ 平均電力制約を満たすため

→ しかしこれでは通信路容量を達成できない

(27)

電力割り当て

P

(l)

:Capacity

:小さい正定数

より少しだけ大きい

が1に近いところでは,

は一定になる

→②の方が少し性能が良くなる

(28)

の最適値は約

Step 1

とする

に対して,

となる があ

れば,それを復号結果とする

• 出力

:このステップで復号された の集合

(SN比が小さく

ないとき)

(29)

Step 2

に対して,

となる があ

れば,それを復号結果とする

• 出力

:このステップで復号された の集合

(30)

Step k

に対して,

となる があ

れば,それを復号結果とする

• 出力

:このステップで復号された の集合

(31)

終了条件

• 復号された の数が

になったとき

(32)

直交化付きアルゴリズム

(33)

Step 1 (前と同じ)

とする

を計算

となる があれば,それを復号結果とする

• 出力

:このステップで復号された の集合

(34)

Step 2

に対する直交成分

を計算

を計算

となる があれば,それを復号結果とする

• 出力

:このステップで復号された の集合

(35)

Step

,

に対する直交成分

を計算

を計算

となる があれば,それを復号結果とする

• 出力

:このステップで復号された の集合

(36)

直交成分の作り方

• シュミットの直交化法により行う

(37)
(38)

の作り方の変更

:step    において閾値を超えた の集合

に入れていく

を超えないよう

な制限の元で,できるだけ多く入れる

は指定しておく

(1にすると

となる)

38

(39)

終了条件

• 復号された の数が

になったとき

• 閾値を超える が一つもなかったとき

(40)

指定すべきパラメータ

① 電力割り当て

② 復号のペース制限

を構成するため

(41)

update function

ただし,

は標準正規分布の上側確

• 辞書のサイズと通信路(

),閾値を設定すると

決まる

(42)

g

L

(x) によるペースの観察

(43)

の設定

を用意

で設定

のとき→

のとき→

(44)

ベイズ最適適応的逐次復号

[Barron and Cho 12]

• 初期ステップ

• 各列

1,2, … ,

と各セクション

1,2, … , に対して以下を計

, ,

‖ ‖

, , , ,

, , ∈ , , Barron and Cho, ``High‐rate sparse superposition codes with iteratively optimal  estimates." Proc. of IEEE Intl. Symp. on Inform. Theory. Cambridge, MA, July 2012,  pp. 120‐124.

(45)

ベイズ型アルゴリズム(続き)

• 第 ステップ

• 以下を計算

, , , , ∑ , , ∈ , ,

• 規定の回数反復した後,最終的な

から台を求めて

終了(MAP)

(46)

ベイズ型アルゴリズムの特徴

,

が第 ステップの時点で

列が正しい列であるという事

後確率

, ,

で各成分対応する列の事後確率

で決まる

• ステップが進むにつれ

が に近づく

の期待値は第 ステップの時点で正しく推定でき

るセクション数の割合の期待値と一致するLemma2, 

[Barron and Cho 2012]

⇒ AMP の t状態発展式の役割に類似.

(47)
(48)

実験

• 各アルゴリズムによる復号を行ってセクション誤り率

をみ

:誤って復号されたセクション数

(49)

復号実験パラメータ

• snr=7

• レート R = 0.3C, 0.4C, 0.5C.

• 各アルゴリズムで各設定100回ずつ実験

• ビット誤り率 < q となる回数を計測 (q=0.1~0.5)

• 使用環境

• R on Linux, Intel(R) Xeon(R) CPU E5-2690 0 @

2.90GHz

• 逐次復号アルゴリズムについて

• 閾値

2log

0.1

(50)

達成可能レート

宮本らによる実験で,Joseph & Barron アルゴリズムで R = 0.4C, 

ベイズ最適化で,R = 0.5C 程度

(51)

考察

at ISIT2012 (Boston)

• LDPC符号

• MAP復号で C 達成

• BPによる効率的復号では C までギャップ

• 空間結合で効率的復号でC達成.

• 圧縮センシング(Bayes最適AMP)

• L0再構成で情報理論的限界達成

• L1再構成は性能のギャップあり.

• 空間結合でL0と同等の性能 [Donoho et al. 2013]

• スパース重ねあわせ符号

• 最尤復号で C 達成

• 効率的復号では大きなレートドロップ

LDPC符号と圧縮センシングの状況から類推して,

空間結合でレートドロップを改善できないか?

(52)

次元ベクトル

,観測行列(

,

A によって

次元ベクトル

が次のように与えられているとする。

問題設定

⋯ ⋮ ⋱ ⋮ ⋯

A~N 0,

(

‐)スパースなベクトル

圧縮センシングとは(1/2)

圧縮率 信号密度 [5]田中利幸, ``圧縮センシングの数理,'' IEICE Fundamentals Review, Vol.4, No.1, pp.39‐ 47,2010年.

圧縮センシングでは非零要素の位置が未知である場合の復元をどの程

度まで

が小さい範囲で行えるかを問題とする

(53)

圧縮センシングとは(2/2)

(計算困難) (効率的) 再構成: arg min | | . . 再構成: arg min | | . .

右に示す3種類のノルムを用いる

• また,各要素が

N 0, σ に従うノイズ

W

があると

(計算困難) (効率的) 再構成: arg min | | . . | | 再構成: arg min | | . . | | ノルム: ノルム: ノルム: ⇔ arg min λ (ラグランジュ未定乗数法による) ノイズなし ノイズあり (ユークリッドノルム) で復元可能 (弱しきい値) で復元可能

(54)

 再構成のアルゴリズムの1つで理論的によいとされている 条件(残差のノルムが一定値以下,反復回数が一定回数以 上等)を満たすまで次の反復式を用いて未知ベクトルを推定

圧縮センシングの再構成アルゴリズム

Approximate  Message Passing (AMP) , λ 1 · η’ , λ ( :反復回数) [5]田中利幸, ``圧縮センシングの数理,'' IEICE Fundamentals Review, Vol.4, No.1,  pp.39‐47,2010年. , λ 1 · η’ , λ ( :反復回数)

(55)

空間結合圧縮センシング

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

(56)

空間結合圧縮センシングのアイデア

もし,

, , が

推定できたとすると…

連鎖的に他の要素も決定する.

(57)

観測行列 は行列

によって決まる.

空間結合圧縮センシングの再構成アルゴリズム

AMP

Bayes  Optimal AMP Bayes  Optimal AMP :観測行列Aの要素のインデックスを, 対応する ブロックのインデックス に写す関数 ⊙ はアダマール積を表す

未知ベクトル

について事前分布を既知としている

[1] Donoho, Javanmard, and Montanari, "Information‐theoretically optimal compressed sensing via spatial coupling and approximate  message passing," IEEE transactions on information theory 59.11 (2013): 7434‐7464. Bernoulli‐Gussian事前分布 の場合

(58)

スパース重ね合わせ符号における空間結合

[Barbier et al. 14]

 はΓ Γのブロックに分けられる.インデックスを , とし,各ブロックを , とする. 即ち, /Γ列,  /Γ行となる.ここで /Γ , /Γ とする.  帯の幅を決定する ,行列 の要素の値を決定する関数 を導入. 0 1 0  とすると.∀ において, は ∑ , 1 と正規化し, , の各要素は N 0, , に従う , ≔ Γ   2 1

シェイプマトリックス

, [2] Barbier, Dia, and Macris, "Proof of Threshold Saturation for Spatially Coupled Sparse Superposition Codes,"  arXiv preprint arXiv:1603.01817 (2016): 7434‐7464.

(59)

Replica解析: AMP vs 適応的逐次復号

[Barbier & Krzakala 2014]

(60)

空間結合AMP復号器の大極限理論保証

[Barbier,  Dia, & Macris 16]

lim →  定理6.2 孤立系理論限界と空間結合系AMP閾値の関係 シェイプマトリックスが非常に大きいとき…

孤立系 理論限界

通信路符号化定理 :

C

セクション サイズが大 セクション サイズが大

通信路容量達成 通信路容量 達成

Barbier, Mohamad, & Macris, "Proof of Threshold Saturation for Spatially Coupled 

Sparse Superposition Codes,"  arXiv preprint arXiv:1603.01817 (2016): 7434‐7464.

(61)

実験1(波多江ら):

孤立系SS符号の復号 (反復11回で復元)

 信号密度 0.1のときの孤立系AMPの限界 0.2385 であること がわかっている.具体的な値は下表に示す. 符号長 1750 ベクトル の次元 5000 セクションサイズ 10 圧縮率 0.35 信号密度 0.1 SN比 5 伝送速度 0.7343C <孤立系の実験設定>

(62)

実験2(波多江ら):

空間結合系SS符号の復号 (反復63回で復元成功)

 シェイプマトリックスを無限に大きくしたときの伝送速度 を とする  シェイプマトリックスのサイズは55*50,帯の幅は6とした 1ブロックの符号長 21 1ブロックのベクトル 次元 100 符号長 1155 ベクトル の次元 5000 セクションサイズ 10 圧縮率 0.21 信号密度 0.1 SN比 80 伝送速度 0.4537C 伝送速度 0.7045C 1 1/2 1/2 1/3 1/3 1/3 1/4 1/4 1/4 1/4 1/5 1/5 1/5 1/5 1/5 1/5 1/6 1/6 1/6 1/6 1/6 1/6 1/6 1/6 1/6 1/6 1/6 1/6 1/6 1/6 1/3 1/3 1/3 1/2 1/2 1 ・・・

<空間結合系の実験設定> <デザインマトリックスの構造>

(63)

[Donoho, Javanmard, Montanari 13]の

シミュレーションの追試1 [大浦 16]

(64)

[Donoho, Javanmard, Montanari 13]

のシミュレーションの追試2 [大浦 16]

(65)

実験3(波多江ら):

空間結合系SS符号の復号(復元不可能)

 実験2の設定において帯の幅を変えずにシェイプマトリックスを大きくした  デザインマトリックスのサイズは55*50から75*70へとした 1 1/2 1/2 1/3 1/3 1/3 1/4 1/4 1/4 1/4 1/5 1/5 1/5 1/5 1/5 1/5 1/6 1/6 1/6 1/6 1/6 1/6 1/6 1/6 1/6 1/6 1/6 1/6 1/6 1/6 1/3 1/3 1/3 1/2 1/2 1 ・・・

<空間結合系の実験設定> <デザインマトリックスの構造> 1ブロックの符号長 21 1ブロックのベクトル 次元 100 符号長 1575 ベクトル の次元 7000 セクションサイズ 10 圧縮率 0.21 信号密度 0.1 SN比 80 伝送速度 0.4537C 伝送速度 0.7045C

(66)

power allocation AMP復号器の理論保証

[Rush & Venkataramanan 17]

AMP反復式

(67)

ベイズ最適AMP復号器のシミュレーション

[Rush, Greig, Venkataramanan 17]

power allocation with Bayes最適AMP,ただし,辞書はアダマール行列

v = 15

C = 2

(68)

ベイズ最適AMPの

最新のシミュレーション(波多江ら)

• n =351, L = 100, M =30, N =3000, v =10, R = 0.8C

(69)

ベルヌーイ辞書を用いた

スパース重ね合わせ符号

[Takeishi, Kawakita, and Takeuchi 12]

[Takeishi & Takeuchi 16]

[1] 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.  60, no. 5, pp. 2737‐2750, May 2014. [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 2016 IEEE Intl.  Symp. on Inform. Theory, pp. 1168 ‐ 1172, Barcelona, Spain, July 10‐15, 2016.

(70)

Barron and Joseph による予想

(2010)

• ベルヌーイ辞書を用いた場合でも通信路容量を達

成できる

 この場合も,符号語の平均電力制約は満たされる

 符号語は各次元独立に,

にしたがう分布に

近づく(中心極限定理)

ベルヌーイ辞書:

で生成

本研究ではこの予想を確かめた

‐1      ‐1       1

1      ‐1       1

1       1      ‐1

(71)

定理(ベルヌーイ辞書のときの最尤復号)

は各要素独立に確率1/2で

,確率1/2で

として生成する.

とし,セクションサイズ率

はある条件を満た

すものとする.このとき,

に対して,

が成り立つ.ただし,

である.

(72)

補題7(簡略版) [Takeishi, Kawakita, 

Takeuchi 14]

1000以上の任意の自然数 に対して,

(73)

まとめ

• 適応的逐次復号器は速いが,0.4C程度が限界

• Bayes法で0.5C程度までいくが遅くなる

• 符号長1000程度では,レートドロップは大きい

→ 1/(log n)なので,かなり問題.

• ベイズ最適AMPでは,n = 400くらいで復号可能.

• 空間結合は使えない可能性が高い

• Bernoulli辞書にしてもシミュレーションでの性能はほ

とんど変わらない.

参照

関連したドキュメント

[r]

私たちの行動には 5W1H

CIとDIは共通の指標を採用しており、採用系列数は先行指数 11、一致指数 10、遅行指数9 の 30 系列である(2017

[r]

[r]

[r]

都内の観測井の配置図を図-4に示す。平成21年現在、42地点91観測 井において地下水位の観測を行っている。水準測量 ※5

授業は行っていません。このため、井口担当の 3 年生の研究演習は、2022 年度春学期に 2 コマ行います。また、井口担当の 4 年生の研究演習は、 2023 年秋学期に 2