GBDT によるクリック率予測を高速化したい #オレシカナイト vol.4

Gradient boosting decision trees (GBDT) を使ってクリック率を予測する場合に使えそうな高速化方法についてお話しました。

Transcript

1. GBDT ʹΑΔ ΫϦοΫ཰༧ଌΛߴ଎Խ͍ͨ͠ ΦϨγΧφΠτ vol.4 2017-11-22 KOMIYA Atsushi
2. ޿ࠂ഑৴࠷దԽ͓͡͞Μۀ
3. @komiya_atsushi
4. ࠓ೔ͷ͓࿩
5. ͍ΘΏΔ “50ms or die” ͱ ݴΘΕ͍ͯΔք۾ʹ͓͚Δ
6. ޿ࠂΫϦοΫ཰ͷ ΦϯϥΠϯɾϦΞϧλΠϜ༧ଌ
7. ※ ػցֶशدΓͷ ࠐΈೖͬͨ࿩͸͠·ͤΜ (ػցֶशΏΔ;Θ੎ͳͷͰͰ͖·ͤΜ)
8. ΫϦοΫ཰Λ༧ଌ͢Δํ๏ (Ұྫ) • ϩδεςΟοΫճؼ • (Field-aware) factorization machines • Gradient boosting decision trees (GBDT)
9. GBDT ʹΑΔ޿ࠂΫϦοΫ཰༧ଌ • Practical Lessons from Predicting Clicks on Ads at Facebook • https://research.fb.com/publications/practical- lessons-from-predicting-clicks-on-ads-at-facebook/ • Using boosted trees for click-through rate prediction for sponsored search (Yandex) • http://wan.poly.edu/KDD2012/forms/workshop/ ADKDD12/doc/a3.pdf
10. GBDT is Կʁ
11. ܾఆ໦ IUUQYHCPPTUSFBEUIFEPDTJPFOMBUFTUNPEFMIUNM
12. GBDT IUUQYHCPPTUSFBEUIFEPDTJPFOMBUFTUNPEFMIUNM
13. (ͱͬͯ΋ࡶʹදݱ͢Δͱ)
 ܾఆ໦Λԣʹͨ͘͞Μ ฒ΂ͨ΋ͷ
14. ୅දతͳ GBDT ͷ࣮૷ • XGBoost (DMLC ⭐9,661) • LightGBM (Microsoft ⭐4,184) • CatBoost (Yandex ⭐2,129)
15. GBDT ͰΫϦοΫ཰༧ଌ
 ͏Ε͍͜͠ͱɾ൵͍͜͠ͱ
16. Կ͕͏Ε͍͠ͷʁ • ༧ଌਫ਼౓͸ͦΕͳΓʹ͍͍Α • n ࣍ͷಛ௃ྔͷަޓ࡞༻Λѻ͑ΔΑ • ʮੑผ x ޿ࠂΧςΰϦʯΈ͍ͨͳಛ௃ྔͷ ૊߹ΘͤΛ༻ҙ͓ͯ͘͠ඞཁ͕ͳ͍ • (n ͸πϦʔͷਂ͞)
17. ޿ࠂΫϦοΫ཰༧ଌͷ࣮ࡍ Ϣʔβ
    " ộ ޿ࠂ
     ޿ࠂ
     ޿ࠂ
     ޿ࠂ
    O ʴ Ϣʔβͷಛ௃ྔ ޿ࠂ͝ͱͷಛ௃ྔ ༧ଌϞσϧ     ộ ޿ࠂ͝ͱʹ
    ༧ଌ
18. ޿ࠂΫϦοΫ཰༧ଌͷ࣮ࡍ Ϣʔβ
    " ộ ޿ࠂ
     ޿ࠂ
     ޿ࠂ
     ޿ࠂ
    O ʴ Ϣʔβͷಛ௃ྔ ޿ࠂ͝ͱͷಛ௃ྔ ༧ଌϞσϧ     ộ ޿ࠂ͝ͱʹ
    ༧ଌ ผʑʹଘࡏ͢ΔϢʔβͷಛ௃ྔͱ
    ޿ࠂͷಛ௃ྔΛΦϯϥΠϯͰ݁߹
    KPJO ͯ͠ಛ௃ϕΫτϧΛ࡞Δ
