[読み会] ControlBurn- Feature Selection by Sparse Forests

読み会資料
ControlBurn- Feature Selection by Sparse Forests (KDD2021)

Transcript

1. ೥݄೔
   !
   ಡΈձ
   ൃදऀɿ༶໌఩ $POUSPM#VSO
   
 'FBUVSF
   4FMFDUJPO
   CZ
   4QBSTF
   'PSFTUT
2. ࿦จ৘ใͱબ୒ཧ༝  ࿦จ৘ใ
   બ୒ཧ༝
   ಛ௃ྔબ୒ख๏͸આ໌ੑɼެฏੑʹ΋େ͖ؔ͘ΘΔ͔Β
   ,BHHMFͷಛ௃ྔΛͱΓ͋͑ͣશ෦ͭͬ͜Ή͜ͱʹೲಘͰ͖ͳ͍
3. 5SFF#BTFͷಛ௃ྔબ୒ख๏ΛఏҊ  എܠɿܾఆ໦ʴΞϯαϯϒϧख๏͸ਫ਼౓ɼղऍੑͱ΋ʹ༏ल
   ໰୊ɿಛ௃ྔಉ࢜ʹ૬͕ؔ͋ΔσʔλͰ͸ɼ 

   
   
   
   
   
   
   
   
   ಛ௃ྔॏཁ౓͕౰ͯʹͳΒͳ͍
   ˠ
   ૬ؔόΠΞεʹऑ͍
   ఏҊɿಛ௃ྔબ୒ʹॏΈ෇͖-"440Λద༻
   ݁Ռɿ૬͕ؔ͋ΔσʔλͰطଘͷಛ௃ྔબ୒ΑΓ΋ 

   
   
   
   
   
   
   
   
   30$"6$͕ߴ͘ɼ͔ͭಉ౳ͷܭࢉίετʹ཈͑ͨ
