Upgrade to Pro — share decks privately, control downloads, hide ads and more …

Harnessing the Power of Vicinity-Informed Analy...

Harnessing the Power of Vicinity-Informed Analysis for Classification under Covariate Shift

第15回ザッピングセミナーにおける発表資料です.

Kazuto Fukuchi

June 10, 2024
Tweet

More Decks by Kazuto Fukuchi

Other Decks in Research

Transcript

  1. ࣗݾ঺հ w ໊લ෱஍Ұే 'VLVDIJ ,B[VUP  w ॴଐஜ೾େֶγεςϜ৘ใܥॿڭ w ܦྺ

    w ஜ೾େֶγεςϜ৘ใ޻ֶઐ߈Պത࢜ޙظ՝ఔमྃ w ཧݚ"*1ಛผݚڀһ w ݱࡏஜ೾େֶγεςϜ৘ใܥॿڭ w ݱࡏཧݚ"*1٬һݚڀһ w ݚڀڵຯ w ػցֶशʹ͓͚ΔόΠΞεʢެฏੑɼసҠֶशɼҼՌਪ࿦ʣ w ਺ཧ౷ܭɼಛʹɼ൚ؔ਺ਪఆ
  2. ෼ྨ໰୊ ֶशΞϧΰϦζϜ ෼ྨث h( )=Ҝࢠ ͳΔ΂͘౰ͨΔΑ͏ h Λબ୒͍ͨ͠ ϥϕϧ෇͖σʔλ 0

    ffi DF)PNF%BUBTFU)7FOLBUFTXBSBFUBM%FFQIBTIJOHOFUXPSLGPSVOTVQFSWJTFEEPNBJOBEBQUBUJPO$713 QQ 
  3. సҠֶश ֶशΞϧΰϦζϜ ෼ྨث h( )=Ҝࢠ ιʔεσʔλ ༧ଌ࣌ʹҟͳΔ ੑ࣭ͷσʔλ λʔήοτ 0

    ffi DF)PNF%BUBTFU)7FOLBUFTXBSBFUBM%FFQIBTIJOHOFUXPSLGPSVOTVQFSWJTFEEPNBJOBEBQUBUJPO$713 QQ 
  4. సҠֶश ֶशΞϧΰϦζϜ ෼ྨث h( )=Ҝࢠ ιʔεσʔλ ༧ଌ࣌ʹҟͳΔ ੑ࣭ͷσʔλ λʔήοτσʔλ ༧ଌ࣌ͱಉ͡ੑ࣭ͷ

    σʔλΛগྔ؍ଌ ιʔεσʔλ͸ େྔʹ֬อՄೳ λʔήοτ 0 ffi DF)PNF%BUBTFU)7FOLBUFTXBSBFUBM%FFQIBTIJOHOFUXPSLGPSVOTVQFSWJTFEEPNBJOBEBQUBUJPO$713 QQ 
  5. సҠֶश ֶशΞϧΰϦζϜ ෼ྨث h( )=Ҝࢠ ιʔεσʔλ ιʔεσʔλΛ׆༻͠ ͯΑΓߴਫ਼౓ͷ ༧ଌΛ࣮ݱ λʔήοτσʔλ

    ༧ଌ࣌ͱಉ͡ੑ࣭ͷ σʔλΛগྔ؍ଌ ιʔεσʔλ͸ େྔʹ֬อՄೳ ༗༻ͳ৘ใΛநग़ʢసҠʣ λʔήοτ 0 ffi DF)PNF%BUBTFU)7FOLBUFTXBSBFUBM%FFQIBTIJOHOFUXPSLGPSVOTVQFSWJTFEEPNBJOBEBQUBUJPO$713 QQ 
  6. సҠֶशͷ੒ޭ wྫ0 ff i DF)PNFEBUBTFU wͭͷυϝΠϯ Ξʔτ ΫϦοϓΞʔτ ϓϩμΫτ ϦΞϧ

     wͷΧςΰϦ 0 ffi DF)PNF%BUBTFU)7FOLBUFTXBSBFUBM%FFQIBTIJOHOFUXPSLGPSVOTVQFSWJTFEEPNBJOBEBQUBUJPO$713 QQ  1BQFSTXJUI$PEFIUUQTQBQFSTXJUIDPEFDPNTPUBEPNBJOBEBQUBUJPOPOP ff i DFIPNF  ෼ྨਫ਼౓
  7. ෼ྨ໰୊ͷֶश ֶशΞϧΰϦζϜ ෼ྨث h( )=Ҝࢠ h ʹΑΔ෼ྨޡ͕ࠩ ࠷খʹͳΔΑ͏ʹ͢Δ ϥϕϧ෇͖σʔλ 0

    ffi DF)PNF%BUBTFU)7FOLBUFTXBSBFUBM%FFQIBTIJOHOFUXPSLGPSVOTVQFSWJTFEEPNBJOBEBQUBUJPO$713 QQ 
  8. ෼ྨ໰୊ͷֶश ֶशΞϧΰϦζϜ ෼ྨث h ʹΑΔ෼ྨޡ͕ࠩ ࠷খʹͳΔΑ͏ʹ͢Δ ϥϕϧ෇͖σʔλ 0 ffi DF)PNF%BUBTFU)7FOLBUFTXBSBFUBM%FFQIBTIJOHOFUXPSLGPSVOTVQFSWJTFEEPNBJOBEBQUBUJPO$713

    QQ  h(X) = ̂ Y (X, Y) ∼ P (X, Y) iid ∼ P = (X1 , Y1 ), ⋮ , (Xn , Yn ) ෼ྨޡࠩʢظ଴ޡࠩʣ errP (h) = 𝔼 P [1{h(X) ≠ Y}]
  9. ʢڭࢣ͋ΓʣసҠֶश ֶशΞϧΰϦζϜ ෼ྨث h( )=Ҝࢠ ιʔεσʔλ h ʹΑΔλʔήοτͰ ͷ෼ྨޡ͕ࠩ ࠷খʹͳΔΑ͏ʹ͢Δ

    λʔήοτσʔλ λʔήοτ 0 ffi DF)PNF%BUBTFU)7FOLBUFTXBSBFUBM%FFQIBTIJOHOFUXPSLGPSVOTVQFSWJTFEEPNBJOBEBQUBUJPO$713 QQ 
  10. ʢڭࢣ͋ΓʣసҠֶश ֶशΞϧΰϦζϜ ෼ྨث h(X) = ̂ Y ιʔεσʔλ P h

    ʹΑΔλʔήοτͰ ͷ෼ྨޡ͕ࠩ ࠷খʹͳΔΑ͏ʹ͢Δ λʔήοτσʔλ Q λʔήοτ Q (X, Y)P iid ∼ P = (X1 , Y1 ), ⋮ , (XnP , YnP ) (X, Y)Q iid ∼ Q = (XnP +1 , YnP +1 ), ⋮ , (XnP +nQ , YnP +nQ ) nP ≫ nQ ෼ྨޡࠩʢظ଴ޡࠩʣ errQ (h) = 𝔼 Q [1{h(X) ≠ Y}] (X, Y) ∼ Q
  11. సҠֶशͷֶशཧ࿦ wߏஙͨ͠ΞϧΰϦζϜʹ͍ͭͯ࢒༨ޡࠩͱιʔεͷαϯϓ ϧαΠζ ͱλʔήοτͷαϯϓϧαΠζ ͷؔ܎Λ໌Β ͔ʹ͍ͨ͠ nP nQ ιʔεαϯϓϧαΠζେ ιʔεαϯϓϧαΠζখ

    λʔήοτޡࠩେ λʔήοτޡࠩখ nP errQ (h) ℰQ (h) = errQ (h) − inf h*:Մଌؔ਺ errQ (h*) inf h*:Մଌؔ਺ errQ (h*) 𝔼 [ℰQ (h)] ≤ U(nP , nQ )
  12. $PWBSJBUF4IJGU ιʔε λʔήοτ PX QX PY|X QY|X  PX ≠

    QX PY|X (Y = 1|X) = QY|X (Y = 1|X) = η(X) $PWBSJBUFTIJGUԾఆ η(X) = 1 2
  13. ෼෍ؒڑ཭Λ࢖ͬͨ൚ԽޡࠩʹΑΔ্ք #FO%BWJEFUBM  1BSLFUBM "NJOJBOFUBM   ʜ w൚ԽޡࠩղੳΛ௨ͨ͠࢒ࠩޡࠩͷ্ք 𝔼

    [ℰQ (h)] ≤ errP,nP (h) + d(PX , QX ) + n−c P ιʔεͷܦݧޡࠩerrP,nP (h) = 1 nP nP ∑ i=1 1{h(Xi ) ≠ Yi } ෼෍ؒڑ཭ ιʔεͷܦݧޡࠩ ෼෍͕ࣅ͍ͯΔ΄ͲసҠֶश্͕ख͍͘͘ ݟͨ໨͕ࣅ͍ͯΔ
  14. ෼෍ؒڑ཭Λ࢖ͬͨ൚ԽޡࠩʹΑΔ্ք #FO%BWJEFUBM  1BSLFUBM "NJOJBOFUBM   ʜ w൚ԽޡࠩղੳΛ௨ͨ͠࢒ࠩޡࠩͷ্ք 𝔼

    [ℰQ (h)] ≤ errP,nP (h) + d(PX , QX ) + n−c P ιʔεͷܦݧޡࠩerrP,nP (h) = 1 nP nP ∑ i=1 1{h(Xi ) ≠ Yi } ෼෍ؒڑ཭ ιʔεͷܦݧޡࠩ ෼෍͕ࣅ͍ͯΔ΄ͲసҠֶश্͕ख͍͘͘ ݟͨ໨͕ࣅ͍ͯΔ ຊ౰ʹʁ
  15. ֬཰ൺΛ࢖্ͬͨք ,QPUVGF .BFUBM  'FOHFUBM  w֬཰ൺ  wֶशΞϧΰϦζϜ ρ(x)

    = dQX dPX (x) h = arg minh 1 nP ∑nP i=1 ρ(Xi )ℓ(h, (Xi , Yi )) ιʔε λʔήοτ PX QX ௿͍ॏΈ ߴ͍ॏΈ λʔήοτͬΆ͍σʔλΛ ߴ͘ධՁ͢Δ
  16. ֬཰ൺΛ࢖্ͬͨք ,QPUVGF .BFUBM  'FOHFUBM  w֬཰ൺ  wֶशΞϧΰϦζϜ ρ(x)

    = dQX dPX (x) h = arg minh 1 nP ∑nP i=1 ρ(Xi )ℓ(h, (Xi , Yi )) 𝔼 [ℰQ (h)] ≤ C ( ln(nP ) nP ) c ҰகੑΛ͍ࣔͤͯΔʁ
  17. ֬཰ൺΛ࢖্ͬͨք ,QPUVGF .BFUBM  'FOHFUBM  w֬཰ൺ  wֶशΞϧΰϦζϜ ρ(x)

    = dQX dPX (x) h = arg minh 1 nP ∑nP i=1 ρ(Xi )ℓ(h, (Xi , Yi )) 𝔼 [ℰQ (h)] ≤ C1 ( ln(nP ) nP ) c1 + C2 n−c2 Q ͷਪఆʹҰகੑΛ ્֐͢Δ߲͕ݱΕΔ ρ ֶशʹ֬཰ൺΛ࢖͍ͬͯΔ ࣮ࡍʹ͸ಘΒΕͳ͍ ͜ΕΒͷ্քͰ͸αϯϓϧαΠζʹର͢ΔҰகੑΛࣔͤͳ͍
  18. ڑ཭ۭؒϕʔε෼෍ؒྨࣅ౓ʹΑΔ্ք ,QPUVGFFUBM  1BUIBLFUBM  (BMCSBJUIFUBM   ڑ཭্ۭؒͷ௒ٿΛ΋ͱʹͨ͠ྨࣅ౓ 1BUIBLFUBM

      wڑ཭ۭؒ  w൒ܘ ͷ௒ٿ ( 𝒳 , ρ) r Bρ (x, r) = {x′  ∈ 𝒳 : ρ(x, x′  ) ≤ r} ΔPMW (P, Q; r) = ∫ 𝒳 1 PX (B(x, r)) QX (dx) ͷ࣌ ҰகੑΛ࣋ͭΞϧΰϦζϜΛߏங ΔPMW (P, Q; r) = O(r−τ) (τ < ∞) 𝔼 [ℰQ (h)] ≤ Cn−c P (c > 0) ࣮ࡍ͸ 1BUIBLFUBM  ͸ճؼઃఆͰ͋Δ͕ɼ্هྨࣅ౓͸෼ྨʹద༻Մೳʢຊ࿦จʣ
  19. ڑ཭ϕʔε෼෍ؒྨࣅ౓ʹΑΔ্ք ,QPUVGFFUBM  1BUIBLFUBM  (BMCSBJUIFUBM   ڑ཭্ۭؒͷ௒ٿΛ΋ͱʹͨ͠ྨࣅ౓ ΔPMW

    (P, Q; r) = ∫ 𝒳 1 PX (B(x, r)) QX (dx) ׂΓࢉ͕ى͜ΔՄೳੑ ιʔε PX QX λʔήοτ ॏͳ͍ͬͯΔʢઈର࿈ଓʣ ˠׂ͸ى͜Βͳ͍
  20. ڑ཭ϕʔε෼෍ؒྨࣅ౓ʹΑΔ্ք ,QPUVGFFUBM  1BUIBLFUBM  (BMCSBJUIFUBM   ڑ཭্ۭؒͷ௒ٿΛ΋ͱʹͨ͠ྨࣅ౓ ΔPMW

    (P, Q; r) = ∫ 𝒳 1 PX (B(x, r)) QX (dx) ׂΓࢉ͕ى͜ΔՄೳੑ ιʔε PX QX λʔήοτ ͣΕ͍ͯΔʢඇઈର࿈ଓʣ ˠׂ͕ى͜Δʂ
  21. ڑ཭ϕʔε෼෍ؒྨࣅ౓ʹΑΔ্ք ,QPUVGFFUBM  1BUIBLFUBM  (BMCSBJUIFUBM   ڑ཭্ۭؒͷ௒ٿΛ΋ͱʹͨ͠ྨࣅ౓ ΔPMW

    (P, Q; r) = ∫ 𝒳 1 PX (B(x, r)) QX (dx) ׂΓࢉ͕ى͜ΔՄೳੑ ιʔε PX QX λʔήοτ ͣΕ͍ͯΔʢඇઈର࿈ଓʣ ˠׂ͕ى͜Δʂ ඇઈର࿈ଓͷঢ়ଶͰ͸αϯϓϧαΠζʹର͢ΔҰகੑΛࣔͤͳ͍
  22. ݱ࣮ੈքͰͷඇઈର࿈ଓੑ wྫ0 ff i DF)PNFEBUBTFU wͭͷυϝΠϯ Ξʔτ ΫϦοϓΞʔτ ϓϩμΫτ ϦΞϧ

     wͷΧςΰϦ 0 ffi DF)PNF%BUBTFU)7FOLBUFTXBSBFUBM%FFQIBTIJOHOFUXPSLGPSVOTVQFSWJTFEEPNBJOBEBQUBUJPO$713 QQ  ҟͳΔυϝΠϯͰ͸ग़ݱ͠ͳ͍ը૾͕͋Δˠඇઈର࿈ଓ
  23. ΍ͬͨ͜ͱ w৽͍͠௒ٿΛ΋ͱʹͨ͠ྨࣅ౓ΛఏҊ Δ 𝒱 (P, Q; r) = ∫ 𝒳

    inf x′  ∈ 𝒱 (x) 1 PX (B(x′  , r)) QX (dx) ۙ๣ू߹ 𝒱 (x) ͷ࣌ ҰகੑΛ࣋ͭΞϧΰϦζϜΛߏங Δ 𝒱 (P, Q; r) = O(r−τ) (τ < ∞) *O fi NVNΛऔΔ͜ͱͰׂΓࢉΛ ͋Δఔ౓ճආՄೳ
  24. //ΞϧΰϦζϜ k wιʔεʴλʔήοταϯϓϧΛ׆༻ͨ͠ //෼ྨث k (X, Y)P (X, Y)Q ιʔεαϯϓϧ

    λʔήοταϯϓϧ (X, Y) ݁߹ ςετೖྗX (X(1) , Y(1) ), . . . , (X(k) , Y(k) ) ͱڑ཭͕͍ۙ ݸΛநग़ X k ̂ ηk (X) = 1 k k ∑ i=1 Y(i) ̂ hk (X) = 1 { ̂ ηk (X) ≥ 1 2}
  25. λʔήοτ ͷ೉͠͞ Q wλʔήοταϯϓϧͷΈͰͷ෼ྨ໰୊ͷ೉͠͞ͷԾఆ w4NPPUIOFTT /PJTFDPOEJUJPO w4NPPUIOFTT ͷ)ÖMEFS࿈ଓੑ  

    w/PJTFDPOEJUJPO 5TZCBLPWϊΠζ৚݅  η |η(x) − η(x′  )| ≤ Cα ρα(x, x′  ) QX (0 < |η(X)− 1 2 | ≤ t) ≤ Cβ tβ X ϥϕϧ͕ ϥϕϧ͕ η(X) 1 2 1 ϊΠζͷେ͖͞ ʢؒҧͬͨϥϕϧ͕ಘΒΕΔ֬཰ʣ େ͖͍ϊΠζك ۙ͘ͷϥϕϧ͸ಉ͡
  26. ۙ๣ू߹ w఺ ͷϥϕϧΛ༧ଌ͢Δͱ͖ϥϕϧ͕มΘΒͳ͍ۙ๣఺ ͷϥϕϧΛ༧ଌͨ݁͠ՌΛ࢖ͬͯྑ͍ X X′  𝒱 (x) =

    { x′  ∈ 𝒳 : 2Cα ρα(x, x′  ) < η(x) − 1 2 } X 𝒱 (X) ڥքΛ௒͑ͳ͍͙Β͍ͷ େ͖͞ͷٿ
  27. సҠࢦ਺ɾࣗݾࢦ਺ wڑ཭ۭؒϕʔεྨࣅ౓  w Λ࢖ͬͨ ͷಛ௃ ͱ ͷಛ௃ Δ(P, Q;

    r) Δ (P, Q) τ Q ψ 𝔼 [ℰQ (h)] ≤ U(nP , nQ ) λʔήοτ෼෍Ͱଌͬͨ࢒ࠩޡࠩ wཧ࿦ղੳͷ໨ඪ 𝔼 [ℰQ (h)] ≤ C (nc(τ) P + nc(ψ) Q ) −1 ͷ߲ͱ ͷ߲ͷ଍͠ࢉ nP nQ Λେ͖͘͢Ε͹ʹऩଋ ˠҰகੑ nP
  28. సҠࢦ਺ɾࣗݾࢦ਺ wڑ཭ۭؒϕʔεྨࣅ౓  w Λ࢖ͬͨ ͷಛ௃ ͱ ͷಛ௃  సҠࢦ਺

      ࣗݾࢦ਺  Δ(P, Q; r) Δ (P, Q) τ Q ψ Δ τ sup r∈(0,D 𝒳 ( r D 𝒳 ) τ Δ(P, Q; r) ≤ C Δ ψ sup r∈(0,D 𝒳 ( r D 𝒳 ) ψ Δ(Q, Q; r) ≤ C Δ(P, Q; r) = O(r−τ) Δ(Q, Q; r) = O(r−ψ)
  29. ओ݁Ռ ʢఆཧʣ ͸ ࿈ଓੑɼ ϊΠζ৚͕݅੒Γཱͪɼ ࣗݾࢦ ਺ Λ࣋ͭɽ ͸ సҠࢦ਺

    Λ࣋ͭɽ //෼ྨث͸Ҏ Լͷ্քΛ࣋ͭɽ Q α β Δ 𝒱 ψ (P, Q) Δ 𝒱 τ k C (n 1 + β 2 + β +max{1,τ/α} P + n 1 + β 2 + β +max{1,ψ/α} Q ) −1
  30. ओ݁Ռ w௨ৗઃఆͷ࠷దϨʔτ͸ ʢ ͸࣍ݩʣ "VEJCFSU FUBM   w࣮ࡍ ͸࣍ݩͱࣅͨΑ͏ͳੑ࣭Λ࣋ͭ

    n− 1 + β 2 + β + d/α d ψ ʢఆཧʣ ͸ ࿈ଓੑɼ ϊΠζ৚͕݅੒Γཱͪɼ ࣗݾࢦ ਺ Λ࣋ͭɽ ͸ సҠࢦ਺ Λ࣋ͭɽ //෼ྨث͸Ҏ Լͷ্քΛ࣋ͭɽ Q α β Δ 𝒱 ψ (P, Q) Δ 𝒱 τ k C (n 1 + β 2 + β +max{1,τ/α} P + n 1 + β 2 + β +max{1,ψ/α} Q ) −1 సҠࢦ਺ ࣗݾࢦ਺
  31. సҠࢦ਺ɾࣗݾࢦ਺ʹΑΔطଘ݁Ռͷ࠶ղऍ wطଘͷ݁Ռ͸ҟͳΔ Λ࢖͍ͬͯΔͱղऍͰ͖Δ 1BUIBLFUBM    ,QPUVGFFUBM  

      Δ ΔPMW (P, Q; r) = ∫ 𝒳 1 PX (B(x, r)) QX (dx) ΔDM (Q, Q; r) = sup x∈ 𝒳 Q 1 QX (B(x, r)) ΔBCN (Q, Q; r) = 𝒩 ( 𝒳 Q , ρ, r) ΔKM (Q, Q; r) = sup x∈ 𝒳 Q QX (B(x, r)) PX (B(x, r)) ඃෳ਺
  32. సҠࢦ਺ɾࣗݾࢦ਺ʹΑΔطଘ݁Ռͷ࠶ղऍ ʢఆཧʣ ͸ ࿈ଓੑɼ ϊΠζ৚͕݅੒Γཱͭɽ ʹ͍ͭ ͯҎԼͷ͍ͣΕ͔͕੒Γཱͭɽ  ͕ ࣗݾࢦ਺

    ɼ ͕ సҠࢦ਺ Λ࣋ͭ  ͕ PS ࣗݾࢦ਺ ɼ ͕ సҠࢦ਺ Λ͔࣋ͭͭ  ͜ͷ࣌ //෼ྨث͸ओఆཧͱಉ্͡քΛ࣋ͭɽͭ·Γɼ Q α β (P, Q) Q ΔPMW ψ (P, Q) ΔPMW τ Q ΔDM ΔBCN ψ (P, Q) ΔKM τ − ψ τ ≥ ψ k C (n 1 + β 2 + β +max{1,τ/α} P + n 1 + β 2 + β +max{1,ψ/α} Q ) −1 Λൺֱ͢Ε͹্քͷྑ͠ѱ͕͠ൺֱͰ͖Δ Δ
  33. ͷൺֱ Δ ʢఆཧʣ೚ҙͷ ʹ͍ͭͯ    ͕࣋ͭ࠷খͷ సҠࢦ਺ɾࣗݾࢦ਺ w

    ఏҊ͍ͯ͠Δ ͷసҠࢦ਺ɾࣗݾࢦ਺͕Ұ൪খ͍͞ w ˠҰ൪ૣ͍ऩଋΛ্ࣔ͢ք͕ಘΒΕΔ (P, Q) τΔ 𝒱 ≤ τΔPMW ≤ τΔKM + min{ψΔDM , ψΔDM } ψΔ 𝒱 ≤ τΔPMW ≤ min{ψΔDM , ψΔDM } τΔ , ψΔ (P, Q) Δ Δ 𝒱
  34. ࣮ݧ ͷਓ޻σʔλͷ࣮ݧΛ࣮ࢪ wӈਤͷ෼෍ɾճؼؔ਺ w  ධՁࢦඪ wαΠζͷςετσʔληοτ Ͱܭࢉͨ͠࢒༨ޡࠩ 𝒳 =

    ℝ nP ∈ {28,29, . . . ,218}, nQ = 10 ੨ιʔε෼෍ͷີ౓ؔ਺ ᒵλʔήοτ෼෍ͷີ౓ؔ਺ ੺αϙʔτ͕ҟͳΔྖҬ ྘ճؼؔ਺ BMQIB CBUB UBV QTJ 1.8 PS BMQIB ♾  0VS PS BMQIB PS  ඇઈର࿈ଓΑΓ