19. ޿ࠂΫϦοΫ཰༧ଌͷ࣮ࡍ Ϣʔβ
    " ộ ޿ࠂ
     ޿ࠂ
     ޿ࠂ
     ޿ࠂ
    O ʴ Ϣʔβͷಛ௃ྔ ޿ࠂ͝ͱͷಛ௃ྔ ༧ଌϞσϧ     ộ ޿ࠂ͝ͱʹ
    ༧ଌ ݁߹ͨ͠ಛ௃ϕΫτϧΛ
    ༧ଌϞσϧʹ༩͑ͯ݁ՌΛಘΔ
20. Կ͕൵͍͠ͷʁ • ֶश͸ͦΕͳΓʹ͕͔͔࣌ؒΔΑ • ༧ଌ΋ͦΕͳΓʹ͕͔͔࣌ؒΔΑ • πϦʔ਺Λ૿΍͢΄Ͳ (աֶशͷϦεΫ͸͋ Δ͚Ͳ) ਫ਼౓͕ߴ͘ͳΔ • ҰํͰɺ༧ଌʹ͔͔Δ࣌ؒܭࢉྔ͸πϦʔ ਺ʹൺྫͯ͠૿Ճ͢Δ
21. ༧ଌਫ਼౓ͱॲཧ଎౓͸ τϨʔυΦϑؔ܎ʹͳΓ͕ͪ
22. ༧ଌਫ਼౓ΛߴΊΔͨΊʹ΋
 ༧ଌͷॲཧ଎౓ΛߴΊ͍ͨ❗
23. GBDT ʹΑΔΫϦοΫ཰༧ଌͷ ߴ଎ԽΛਤΔ
24. ⚠
25. ͝஫ҙ • ࠓճ͝঺հ͢ΔɺGBDT ʹ͓͚Δ༧ଌॲཧͷ ߴ଎ԽϙΠϯτ͸ɺ޿ࠂࡏݿͷྔɺར༻͢Δ ϋʔυ΢ΣΞ΍ݴޠɺಛ௃ϕΫτϧͷେ͖͞ ͳͲΑͬͯੑೳͷྑ͠ѱ͕͠େ͖͘มΘΔՄ ೳੑ͕͋Γ·͢ • ※ඞͣߴ଎ԽͰ͖Δ͜ͱΛอূ͢Δ΋ͷͰ͸͋ Γ·ͤΜ
26. GBDT ༧ଌॲཧͷߴ଎ԽϙΠϯτ • GBDT ͷ֤πϦʔͷϝϞϦ্Ͱͷදݱํ๏Λ ޻෉͢Δ • ಛ௃ϕΫτϧͷදݱํ๏Λ޻෉͢Δ • ༧ଌͷॲཧखॱʹେ͖͘ӨڹΛ༩͑͏Δ
 ͞ΒͳΔ޻෉Λ͢Δ
27. πϦʔͷϝϞϦ্Ͱͷ දݱํ๏Λ޻෉͢Δ
28. ϕʔεϥΠϯɿφΠʔϒͳ໦ߏ଄ Y<>
    
       Y<>
    
       Y<>
    
    
29. ϕʔεϥΠϯɿφΠʔϒͳ໦ߏ଄ Y<>
    
       Y<>
    
       Y<>
    
     ɾಛ௃ϕΫτϧ্ͷΠϯσΫε
    
    ɾ෼ׂ৚݅ͷ஋
    
    ɾ಺෦ϊʔυ
    PS
    ༿ϊʔυʁ
    ɾࠨͷࢠϊʔυ΁ͷࢀর
    ɾӈͷࢠϊʔυ΁ͷࢀর
30. ϕʔεϥΠϯɿφΠʔϒͳ໦ߏ଄ • ࠨӈͷࢠϊʔυ΁ͷࢀরΛ࣋ͨͳ͚Ε͹
 ͍͚ͳͯ͘৑௕Ͱ͋Δ • ΩϟογϡϝϞϦతʹܾͯ͠๬·͍͠දݱͰ ͸ͳ͍
31. ໦ߏ଄Λϑϥοτͳ഑ྻͰදݱ Y<>
    
       Y<>
    
       Y<>
    
                   ಛ௃ϕΫτϧͷΠϯσΫε ෼ׂ৚݅ͷ஋
    
    ༿ϊʔυͷ஋
