ERATO感謝祭 Season IV

特徴選択のためのLasso解列挙（AAAI’17）
原 聡1,2、前原 貴憲31) 国⽴情報学研究所
2) JST, ERATO, 河原林巨⼤グラフプロジェクト
3) 理研AIP

1

研究背景

2

研究背景：特徴選択は完璧か？
n『特徴選択を使うと、タスクに関連する特徴量と、タスクに関連しない特徴量とを識別することができる』と⾔われている。
Lassoを使うとモデルのスパースな表現が得られる。
• Lassoによって選ばれた特徴量が重要な特徴量だと⾔われている。
•3

研究背景：特徴選択は完璧か？
n『特徴選択を使うと、タスクに関連する特徴量と、タスクに関連しない特徴量とを識別することができる』と⾔われている。
Lassoを使うとモデルのスパースな表現が得られる。
• Lassoによって選ばれた特徴量が重要な特徴量だと⾔われている。
•n

しかし、機械学習に完璧はありえない。
有限のデータから学習する以上、ある程度のエラーは起こりうる。
• データ由来・学習⼿法由来のバイアスがのることがある。
•4

研究背景：特徴選択は完璧か？
n『特徴選択を使うと、タスクに関連する特徴量と、タスクに関連しない特徴量とを識別することができる』と⾔われている。
Lassoを使うとモデルのスパースな表現が得られる。
• Lassoによって選ばれた特徴量が重要な特徴量だと⾔われている。
•n

しかし、機械学習に完璧はありえない。
有限のデータから学習する以上、ある程度のエラーは起こりうる。
• データ由来・学習⼿法由来のバイアスがのることがある。
•

機械学習は時として間違える。
機械学習がミスすると。。。

5

研究背景：機械学習がミスすると。。。
Xという病気には「体重」と「⾎圧」が関連するはず！

専⾨家

6

研究背景：機械学習がミスすると。。。
Xという病気には「体重」と「⾎圧」が関連するはず！

Xという病気に関連する項⽬は「⾝⻑」と「⾎圧」です！

!?
専⾨家

機械学習モデル7

研究背景：機械学習がミスすると。。。
Xという病気には「体重」と「⾎圧」が関連するはず！

Xという病気に関連する項⽬は「⾝⻑」と「⾎圧」です！

!?
専⾨家

n

機械学習モデル

理想的には⾃分の理解が間違っていたかも。調べ直そう。

8

研究背景：機械学習がミスすると。。。
Xという病気には「体重」と「⾎圧」が関連するはず！

Xという病気に関連する項⽬は「⾝⻑」と「⾎圧」です！

!?
専⾨家

n

機械学習モデル

最悪の場合はこのモデルは間違っている！
こんなモデル使えるか！!

9

研究背景：機械学習がミスすると。。。
Xという病気には「体重」と「⾎圧」が関連するはず！

Xという病気に関連する項⽬は「⾝⻑」と「⾎圧」です！

!?
専⾨家

n

機械学習モデル

最悪の場合はこのモデルは間違っている！
こんなモデル使えるか！!

悲劇
たとえ精度の⾼いモデルでも、ユーザの信頼が得られないと使われない。

10

研究背景：ユーザに信頼される特徴選択をしたい。
n

しかし、“間違えない特徴選択”は難しい。
•Lassoは選ばれた特徴量が“真に重要な特徴量”であることが保証されない。
- Adaptive Lassoをはじめ、様々な改善法が考案されている。
- しかし、有限のデータから学習している以上、エラーは避けられない。

11

研究背景：ユーザに信頼される特徴選択をしたい。
n

しかし、“間違えない特徴選択”は難しい。
•Lassoは選ばれた特徴量が“真に重要な特徴量”であることが保証されない。
- Adaptive Lassoをはじめ、様々な改善法が考案されている。
- しかし、有限のデータから学習している以上、エラーは避けられない。

n

本研究のアイディア•

