Upgrade to Pro
— share decks privately, control downloads, hide ads and more …
Speaker Deck
Features
Speaker Deck
PRO
Sign in
Sign up for free
Search
Search
高次元データに対するL1正則化の有効性
Search
Takayuki Uchiba
December 14, 2018
Technology
1
3.1k
高次元データに対するL1正則化の有効性
高次元データに対してよく用いられるL1正則化、特にLasso回帰の有効性について数理統計的にわかっている話を少しだけサマリーしました。
Takayuki Uchiba
December 14, 2018
Tweet
Share
More Decks by Takayuki Uchiba
See All by Takayuki Uchiba
statistician_ja_lt5.pdf
utaka233
0
660
縮小推定のはなし.pdf
utaka233
1
2.3k
Other Decks in Technology
See All in Technology
新卒エンジニア研修の試行錯誤と工夫/nikkei-tech-talk-31
nishiuma
0
200
ウェブアクセシビリティとは
lycorptech_jp
PRO
0
260
Javaの新しめの機能を知ったかぶれるようになる話 #kanjava
irof
3
4.9k
20250328_OpenAI製DeepResearchは既に一種のAGIだと思う話
doradora09
PRO
0
150
AI・LLM事業部のSREとタスクの自動運転
shinyorke
PRO
0
300
一人QA時代が終わり、 QAチームが立ち上がった話
ma_cho29
0
290
技術好きなエンジニアが _リーダーへの進化_ によって得たものと失ったもの / The Gains and Losses of a Tech-Enthusiast Engineer’s “Evolution into Leadership”
kaminashi
0
200
Tirez profit de Messenger pour améliorer votre architecture
tucksaun
1
140
LINE API Deep Dive Q1 2025: Unlocking New Possibilities
linedevth
1
160
ソフトウェア開発におけるインターフェイスという考え方 / PHPerKaigi 2025
k1low
9
3.9k
グループポリシー再確認
murachiakira
0
160
Security response for open source ecosystems
frasertweedale
0
100
Featured
See All Featured
Evolution of real-time – Irina Nazarova, EuRuKo, 2024
irinanazarova
7
620
The Success of Rails: Ensuring Growth for the Next 100 Years
eileencodes
44
7.1k
Unsuck your backbone
ammeep
670
57k
VelocityConf: Rendering Performance Case Studies
addyosmani
328
24k
Fashionably flexible responsive web design (full day workshop)
malarkey
407
66k
How to Think Like a Performance Engineer
csswizardry
22
1.5k
The Straight Up "How To Draw Better" Workshop
denniskardys
232
140k
Making the Leap to Tech Lead
cromwellryan
133
9.2k
Reflections from 52 weeks, 52 projects
jeffersonlam
349
20k
It's Worth the Effort
3n
184
28k
Rails Girls Zürich Keynote
gr2m
94
13k
Navigating Team Friction
lara
184
15k
Transcript
ߴ࣍ݩσʔλʹର͢Δ-ਖ਼ଇԽͷ༗ޮੑ !VUBLB ػցֶशͷཧ"EWFOU$BMFOEBS
എܠ ߴ࣍ݩσʔλ ɾೖྗมͷݸEαϯϓϧαΠζO ɾྫɿηϯαʔσʔλ࣍ੈγʔέϯαʔʹΑΔήϊϜྻσʔλͳͲ ߴ࣍ݩσʔλʹ͓͚Δ༧ଌ ɾදྫઢܗճؼϞσϧɿ ɹɹɾฏۉଛࣦ࠷খԽਪఆྔɿਖ਼نํఔࣜͷղ ɹɹɹߴ࣍ݩσʔλͰɺਖ਼نํఔࣜͷղͷҰҙੑΛظͰ͖ͳ͍ɻ ɹɹɹͳͥͳΒɺਖ਼نํఔࣜͷղ͕ҰҙͰ͋ΔͨΊʹ ɹɹɹཁߦྻ͕GVMMSBOLͰ͋Δඞཁ͕͋Δɻͱ͜Ζ͕ɺ
ɹɹɹͳͷͰɺߴ࣍ݩσʔλͰҰൠʹΓཱͨͣແݶʹղΛڐ͠ಘΔɻ y = Xw + ϵ, ϵ ∼ N(0,σ2En ) XT Xw = XTy rankXT X = n rankXT X = rankX ̂ w = argmin 1 2n ||y − Xw||2 2 ˠ
ઢܗճؼϞσϧʹ͓͚Δ-ਖ਼ଇԽʢ-BTTPճؼʣ ߴ࣍ݩσʔλʹ͓͚ΔઢܗճؼϞσϧ ɾूஂϞσϧʹఆ͢ΔԾઆɿճؼ͕εύʔεϕΫτϧͰ͋Δͱ͍͏ظ ɾ-BTTPճؼɿ-ਖ਼ଇԽʹΑΔεύʔεਪఆ ɹɾฏۉ̎ଛࣦ࠷খԽΛҎԼͷΑ͏ʹमਖ਼͢Δɻ ɹɹ͜ΕɺҎԼͷΑ͏ͳ੍͖࠷దԽͱಉͰ͋Δɻ ɹɹతؔͷತੑ͔Βղଘࡏͯ͠ҰҙʹͳΔɻ ɹɹ͞Βʹɺ੍݅ͷܗ͔Βղ͕εύʔεϕΫτϧʹͳΔ͜ͱ͕ظͰ͖Δɻ ̂ w
= argmin 1 2n ||y − Xw||2 2 + λn ||w|| 1 min 1 2n ||y − Xw||2 2 s . t . ||w|| 1 ≤ C
հ͢Δఆཧ ఆཧɿ</FHBICBO3BWJLVNBS8BJOXSJHIU:V $PSPMMBSZ> ूஂ͕ઢܗճؼϞσϧͰɺಛʹճؼɹ͕Lεύʔεͱ͠·͢ɻ ·ͨɺೖྗมEྻͰಠཱʹඪ४ਖ਼نʹै͍ͬͯΔͱ͠·͠ΐ͏ɻ͍· αΠζOͷඪຊΛऔͬͨ࣌ɺ ΛΈͨ͢ेେ͖ͳਖ਼ͷD͕͋Δͱ͠·͢ɻ͜ͷͱ͖ɺਖ਼ଇԽύϥϝʔλΛ ΛΈͨ͢Α͏ʹͱΕ-BTTPճؼʹΑͬͯಘΒΕΔϕΫτϧɹগͳ͘ͱ֬ ͰҎԼͷධՁΛΈͨ͢ɻ͜͜Ͱɺ$ఆͱ͢Δɻ
w* ̂ w n ≥ ck log(d) λn ≥ 8σ log(d)/n 1 − 1/d − O(exp(−n/2)) || ̂ w − w*||2 2 ≤ C kσ2 log(d) n
հ͢Δఆཧͷओு ཁ͢Δʹɺ ɾूஂ͕ઢܗճؼϞσϧͰճؼ͕ेʹεύʔεϕΫτϧͰ͋Δɻ ɾೖྗۭ͕ؒेʹߴ࣍ݩʹͳ͍ͬͯΔɻ ͷͰ͋Εɺेʹେ͖ͳਖ਼ଇԽύϥϝʔλΛΈͨ͢Α͏ʹͱΔ͜ͱͰɺ-BTTP ճؼͷਪఆྔͷฏۉޡࠩ ɾ࣍ݩʹରͯ͠ରతʹ͔͠ґଘ͠ͳ͍ɻʢ࣍ݩͷґଘ͕͍ʂʣ ɾճؼͷεύʔεੑɺޡࠩͷࢄɺαϯϓϧαΠζʹઢܗʹґଘ͢Δɻ ͱ͍͏ධՁΛ༩͍͑ͯΔɻ
ূ໌ͷͨΊͷ४උ Ωʔϫʔυɿ੍ݶڧತੑ 34$DPOEJUJPO αΠζɹɹͷߦྻ9ʹରͯ͠ɺू߹$ S Λ࣍ͷΑ͏ʹఆٛ͠·͢ɻ ਖ਼ͷఆɹ͕ଘࡏͯ͠ɺҙͷ$ S ͷݩ϶ʹରͯ͠ҎԼͷෆࣜ
ཱ͕͢Δͱ͖ɺߦྻ9$ S ʹ੍ؔͯ͠ݶڧತੑΛΈͨ͢ͱݴ͍·͢ɻ n × d C(r) = { Δ ∈ ℝd ∣ Δ ≠ 0, ||Δ|| 1 ||Δ|| 2 ≤ r } 1 n ||XΔ||2 2 ≥ κ||Δ||2 2 κ
੍ݶڧತੑͷͱͰͷ-BTTPਪఆྔͷྑ͞ ิɿ</FHBICBO3BWJLVNBS8BJOXSJHIU:V 5IFPSFN> ूஂʹର͢ΔԾఆɺఆཧͱ·ͬͨ͘ಉ͡Ͱ͋Δͱ͢Δɻ͠ਖ਼ͷఆD Λͱͬͯɺߦྻ9͕ू߹ɹɹɹɹɹɹɹʹରͯ͠ఆɹͰڧತੑΛ࣋ͭͱ͢Δɻ ͜ͷͱ͖ɺҙͷਖ਼ͷLʹରͯ͠ Ͱ͋Εɺਖ਼ଇԽύϥϝʔλ͕ɹɹɹɹɹɹɹɹͷ-BTTPճؼʹΑͬͯಘΒΕΔ ਪఆྔҎԼͷධՁΛຬͨ͠·͢ɻ C(8
n/(c log d)) κ n ≥ ck log(d) λn ≥ 2||XTϵ|| ∞ /n || ̂ w − w*||2 2 ≤ 9kλn κ2 ͜ͷධՁͩͱ͋·Γخ͕͠͞Θ͔Βͳ͍ɻ
ศརͳෆࣜ ิɿ<3BTLVUUJ8BJOXSJHIU:V 1SPQPTJUJPO> αΠζɹɹͷߦྻ9ͷ֤ߦ͕ಠཱʹଟมྔਖ਼ن/ Є ʹैͬͯಘΒΕΔͱ͖ ਖ਼ͷఆD D`͕ଘࡏͯ͠ɺҙͷE࣍ݩϕΫτϧWʹରͯ͠গͳ͘ͱ֬
ͰҎԼͷධՁ͕Γཱͪ·͢ɻͨͩ͠ɺ4ೖྗมͷඪ४ภࠩͷ࠷େͰ͢ɻ n × d 1 − c exp(−c′n) ||Xv|| 2 n ≥ 1 4 ||Σ1/2v|| 2 − 9S log(d) n ||v|| 1
ఆཧͷূ໌ 3BTLVUUJ8BJOXSJHIU:Vͷෆ͔ࣜΒ ΛಘΔɻͦ͜ͰɺɹɹɹɹɹɹɹɹͳͷͰɺఆDΛेେ͖͘ͱΕΕ ੍ݶڧತੑ͕গͳ͘ͱ֬ɹɹɹɹɹɹɹͰΓཱͭ͜ͱ͕Θ͔Γ·͢ɻ ͜͜ͰɺࠓͱͬͨఆD͕ɹɹɹɹɹɹΈͨ͢ͱԾఆͯ͠ɺ /FHBICBO3BWJLVNBS8BJOXSJHIU:VͷఆཧΛߟ͑·͢ɻਖ਼ଇԽύϥϝʔλͷ ͔݅Βɺগͳ͘ͱ֬ Ͱਪఆྔʹؔ͢ΔఆཧͷධՁΛಘΔɻҎ্ͰఆཧΛূ໌Ͱ͖ͨɻ ||Xv|| 2
n ≥ 1 4 ( 1 − 36 log(d) n ||v|| 1 ||v|| 2 ) v ∈ C(8 n/(c log d)) 1 − c exp(−c′n) n ≥ ck log(d) P [ ||XTϵ|| ∞ ≤ 8σ2n log(d)] ≥ 1 − 1 d − exp (− n 2 )
ࢀߟจݙ <>3BTLVUUJ8BJOXSJHIU:V .JOJNBYSBUFTPGFTUJNBUJPOGPSIJHI EJNFOTJPOBMMJOFBSSFHSFTTJPOPWFSMRCBMMT *&&&5SBOTBDUJPO PO*OGPSNBUJPO5IFPSZ <>/FHBICBO3BWJLVNBS8BJOXSJHIU:V "6OJpFE'SBNFXPSLGPS )JHI%JNFOTJPOBM"OBMZTJTPG.&TUJNBUPSTXJUI%FDPNQPTBCMF
3FHVMBSJ[FST 4UBUJTUJDBM4DJFODF 7PM /P <>Ԭ྄ଠ εύʔεੑʹجͮ͘ػցֶश ػցֶशϓϩϑΣογϣφϧ γϦʔζ ߨஊࣾ