32. ໦ߏ଄Λϑϥοτͳ഑ྻͰදݱ • ࢠϊʔυΛͨͲΔํ๏ • ਌ϊʔυͷ഑ྻ্ͷΠϯσΫεΛ i ͱͨ͠ͱ͖ɺࠨͷࢠ ϊʔυ͸ 2 * (i + 1) - 1ɺӈͷࢠϊʔυ͸ 2 * (i + 1) Ͱࢀ রͰ͖Δ • φΠʔϒͳ໦ߏ଄ΑΓ͸ΩϟογϡϝϞϦతʹ༏͍ͩ͠Ζ ͏… • ͳ͓πϦʔ͸ৗʹ׬શೋ෼໦Ͱ͋Δͱ͸ݶΒͳ͍ • Ұ෦ͷαϒπϦʔ͕ࣃൈ͚ʹͳΓ͏Δ͜ͱΛ
 ߟྀ͢Δඞཁ͕͋Δ
33. ωετͨ͠ if - else Ͱίʔυදݱ double predict_tree1(double[] x) { if (x[3] < 5) { if (x[8] < 2) return 9; else return 5; } else { if (x[7] < 3) return 4; else return 7; } }
34. ωετͨ͠ if - else Ͱίʔυදݱ • ωΠςΟϒίʔυʹม׵Ͱ͖Δ / ͞ΕΔݴޠͳΒߴ଎ͳॲཧ͕ ظ଴Ͱ͖Δ • Java ͷ৔߹ͷ͓࿩ • ASM ͳͲΛ࢖ͬͯ GBDT ͷ༧ଌϞσϧΛόΠτίʔυʹ
 ม׵ & ಈతΫϥεϩʔυ → JIT ίϯύΠϧ͕ظ଴Ͱ͖Δ • ҰํͰɺπϦʔͷਂ࣍͞ୈͰ͸ϝιουͷόΠτίʔυαΠ ζ͕େ͖͗ͯ͢ΠϯϥΠϯల։Λ્֐ͯ͠͠·͏͜ͱ΋…
35. ಛ௃ϕΫτϧͷ දݱํ๏Λ޻෉͢Δ
36. ಛ௃ϕΫτϧʹٻΊΒΕΔಛੑ • GBDT Ͱ͸ɺಛ௃ϕΫτϧͷ֤ཁૉͷࢀর͸ϥϯμϜ ΞΫηεʹͳΔ • ϩδεςΟοΫճؼ΍ factorization machines ͱ͸ େ͖͘ҟͳΔ • ΩϟογϡϝϞϦతʹͳ͔ͳ͔͓ਏ͍ײ͡ • ಛ௃ྔΛอ࣋͢Δۭؒޮ཰ͱࢀর࣌ͷॲཧ଎౓ͱͷτ ϨʔυΦϑʹͳΔ
37. ૉ๿ʹ഑ྻͰදݱ͢Δ x = { 3, 0, NaN, 7, 2, NaN, 4 };    OB  OB 
38. ૉ๿ʹ഑ྻͰදݱ͢Δ • ۭؒޮ཰͸ྑ͘ͳ͍͕ɺࢀরੑೳ͸ߴ͍ • ద͍ͯ͠Δέʔε • ಛ௃ϕΫτϧͷ࣍ݩ͕ൺֱతখ͍͞ • ಛ௃ϕΫτϧ͕ൺֱత ີ (dense) Ͱ͋Δ • Missing value ͷѻ͍ʹؾΛ͚ͭΔඞཁ͕͋Δ
39. ࿈૝഑ྻͰදݱ͢Δ x = { 0: 3, 1: 0, 3: 7, 4: 2, 6: 4 }
40. ࿈૝഑ྻͰදݱ͢Δ • ࿈૝഑ྻ: ฏߧ໦΍ϋογϡදʹΑΔ࣮૷ • ۭؒޮ཰͸ͦΕͳΓʹྑ͍ҰํͰɺࢀর࣌ͷΦʔόʔϔο υ͕ؾʹͳΓ͕ͪ • ద͍ͯ͠Δέʔε • ඇৗʹߴ࣍ݩͷಛ௃ϕΫτϧΛѻΘͳ͚Ε͹ͳΒͳ͍ • ͦͷҰํͰɺ࣮ࡍͷಛ௃ϕΫτϧ͸ ૄ (sparse) Ͱ͋Δ
41. AssocVector తͳදݱΛ༻͍Δ J
    W J
    W J
    W J
    W J
    W