そもそも“重要な特徴量の組”を⼀つ探そうとしているから難しい。

12

研究背景：ユーザに信頼される特徴選択をしたい。
n

しかし、“間違えない特徴選択”は難しい。
•Lassoは選ばれた特徴量が“真に重要な特徴量”であることが保証されない。
- Adaptive Lassoをはじめ、様々な改善法が考案されている。
- しかし、有限のデータから学習している以上、エラーは避けられない。

n

本研究のアイディア
そもそも“重要な特徴量の組”を⼀つ探そうとしているから難しい。
• “重要な特徴量の組”をたくさん⾒つけて、それをユーザに提⽰したらどうか？
→ 「Lasso解を複数列挙する問題」を考える。
•13

研究背景：ユーザに信頼される特徴選択をしたい。
n

しかし、“間違えない特徴選択”は難しい。
•Lassoは選ばれた特徴量が“真に重要な特徴量”であることが保証されない。
- Adaptive Lassoをはじめ、様々な改善法が考案されている。
- しかし、有限のデータから学習している以上、エラーは避けられない。

n

本研究のアイディア
そもそも“重要な特徴量の組”を⼀つ探そうとしているから難しい。
• “重要な特徴量の組”をたくさん⾒つけて、それをユーザに提⽰したらどうか？
→ 「Lasso解を複数列挙する問題」を考える。
•

Xという病気に関連する項⽬は。。。

14

研究背景：ユーザに信頼される特徴選択をしたい。
n

しかし、“間違えない特徴選択”は難しい。
•Lassoは選ばれた特徴量が“真に重要な特徴量”であることが保証されない。
- Adaptive Lassoをはじめ、様々な改善法が考案されている。
- しかし、有限のデータから学習している以上、エラーは避けられない。

n

本研究のアイディア
そもそも“重要な特徴量の組”を⼀つ探そうとしているから難しい。
• “重要な特徴量の組”をたくさん⾒つけて、それをユーザに提⽰したらどうか？
→ 「Lasso解を複数列挙する問題」を考える。
•う〜ん？
「⾝⻑」と「⾎圧」

Xという病気に関連する項⽬は。。。

15

研究背景：ユーザに信頼される特徴選択をしたい。
n

しかし、“間違えない特徴選択”は難しい。
•Lassoは選ばれた特徴量が“真に重要な特徴量”であることが保証されない。
- Adaptive Lassoをはじめ、様々な改善法が考案されている。
- しかし、有限のデータから学習している以上、エラーは避けられない。

n

本研究のアイディア
そもそも“重要な特徴量の組”を⼀つ探そうとしているから難しい。
• “重要な特徴量の組”をたくさん⾒つけて、それをユーザに提⽰したらどうか？
→ 「Lasso解を複数列挙する問題」を考える。
•う〜ん？
う〜ん？

「⾝⻑」と「⾎圧」「体重」と「⾎糖値」

Xという病気に関連する項⽬は。。。

16

研究背景：ユーザに信頼される特徴選択をしたい。
n

しかし、“間違えない特徴選択”は難しい。
•Lassoは選ばれた特徴量が“真に重要な特徴量”であることが保証されない。
- Adaptive Lassoをはじめ、様々な改善法が考案されている。
- しかし、有限のデータから学習している以上、エラーは避けられない。

n

本研究のアイディア
そもそも“重要な特徴量の組”を⼀つ探そうとしているから難しい。
• “重要な特徴量の組”をたくさん⾒つけて、それをユーザに提⽰したらどうか？
→ 「Lasso解を複数列挙する問題」を考える。
•う〜ん？
う〜ん？
これだ！！

Xという病気に関連「⾝⻑」と「⾎圧」「体重」と「⾎糖 する項⽬は。。。
「体重」と「⾎圧」
値」

17

Lasso18Lassoによる特徴選択
スパース線形回帰問題

