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
3k
高次元データに対する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
630
縮小推定のはなし.pdf
utaka233
1
2.2k
Other Decks in Technology
See All in Technology
Oracle Base Database Service 技術詳細
oracle4engineer
PRO
5
49k
Automated Promptingを目指すその前に / Before we can aim for Automated Prompting
rkaga
0
110
新卒1年目が挑む!生成AI × マルチエージェントで実現する次世代オンボーディング / operation-ai-onboarding
cyberagentdevelopers
PRO
1
160
pandasはPolarsに性能面で追いつき追い越せるのか
vaaaaanquish
4
4.5k
生成AIの強みと弱みを理解して、生成AIがもたらすパワーをプロダクトの価値へ繋げるために実践したこと / advance-ai-generating
cyberagentdevelopers
PRO
1
180
新R25、乃木坂46 Mobileなどのファンビジネスを支えるマルチテナンシーなプラットフォームの全体像 / cam-multi-cloud
cyberagentdevelopers
PRO
1
130
ガバメントクラウド単独利用方式におけるIaC活用
techniczna
3
270
신뢰할 수 있는 AI 검색 엔진을 만들기 위한 Liner의 여정
huffon
0
310
一休.comレストランにおけるRustの活用
kymmt90
3
580
新卒1年目が向き合う生成AI事業の開発を加速させる技術選定 / ai-web-launcher
cyberagentdevelopers
PRO
7
1.5k
ユーザーの購買行動モデリングとその分析 / dsc-purchase-analysis
cyberagentdevelopers
PRO
2
100
Apple/Google/Amazonの決済システムの違いを踏まえた定期購読課金システムの構築 / abema-billing-system
cyberagentdevelopers
PRO
1
220
Featured
See All Featured
Testing 201, or: Great Expectations
jmmastey
38
7k
Rails Girls Zürich Keynote
gr2m
93
13k
Faster Mobile Websites
deanohume
304
30k
Java REST API Framework Comparison - PWX 2021
mraible
PRO
28
7.9k
Exploring the Power of Turbo Streams & Action Cable | RailsConf2023
kevinliebholz
27
4.2k
Facilitating Awesome Meetings
lara
49
6k
Bash Introduction
62gerente
608
210k
[RailsConf 2023] Rails as a piece of cake
palkan
51
4.9k
Principles of Awesome APIs and How to Build Them.
keavy
126
17k
Writing Fast Ruby
sferik
626
61k
The Psychology of Web Performance [Beyond Tellerrand 2023]
tammyeverts
41
2.1k
Side Projects
sachag
452
42k
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 <>Ԭ྄ଠ εύʔεੑʹجͮ͘ػցֶश ػցֶशϓϩϑΣογϣφϧ γϦʔζ ߨஊࣾ