42. AssocVector తͳදݱΛ༻͍Δ • ಛ௃ϕΫτϧ্ͷΠϯσΫεͱ஋ͷ૊Λɺ
 ΠϯσΫεͰιʔτͯ͠഑ྻͰอ࣋͢Δ • ࢀর͸ೋ෼୳ࡧͰߦ͏ → O(log N) • ۭؒޮ཰͸࿈૝഑ྻΑΓ༏Ε͍ͯΔ • ΩϟογϡϝϞϦʹ΋༏͍͠දݱͳͷͰ͸…
43. ͞ΒͳΔ޻෉
44. ༧ଌͷॲཧखॱʹӨڹ͢Δ޻෉ • ޿ࠂΫϦοΫ཰ͷ༧ଌ͸ 1 Ϣʔβ 1 ޿ࠂ͚ͩͰࡁΉ Α͏ͳ΋ͷͰ͸ͳ͍ • ͢΂ͯͷ޿ࠂʹ͍ͭͯΫϦοΫ཰Λ༧ଌ͍ͨ͠ • ͦΕͧΕͷ޿ࠂ͝ͱʹஞ࣍తʹ༧ଌͯ͠΋͍͍͕ɺ Ұׅͯ͠༧ଌ͢Δ͜ͱΛલఏͱͯ͠ޮ཰Խ͢Δํ๏ ΋ଘࡏ͢Δ • ͨͩ͠ɺ͔ͳΓखͷࠐΜ࣮ͩ૷ʹͳΓ͕ͪ
45. Ұ࿈ͷ༧ଌʹͯෆมͷಛ௃ྔͰࢬמΓ͢Δ ੑผஉੑʁ   ޿ࠂΧςΰϦήʔϜ   ޿ࠂΧςΰϦԽহ඼ ZFT OP Ϣʔβͷಛ௃ྔ
    உੑ
    ࡀ
    ʜ ͪ͜Β͸ઈରʹḷΒͳ͍
46. Ұ࿈ͷ༧ଌʹͯෆมͷಛ௃ྔͰࢬמΓ͢Δ • ྫ͑͹Ϣʔβͷಛ௃ྔ͸ɺ޿ࠂ͝ͱͷ༧ଌʹ͓͍ ͯ͸ෆมͰ͋Δ • ෆมͷಛ௃ྔʹର͢Δ৚݅ΛຖճධՁ͢Δͷ͸ ແବ • ༧ଌͷલॲཧͱͯ͠ɺͦͷΑ͏ͳ಺෦ϊʔυΛε Ωοϓͯ͠πϦʔΛίϯύΫτʹ͓ͯ͘͠ • લॲཧ෼ͷΦʔόʔϔου͕ੜ͡Δ
47. QuickScorer • ޱ಄Ͱઆ໌͢Δͷ͸ແཧͳͷͰɺ໊લ͚ͩ
 ֮͑ͯޙͰ͙͙͍ͬͯͩ͘͞ • ಛڐग़ئதΒ͍͠ͷͰɺ͝ར༻ʹ͸͝஫ҙΛ
48. ଞʹ΋͍Ζ͍Ζ͋Γ·͕͢… • Google Scholar Ͱ QuickScorer ΛҾ༻ͯ͠ ͍Δ࿦จ΍ؔ࿈هࣄΛ୳͢ͷΛ͓͢͢Ί͠ ·͢
49. ँࣙɾࢀߟจݙ
50. ँࣙɾࢀߟจݙ • ࠓճ͝঺հͨ͠΋ͷͷଟ͘͸ɺಙӬ͞Μ (@tkng) ΑΓΞυόΠε͍͍ͨͩͨ΋ͷʹͳΓ·͢ • Evaluating boosted decision trees for billions of users • https://code.facebook.com/posts/ 975025089299409/evaluating-boosted- decision-trees-for-billions-of-users/
51. Thank you!