Given: ⼊出⼒のペア 𝑥" , 𝑦" ∈ ℝ' ×ℝ 𝑖 = 1, 2, … , 𝑁
Find: 回帰係数𝛽 ∈ ℝ' s.t. 𝑥"1 𝛽 ≈ 𝑦 (𝑖 = 1, 2, … , 𝑁)
ただし、𝛽は⾮ゼロ要素が少ない（スパース）

nスパース性•

物理的要請- ⼤量の特徴量のうち、効く特徴量は少ないはずという直感。

•解釈性向上- 解から意味のある特徴量を⾒出したい。変数の絞込み。

解法：Lasso回帰（ ℓ6 正則化）𝛽 ∗ = argmin>•1
𝑋𝛽 − 𝑦 A + 𝜌 𝛽 62

Lasso解𝛽 ∗ はスパース。supp(𝛽 ∗ ) = {𝑖 ∶ 𝛽"∗ ≠ 0}が重要な特徴量。
19

Lassoの理論的正当性：復元定理
6∗
Lasso解：𝛽 = argmin
A>𝑋𝛽 − 𝑦 A + 𝜌 𝛽 6

適当な設定の元で、Lasso解𝛽∗ は真のパラメータ𝛽L のサポート（⾮零要素）を⾼い確率で復元する。
n仮定
真のモデルが𝑦 = 𝑋𝛽 L + 𝑤; 𝛽 L はスパース, 𝑤 ∼ 𝑁(0, 𝜎 A )• 正則化パラメータ𝜌は⼗分⼩さい。
• 𝑋の各⾏は⼗分独⽴（⾼相関な特徴量はない）。
•n

上記仮定の元で、⾼い確率で真のパラメータ𝛽L のサポートが復元できる。
supp(𝛽∗ ) = supp(𝛽L )20

Lassoの限界：重要な特徴量を見落とす。
n⾼次元データでは、類似した特徴量が存在することが多い。
類似特徴量のうち、どれを使っても同等の予測精度のモデルが作れる。
• 「𝑋の各⾏は⼗分独⽴（⾼相関な特徴量はない）」という仮定が成⽴しない場合に相当。
•→このような場合、Lassoは類似特徴量の⼀部だけを使い残りを無視する。
nLassoの限界：類似特徴量の中の重要な特徴量を⾒落とす。
例えば、「⾝⻑」と「体重」のような相関の⾼い特徴量のうち、⽚⽅（例えば「⾝⻑」）だけを使ったモデルを出⼒する。
→「体重」を⾒落とす。「体重」を使ったモデルを期待するユーザとの間に齟齬が起きる。
•n

本研究：「⾝⻑」、「体重」それぞれを使ったモデルを両⽅出⼒する。
21

本研究の成果：Lasso解の列挙
成果1：アルゴリズム
Lassoの解を⽬的関数値の昇順にサポートを列挙するアルゴリズム。
列挙した解からユーザに気に⼊った解を選んでもらう。

成果2：列挙版の復元定理
正則化パラメータ𝜌が⼗分⼩さければ、適当な個数だけ解を列挙すれば真のパラメータ𝛽 L のサポートを復元するものが⾒つかる。
- どれがサポート復元するかは特定不能（なんらかの別基準が必要）。
- 何個列挙すればいいかは問題依存（傾向は理論的にわかる）。

副次的な成果Lassoで得られた特徴量を安易に信頼するのは危険。
実データで、実際に同等な解が無数に存在することを確認。

22

問題の定式化と提案法

23

問題の定式化：Lasso解の列挙
n解のサポートを𝑆 ⊆ {𝑥6 , 𝑥A , … , 𝑥' }に制限したLasso：
Lasso 𝑆

6= min> A

𝑋𝛽 − 𝑦 A + 𝜌 𝛽 6 s.t. supp 𝛽 ⊆ 𝑆

最適解での⽬的関数値をLasso 𝑆 とする。

問題：Lasso解の列挙
Lasso 𝑆 の⼩さい順に極⼩の𝑆を𝑘個列挙する。
（極⼩：supp 𝛽 = 𝑆となるもの。それ以外は冗⻑。）【注意】正則化パスに基づいた解の列挙ではない。
• 正則化パスでは疎な解から密な解へと𝜌を変化させた時の解を列挙する。
• 本問題では𝜌固定の元で、⽬的関数値が昇順になるように解のサポートを列挙する。
•𝑥6 , 𝑥A , 𝑥V , 𝑥6 , 𝑥A , 𝑥W , 𝑥6 , 𝑥W , 𝑥X , 𝑥6 , 𝑥A , …

24

アルゴリズム：『Lawlerの𝒌-best列挙』
アルゴリズム概略1. サポート𝑆を⼊⼒して、特徴量の集合𝑇が出⼒されたとする。
2. 全ての𝑡 ∈ 𝑇について𝑆からを𝑡を取り除いた𝑆 \ = 𝑆 ∖ {𝑡}を作る 。
Lasso(𝑆′)の解𝑇′を得る。
(𝑇 \ , 𝑆′)を解の候補としてヒープに保持する。

3. 保持している解の候補のうち、⽬的関数値が最⼩のものを出⼒する。
4. 以上、繰り返し。

25

アルゴリズム：『Lawlerの𝒌-best列挙』
アルゴリズム概略
1. サポート𝑺を入力して、特徴量の集合𝑻が出力されたとする。
2. 全ての𝑡 ∈ 𝑇について
𝑆からを𝑡を取り除いた𝑆 \ = 𝑆 ∖ {𝑡}を作る 。
Lasso(𝑆′)の解𝑇′を得る。
(𝑇 \ , 𝑆′)を解の候補としてヒープに保持する。

3. 保持している解の候補のうち、⽬的関数値が最⼩のものを出⼒する。
4. 以上、繰り返し。
𝑆 = 𝑥6 , 𝑥A , 𝑥W , 𝑥V , 𝑥XLasso
ソルバ

解の候補
𝑇 = 𝑥6 , 𝑥A , 𝑥V

出⼒
𝑇6 = 𝑥6 , 𝑥A , 𝑥V
𝑆6 = 𝑥6 , 𝑥A , 𝑥W , 𝑥V , 𝑥X

26

アルゴリズム：『Lawlerの𝒌-best列挙』
アルゴリズム概略
1. サポート𝑆を⼊⼒して、特徴量の集合𝑇が出⼒されたとする。
2. 全ての𝒕 ∈ 𝑻について𝑺からを𝒕を取り除いた𝑺\ = 𝑺 ∖ {𝒕}を作る 。
Lasso(𝑆′)の解𝑇′を得る。
(𝑇 \ , 𝑆′)を解の候補としてヒープに保持する。

3. 保持している解の候補のうち、⽬的関数値が最⼩のものを出⼒する。
4. 以上、繰り返し。
𝑆6 = 𝑥6 , 𝑥A , 𝑥W , 𝑥V , 𝑥X

Lasso
ソルバ

𝑆6\ = 𝑥A , 𝑥W , 𝑥V , 𝑥X

𝑇6 = 𝑥6 , 𝑥A , 𝑥V
𝑆6 = 𝑥6 , 𝑥A , 𝑥W , 𝑥V , 𝑥X

𝑆W\ = 𝑥6 , 𝑥A , 𝑥W , 𝑥X

解の候補

𝑆A\ = 𝑥6 , 𝑥W , 𝑥V , 𝑥X

27

アルゴリズム：『Lawlerの𝒌-best列挙』
アルゴリズム概略
1. サポート𝑆を⼊⼒して、特徴量の集合𝑇が出⼒されたとする。
2. 全ての𝒕 ∈ 𝑻について𝑆からを𝑡を取り除いた𝑆 \ = 𝑆 ∖ {𝑡}を作る 。
𝐋𝐚𝐬𝐬𝐨(𝑺′)の解𝑻′を得る。
(𝑻\ , 𝑺′)を解の候補としてヒープに保持する。

3. 保持している解の候補のうち、⽬的関数値が最⼩のものを出⼒する。
4. 以上、繰り返し。
𝑆6 = 𝑥6 , 𝑥A , 𝑥W , 𝑥V , 𝑥X

Lasso
ソルバ

𝑆6\ = 𝑥A , 𝑥W , 𝑥V , 𝑥X

𝑇6 = 𝑥6 , 𝑥A , 𝑥V
𝑆6 = 𝑥6 , 𝑥A , 𝑥W , 𝑥V , 𝑥X

𝑆W\ = 𝑥6 , 𝑥A , 𝑥W , 𝑥X

𝑆A\ = 𝑥6 , 𝑥W , 𝑥V , 𝑥X

解の候補
(𝑇6\ = 𝑥A , 𝑥V , 𝑥X , 𝑆6\ )28

アルゴリズム：『Lawlerの𝒌-best列挙』
アルゴリズム概略
1. サポート𝑆を⼊⼒して、特徴量の集合𝑇が出⼒されたとする。
2. 全ての𝒕 ∈ 𝑻について𝑆からを𝑡を取り除いた𝑆 \ = 𝑆 ∖ {𝑡}を作る 。
𝐋𝐚𝐬𝐬𝐨(𝑺′)の解𝑻′を得る。
(𝑻\ , 𝑺′)を解の候補としてヒープに保持する。

3. 保持している解の候補のうち、⽬的関数値が最⼩のものを出⼒する。
4. 以上、繰り返し。
𝑆6 = 𝑥6 , 𝑥A , 𝑥W , 𝑥V , 𝑥X

Lasso
ソルバ

𝑆6\ = 𝑥A , 𝑥W , 𝑥V , 𝑥X

𝑇6 = 𝑥6 , 𝑥A , 𝑥V
𝑆6 = 𝑥6 , 𝑥A , 𝑥W , 𝑥V , 𝑥X

𝑆W\ = 𝑥6 , 𝑥A , 𝑥W , 𝑥X

𝑆A\ = 𝑥6 , 𝑥W , 𝑥V , 𝑥X

解の候補
(𝑇6\ = 𝑥A , 𝑥V , 𝑥X , 𝑆6\ )(𝑇A\ = 𝑥6 , 𝑥W , 𝑥V , 𝑆A\ )29

アルゴリズム：『Lawlerの𝒌-best列挙』
アルゴリズム概略
1. サポート𝑆を⼊⼒して、特徴量の集合𝑇が出⼒されたとする。
2. 全ての𝒕 ∈ 𝑻について𝑆からを𝑡を取り除いた𝑆 \ = 𝑆 ∖ {𝑡}を作る 。
𝐋𝐚𝐬𝐬𝐨(𝑺′)の解𝑻′を得る。
(𝑻\ , 𝑺′)を解の候補としてヒープに保持する。

3. 保持している解の候補のうち、⽬的関数値が最⼩のものを出⼒する。
4. 以上、繰り返し。
𝑆6 = 𝑥6 , 𝑥A , 𝑥W , 𝑥V , 𝑥X

Lasso
ソルバ

𝑆6\ = 𝑥A , 𝑥W , 𝑥V , 𝑥X

𝑇6 = 𝑥6 , 𝑥A , 𝑥V
𝑆6 = 𝑥6 , 𝑥A , 𝑥W , 𝑥V , 𝑥X

𝑆W\ = 𝑥6 , 𝑥A , 𝑥W , 𝑥X

𝑆A\ = 𝑥6 , 𝑥W , 𝑥V , 𝑥X

解の候補
(𝑇6\ = 𝑥A , 𝑥V , 𝑥X , 𝑆6\ )(𝑇A\ = 𝑥6 , 𝑥W , 𝑥V , 𝑆A\ )(𝑇W\ = 𝑥6 , 𝑥A , 𝑥X , 𝑆W\ )30

アルゴリズム：『Lawlerの𝒌-best列挙』
アルゴリズム概略
1. サポート𝑆を⼊⼒して、特徴量の集合𝑇が出⼒されたとする。
2. 全ての𝒕 ∈ 𝑻について𝑆からを𝑡を取り除いた𝑆 \ = 𝑆 ∖ {𝑡}を作る 。
𝐋𝐚𝐬𝐬𝐨(𝑺′)の解𝑻′を得る。
(𝑻\ , 𝑺′)を解の候補としてヒープに保持する。

3. 保持している解の候補のうち、⽬的関数値が最⼩のものを出⼒する。
4. 以上、繰り返し。
解の候補

Lasso
ソルバ
𝑇6 = 𝑥6 , 𝑥A , 𝑥V
𝑆6 = 𝑥6 , 𝑥A , 𝑥W , 𝑥V , 𝑥X
𝑇A = 𝑥A , 𝑥V , 𝑥X
𝑆A = 𝑥A , 𝑥W , 𝑥V , 𝑥X

(𝑇6\ = 𝑥A , 𝑥V , 𝑥X , 𝑆6\ )出⼒(𝑇A\ = 𝑥6 , 𝑥W , 𝑥V , 𝑆A\ )(𝑇W\ = 𝑥6 , 𝑥A , 𝑥X , 𝑆W\ )31

アルゴリズム：『Lawlerの𝒌-best列挙』
アルゴリズム概略
1. サポート𝑆を⼊⼒して、特徴量の集合𝑇が出⼒されたとする。
2. 全ての𝒕 ∈ 𝑻について𝑺からを𝒕を取り除いた𝑺\ = 𝑺 ∖ {𝒕}を作る 。
Lasso(𝑆′)の解𝑇′を得る。
(𝑇 \ , 𝑆′)を解の候補としてヒープに保持する。

3. 保持している解の候補のうち、⽬的関数値が最⼩のものを出⼒する。
4. 以上、繰り返し。
𝑆A = 𝑥A , 𝑥W , 𝑥V , 𝑥X

解の候補

Lasso
ソルバ

𝑆V\ = 𝑥W , 𝑥V , 𝑥X
𝑆X\ = 𝑥A , 𝑥W , 𝑥X

𝑇6 = 𝑥6 , 𝑥A , 𝑥V
𝑆6 = 𝑥6 , 𝑥A , 𝑥W , 𝑥V , 𝑥X
𝑇A = 𝑥A , 𝑥V , 𝑥X
𝑆A = 𝑥A , 𝑥W , 𝑥V , 𝑥X

(𝑇A\ = 𝑥6 , 𝑥W , 𝑥V , 𝑆A\ )𝑆f\ = 𝑥A , 𝑥W , 𝑥V

(𝑇W\ = 𝑥6 , 𝑥A , 𝑥X , 𝑆W\ )32

アルゴリズムの妥当性定理
提案法によりLasso 𝑆 の⼩さい順に極⼩の𝑆を列挙できる。
n不要な探索をスキップすることで、提案法を効率化できる。
既に探索した𝑆を重複して探索しないようにする。取り除く変数の履歴を保持する。
• 探索したことのない𝑆 についても、Lassoの最適性条件から解が既に探索済みのものと⼀致することが判定できることがある。
•33

列挙版の復元定理
定理概略
適当な仮定の元で、⼗分たくさん列挙すれば、⾼い確率で列挙した解の中にsupp(𝛽L )が含まれる。
n

適当な仮定・⾼い確率：
正則化パラメータ𝜌は⼗分⼩さい(𝛽L の⾮ゼロ成分を下からバウンド)。
• ノイズが⼩さいほど確率は⾼い。
•n列挙個数について⾔えること：
正則化パラメータ𝜌が⼩さいほど列挙すべき要素が増える。
• 𝑋の独⽴性が低い（⾼相関の特徴量が多い）ほど列挙すべき要素が増える。
•34

実験結果

35

実験1. シロイズナの開花
nThaliana gene expression data (Atwell et al. ’10):
どの遺伝⼦が開花に効くかを知りたい。
• 𝑥 ∈ ℝA6f6Wg ：遺伝⼦各パターンが⽣起しているかどうか（2 値）• 𝑦 ∈ ℝ：発現量• データ数（個体数）：134
50個列挙しても、⽬的関数値は0.05%しか増加しなかった。

解のサポートのサイズは⼤体40~45くらい。

⼤域解が6個あった。
⼤域解が複数ある = 単純にLassoを適⽤すると、6個のうちの1つが⾒つかるだけ。他の特徴量は⾒落とす。

36

実験2. ニュース記事の分類
n20 Newsgroups Data (Lang’95); ibm vs mac
ニュース記事を⼆つのカテゴリに分類するのに特徴的な単語を知りたい。
• 𝑥 ∈ ℝ66fVh ：単語の発現（実数値、tf-idf）• 𝑦 ∈ {ibm, mac} ：記事のカテゴリ（2値）• データ数（投稿数）：1168→ 分類問題なので、ロジスティック回帰に提案法を適⽤。

⼤域解にあった語列挙解で置き換わった語

drive, os, diskのようなibmマシン（Windows機）に特有の単語が⾒落とされていたのが⾒つかった。
040, 610のようなmacマシン（型番）に特有の単語が⾒落とされていたのが⾒つかった。

37

まとめn

問題意識：ユーザに信頼される特徴選択をしたい。
•nnn「Lasso解のサポート列挙」として問題を定式化した。
Lawlerの𝑘-best フレームワークを適⽤した効率的なアルゴリズムを設計。
列挙版のスパース復元定理を証明した。
•n単⼀の特徴選択結果を出⼒するのでなく、複数の結果を列挙して出⼒する。

どれだけ列挙するかは問題パラメタ依存。

実験より，実際の特徴選択問題には「同じくらいの品質の解が⼤量に存在する」ことを確認。
•Lasso で得られた特徴量を安易に信じるのは危険。

38

補⾜資料

39

列挙版の復元定理（完全版）
n仮定：𝑦 = 𝑋𝛽L + 𝑤; 𝛽L スパース, 𝑤 ∼ 𝑁(0, 𝜎^2)

𝑋𝛽 L − 𝑦 A ≤ 𝛿 𝑋𝛽 ∗ − 𝑦 A for some 𝛿 ≥ 0•𝑋𝛽 ∗ − 𝑦 A ≤ 𝜖 for some 𝜖 ≥ 0• ∀𝑢 ≠ 0 with 𝑋𝑢 A ≤ 1 + 𝛿 𝜖, 𝑢r s 6 ≤ 𝛾 𝑢r su 6 for some 𝛾 ≥max{1, 𝛿 A }•定理1：No False Inclusion

By enumerating solutions up to 𝐿 𝛽 ℓ ≥ 𝛾𝐿(𝛽 ∗ ), we can find 𝛽 x , 𝑆 x ,1 ≤ 𝑘 ≤ ℓ such that supp 𝛽 x ⊆ supp 𝛽 L ⊆ 𝑆 x and 𝐿 𝛽 x ≤ 𝐿(𝛽 L ).

定理2：No False Exclusion

Let 𝛽 x , 𝑆 x be an enumerated solution where supp 𝛽 x
𝑆 x . If 𝑋r1s 𝑋r s is invertible, then we have{6supp 𝛽 x ⊇ 𝑖 ∶ 𝛽"L > 2𝜌 𝑋r1s 𝑋r s

⊆ supp 𝛽 L ⊆|with probability 1 − 𝑆 L exp −𝜌A /2𝜎 𝜆€•‚ 𝑋r1s 𝑋r s.
40