4. -JHIU(#.ͷGFBUVSF
   JNQPSUBODFྫ ܾఆ໦͸૬ؔόΠΞεʹऑ͍  ܾఆ໦ϕʔεͷख๏͸ 
 ਫ਼౓ͱղऍੑͷόϥϯε͕ྑ͍
   Ξϯαϯϒϧϕʔε͸ಛ௃ྔ਺͕ 
 େ͖͍৔߹Ͱ΋ΦʔόϑΟοτ͠ʹ͍͘
   ϒʔεςΟϯάܥͷख๏Ͱ͸ಛ௃ྔॏཁ ౓ͷܭࢉ͕༰қ
   • -JHIU(#.
   9(#PPTU
   4DJLJUMFBSO ͷGFBUVSF@JNQPSUBODF
5. ૬ؔόΠΞεʹΑͬͯಛ௃ྔॏཁ౓͕มԽ͢Δ  ૬͕ؔ͋Δಛ௃ྔಉ࢜Ͱॏཁ౓͕ബ·ͬͯ͠·͏ 4FY͔Β
   XJHIU
   IFJHIU
   GFNVS
   "HF͔ΒUJCJBΛਓ޻ੜ੒
6. ࢖Θͳ͍ಛ௃ྔΛޙ͔ΒؒҾ͘  ࠷ॳʹܾఆ໦ʹΑΔਂ͍৿ʢΞϯαϯϒϧπϦʔʣΛ࡞Γ 
 ͋ͱͰඞཁͳ͍໦ʢಛ௃ྔʣΛ೩΍͢🔥🌲🔥
   Ԡ༻ઌ
   • આ໌Մೳੑɿඞཁͳಛ௃ྔΛબ୒͢Δ͔Βղऍ͠΍͍͢ʂ
   • 0QUJNBM
   FYQFSJNFOUBM
   EFTJHO
   • ಛ௃ྔΛऔಘ͢ΔͨΊͷίετΛ࡟ݮͰ͖Δ
   • ҩྍ෼໺ͱ͔ͰΘ͟Θ͟σʔλΛͱΔ࣌ͳͲ
7. ४උɿܾఆ໦ͷ͍Ζ͍Ζ  ܾఆ໦ɿδχෆ७౓΍෼ྨޡࠩΛ࠷খԽ͢ΔΑ͏ʹֶश
   w ਂ͕͞ਂ͘ͳΔ΄Ͳදݱ͕ࡉ͔͘ͳΔʢ
   ʣ
   #BHHJOHɿCPPUTUSBQͨ͠σʔλͰ 
 ɹɹɹɹɹֶशثΛಠཱʹֶशɼग़ྗΛ౷߹ͯ͠࠷ऴग़ྗ
   #PPTUJOHɿऑֶशثΛ௚ྻʹܨ͍Ͱֶश 

   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   ࠷ऴతʹ͸ͦΕͧΕͷϞσϧΛ౷߹ͯ͠ग़ྗ
   'FBUVSF
   JNQPSUBODF
   w δχෆ७౓ͳͲΛݩʹܭࢉ͢Δ
   ˠ
   NFBO
   %FDSFBTF
   *NQVSJUZ 

   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   d → 2d
8. #BHHJOHɿόϦΞϯε͕খ͘͞ͳΓ΍͍͢  • ෳ਺Ͱଟ਺ܾ͢Δ͔ΒόϦΞϯε͕཈͑ΒΕΔ
   ϒʔτετϥοϓɿॏෳ͋Γ෮ݩநग़
9. #PPTUJOHɿόΠΞε͕খ͘͞ͳΓ΍͍͢  • ௚લͷϞσϧͷग़ྗΛݩʹ͢Δ͔ΒόΠΞε͕཈͑ΒΕΔ
10. ४උɿಛ௃ྔબ୒ͷ͍Ζ͍Ζ  σʔλͷதʹ͸ϞσϧੑೳʹӨڹ͠ͳ͍ಛ௃ྔ͕͋Δ͸ͣ
    Ϟσϧ͕ϊΠζʹରͯ͠ؤ݈ͳΒ͍͍͕ɼͦ͏͸͍͔ͳ͍
    
    ˠ
    ඞཁͳಛ௃ྔΛબ୒͍ͨ͠
    
    طଘख๏ύλʔϯ
    'JMUFS
    CBTFɿσʔλ౷ܭ͔Βಛ௃ྔΛධՁ
    8SBQQFSɿػցֶशϞσϧΛ࢖ͬͯධՁ
    
    &NCFEEJOHɿϞσϧֶशͱಉ࣌ʹධՁʢFH
    -BTTPʣ
11. ఏҊख๏ɿ-BTTPతͳ੍໿Ͱಛ௃ྔબ୒  ɿOݸͷܾఆ໦
    ɿ෼ྨ໦ͷ Ϋϥεͷग़ྗ݁Ռ
    ɿQݸͷಛ௃ྔΛ࢖͏͔Ͳ͏͔ͷϚεΫ
    ɿܾఆ໦ͷॏΈύϥϝʔλ
    ɿਖ਼ଇԽύϥϝʔλ ti
    GPS
    i ∈ {1,2,...,n} αi ∈ ℝm, A ∈ ℝm×n m gi ∈ {0,1}p, G ∈ ℝp×n w ∈ ℝn λ
12. -BTTPతͳ੍໿Ͱ࠷దԽ໰୊ͱ͢Δ  (SPVQ
    -BTTPΈ͍ͨͳേଇ߲ ʹΑͬͯ੺͍࿮͕͖·Δ
    ৭෇͖ϊʔυ͕࢖༻͢Δಛ௃ྔˠ(ʹΑΓܾఆ
    w
13. ఏҊख๏ɿ৿Λҭͯͯ
    ໦ΛؒҾ͘  ৿ΛҭͯΔɿܾఆ໦ͷֶशํ๏ΛͭఏҊ
    w *ODSFNFOUBM
    EFQUI
    CBHHJOH
    w *ODSFNFOUBM
    EFQUI
    CBHCPPTUJOH
    ໦ΛؒҾ͘ɿલड़ͷ࠷దԽ໰୊Λղ͘
    ˠ৿ΛҭͯΔύʔτͱ໦ΛؒҾ͘ύʔτ͸ͦΕͧΕಠཱ͢Δ
14. *ODSFNFOUBM
    EFQUI
    CBHHJOH  ϋΠύϥͱͯ͠࠷େਂ͞ Λઃఆ
    ऩଋͨ͠Β໦ͷਂ͞Λਂ͘͢Δ
    5SBJOޡ͕ࠩे෼খ͍͞ˠCBHHJOH͸ աֶश͠ʹ͍͘ ܭࢉ͕ૣ͍ dmax
15. *ODSFNFOUBM
    EFQUI
    CBHCPPTUJOH  • ͸࢒ᕓ͔Βࣗಈௐ੔Ͱ͖Δ
    ˠ
    վળ͞ΕΔݶΓਂ͘ʂ dmax
16. ࣮ݧɿఏҊͷಛ௃ྔબ୒ख๏ͷଥ౰ੑΛݟΔ  4FNJTZOUIFUJDɿ
    • ਓ޻తʹ૬ؔͷ͋Δಛ௃ྔΛ௥Ճ
    • ૬ؔόΠΞεΛ্खʹѻ͑Δ͔ΛݟΔ
    #FODINBSLɿ
    • ͷσʔληοτͰطଘख๏ͱ30$"6$ͷվળΛݟΔ
    $BTF
    TUVEJFTɿ
    • ϦΞϧσʔληοτͰͲ͏ͳΔ͔ݟΔ
17. ϕϯνϚʔΫͱܭࢉྔධՁ  ࣄલʹશͯͷσʔλΛ࢖ͬͯϥϯμϜϑΥ ϨετΛֶश
    ಛ௃ྔॏཁ౓Λݩʹ 
 ্Ґ
    ݸͷಛ௃ྔΛબ୒
    બ୒͞Εͨಛ௃ྔ͚ͩͰ࠶ֶशɹ 
 ˠɹϕϯνϚʔΫͱ͢Δ
    
    8SBQQFSCBTFख๏ͷ3FDVSTJWF
    'FBUVSF
    &MJNJOBUJPOͱܭࢉྔൺֱ͢Δ k
18. ݁Ռɿ૬ؔόΠΞεͷӨڹΛड͚ʹ͔ͬͨ͘  3BOEPN
    'PSFTUͷಛ௃ྔॏཁ ౓্ҐʹϊΠζΛՃ͑ͯɼ৽ͨ ͳಛ௃ྔͱͯ͠௥Ճ
    ϊΠζಛ௃ྔ͕૿Ճͯ͠΋ 
 Өڹ͕ड͚ͣʹؤ݈
19. #FODINBSLɿطଘख๏ΑΓਫ਼౓͕ߴΊ  ಛ௃ྔ਺Λ Λ ࢖ͬͨ30$"6$ͷ౓਺෼෍
    ϕϯνϚʔΫΑΓਫ਼౓޲্͕ ݟΒΕͨ k = 1,2,....,10
20. $BTF
    4UVEJFTɿ 
 ϦΞϧσʔλͷϊΠζͰ΋ར༻Մೳͩͬͨ 
21. ϦΞϧσʔληοτͰͷ૬ؔόΠΞε͕վળ  ॎ࣠ଠࣈ͕ఏҊʹΑΔ 
 ্Ґಛ௃ྔ
    ԣ͕࣠طଘख๏ͷ 
 ্Ґಛ௃ྔ
    'OMXHU͕ͳ্͔ͥҐʹདྷ ͍ͯΔͷ͕ফ͍͑ͯΔ
22. ·ͱΊ  • ॏΈ෇͖-BTTPϕʔεͷ 
 ಛ௃ྔબ୒Λߦ͏ΞϧΰϦζϜΛఏҊ
    • ͞·͟·ͳσʔληοτΛ༻͍ͯɼطଘख๏ͱൺ΂ 
 ૬ؔόΠΞεʹରͯ͠ؤ݈Ͱ͋Δ͜ͱΛࣔͨ͠
23. ײ૝  • ಛ௃ྔબ୒ͷϞνϕʔγϣϯ΋Θ͔Γ΍͘͢ɼख๏ͷ΍Γͨ ͍͜ͱ΋Θ͔͕ͬͨɼ࣮ࡍͷֶशํ๏͕গ͠ᐆດ
    • ੲ)VNBO
    CPPTUJOHಡΜ͕ͩɼ 
 )VNBO
    4UBDLJOH
    )VNBO
    //ͱ͔ͬͯ͋Δͷ͔ؾʹͳͬͨ
    • ެฏੑʹ͍ؔͯ͠͏ͱɼϨουϥΠϯޮՌʹରͯ͠࢖͑ͦ͏
    • ૬ؔͷ͋Δಛ௃ྔʹ͓͍ͯ 
 Ͳ͕ͬͪຊ࣭͔ܾఆ͢Δͷ೉ͦ͠͏