Go言語での実装を通して学ぶ、高速なベクトル検索を支えるクラスタリング技術/fukuokago-kmeans

2025.03.11 Fukuoka.go#21
https://fukuokago.connpass.com/event/344467/

Transcript

1. ࡾ୐༔հ / Pepabo R&D Institute, GMO Pepabo, Inc. 2025.03.11 Fukuoka.go#21 GoݴޠͰͷ࣮૷Λ௨ֶͯ͠Ϳ ߴ଎ͳϕΫτϧݕࡧΛࢧ͑Δ ΫϥελϦϯάٕज़
2. 1. ͸͡Ίʹ 2. ϕΫτϧݕࡧΤϯδϯΛࢧ͑ΔΫϥελϦϯάٕज़ 3. GoݴޠͰk-meansΛ࣮૷͢Δ 4. ධՁ 5. ·ͱΊ  2 ໨࣍
3. 1. ͸͡Ίʹ
4. • AIͱ֎෦৘ใͷՍ͚ڮͱͳΔɺRAGʢRetrieval-Augmented Generationʣʹ ୅ද͞ΕΔΑ͏ʹɺඇߏ଄ԽσʔλΛϕΫτϧʹม׵ͯ͠ݕࡧ͢ΔɺϕΫτϧ ݕࡧΤϯδϯͷ༗༻ੑ͕ݟ௚͞Ε͍ͯΔ • ૉ๿ͳϕΫτϧݕࡧΤϯδϯ͸ɺϕΫτϧू߹͔ΒΫΤϦͱͳΔϕΫτϧͷۙ ๣ʹҐஔ͢Δ෦෼ू߹ΛಘΔͨΊʹɺू߹಺ͷશཁૉʹରͯ͠ྨࣅ౓΍ڑ཭ͷ ई౓Λܭࢉ͢Δ • ݕࡧର৅ͱͳΔϕΫτϧ͕ߴ࣍ݩʢ  ʣ͔ͭσʔλ਺͕ଟ͍ ʢ  ʣ৔߹ɺ૯౰ͨΓͰ͸࣮༻తͳݕࡧੑೳΛಘΒΕͳ͍ͨΊɺਫ਼౓ͱ ͷτϨʔυΦϑΛڐ༰ͨ͠ɺۙࣅۙ๣୳ࡧͷΞϓϩʔν͕࠾༻͞ΕΔ D > 103 N > 104  4 ͸͡Ίʹʢ1/2ʣ
5. • ۙࣅۙ๣୳ࡧΛ࣮ݱ͢ΔϕΫτϧݕࡧΤϯδϯ͸਺ଟ͘ఏҊ͞Ε͍ͯΔ ʢAnnoyɺFaissɺQdrantɺChroma౳ʣ • ҰํͰɺ͜ΕΒͷΤϯδϯͷੑೳΛҾ͖ग़ͨ͢Ίʹ͸ɺۙࣅۙ๣୳ࡧΞϧΰϦ ζϜΛɺѻ͏σʔλͱͷ਌࿨ੑΛؚΊͯཧղ͢Δඞཁ͕͋Δ • ͳΜ͔Α͘Θ͔ΒΜ͕IVFPQͰσϑΥϧτύϥϝʔλͰϤγ • ຊൃදͰ͸ɺ͸͡Ίʹ୅දతͳۙࣅۙ๣୳ࡧΞϧΰϦζϜΛ঺հ͢Δɻ ࣍ʹɺͦ͜Ͱڞ௨ͯ͠࠾༻͞ΕΔΫϥελϦϯάٕज़ʹண໨͠ɺGoݴޠͰͷ ࣮૷Λ௨ͯ͠ɺͦͷಛੑΛཧղ͢Δ  5 ͸͡Ίʹʢ2/2ʣ
6. 2. ߴ଎ͳ ϕΫτϧݕࡧΤϯδϯΛࢧ͑Δ ΫϥελϦϯάٕज़
7. • ϕΫτϧ͸ෳ਺ͷ੒෼͔ΒͳΔҰͭͷʮྔʯ • ͭ·Γɺൺ΂ΔͨΊͷදݱܗࣜͷҰछ • ϕΫτϧಉ࢜ͷൺֱͷई౓ • ϢʔΫϦουڑ཭:  • ίαΠϯྨࣅ౓:  d(xi , xj ) = ∥xi − xj ∥2 = D ∑ d=1 (xi,d − xj,d )2 cos(θ) = xi ⋅ xj ∥xi ∥∥xj ∥ = ∑D d=1 xi,d xj,d ∑D d=1 x2 i,d ⋅ ∑D d=1 x2 j,d  7 ϕΫτϧݕࡧ
8. • ϕΫτϧू߹  ʹରͯ͠ΫΤϦϕΫτϧ  ͷۙ๣  ϕΫτϧΛಘ͍ͨ •  • ૯౰ͨΓʢBrute forceʣͰ͸ɺσʔλ਺  ͱ࣍ݩ਺  ʹԠͯ͡ܭࢉྔ͕૿Ճ • ಉ༷ʹɺσʔλαΠζ͕૿Ճ͠ɺϝϞϦ্΁ͷల։͕ࠔ೉ʹͳΔ • ਫ਼౓ͱͷτϨʔυΦϑΛڐ༰ͯ͠ɺݕࡧ଎౓ͷ޲্ͱσʔλαΠζͷ࡟ݮΛਤ Δۙࣅۙ๣୳ࡧΞϧΰϦζϜ͕ଟ͘ఏҊ͞Ε͍ͯΔ X q k 𝒩 k (q, X) = argminS⊂X,|S|=k ∑ x∈S d(q, x) N D  8 ۙ๣୳ࡧ
9. • ϕΫτϧू߹Λ  ݸͷ୅දϕΫτϧ  Ͱදݱ͢Δ • ͜͜ͰͷྔࢠԽ͸ɺ཭ࢄԽʢάϧʔϐϯάʣͱଊ͑ͯΑ͍ • ϕΫτϧू߹  ͸ɺ୅දϕΫτϧͷΠϯσοΫεͷू߹ͱͳΓɺ 256ύλʔϯͰ͋Ε͹ϕΫτϧ͋ͨΓ8bitsͰදݱͰ͖Δ • ݕࡧ࣌ʹ͸ɺΫΤϦϕΫτϧͷ࠷΋͍ۙ୅දϕΫτϧΛ୳ͨ͢Ίɺ୳ࡧ਺΋େ ෯ʹ࡟ݮͰ͖Δ • ҰํͰྔࢠԽޡࠩʢΫϥελ಺Ͱͷࠩҟ͕ͳ͍ɺΫϥελॴଐޡΓ౳ʣ͕ൃੜ ͠ɺߴ࣍ݩʹͳΔ΄Ͳɺ͜ΕΛ཈͑ΔͨΊʹඞཁͳ୅දϕΫτϧ͕૿Ճ͢Δ K C = {c1 , …cK } X  9 ϕΫτϧྔࢠԽʢVector Quantization: VQʣ
10. • ߴ࣍ݩϕΫτϧΛ  ݸͷ௿࣍ݩαϒϕΫτϧʹ෼ׂ͠ɺಠཱͯ͠VQ͢Δ • ͜͜Ͱ௚ੵͱ͸ɺू߹ಉ࢜ͷ૊Έ߹ΘͤͰ৽͍͠ू߹ΛಘΔ͜ͱ •  ࣍ݩϕΫτϧΛ  ຊͷ  ࣍ݩαϒϕΫτϧʹ෼ׂ͠ɺͦΕͧΕͷ VQͰ  ύλʔϯʹྔࢠԽͨ͠ͳΒ͹ɺ  ύλʔϯΛදݱͰ͖Δ M D M = 4 D/M 28 (28)4 = 232  10 ௚ੵྔࢠԽʢProduct Quantization: PQʣʢ1/2ʣ  X ∈ RN×D  X1 ∈ RN×D/M  X2 ∈ RN×D/M  XM ∈ RN×D/M  …  ×  2K/M  2K/M  2K/M  2K  ≃
11. • PQʹ͓͚Δݕࡧ͸ɺΫΤϦϕΫτϧΛ  αϒϕΫτϧʹ෼ׂ͠ɺରԠ͢Δα ϒϕΫτϧू߹ʹ͓͚Δ࠷΋͍ۙ୅දϕΫτϧͱͷڑ཭ΛՃࢉ͢Δ •  • ΫΤϦαϒϕΫτϧͱ୅දαϒϕΫτϧಉ࢜ͷ૊Έ߹Θͤ͸ࣄલʹϧοΫΞο ϓςʔϒϧͱͯ͠ܭࢉՄೳͰ͋ΓɺશϕΫτϧू߹ʹର͢Δڑ཭ܭࢉͷޮ཰Խ Խ͕Մೳʢ΋ͪΖΜϕΫτϧ෼ׂʹΑΔޡࠩ͸͋Δʣ • ҰํͰɺڑ཭ܭࢉ͸શϕΫτϧू߹ͷσʔλ਺  ճ෼ൃੜ͢Δ M d(q, x) = M ∑ m=1 d(q(m), C(m)) N  11 ௚ੵྔࢠԽʢProduct Quantization: PQʣʢ2/2ʣ
12. • ϕΫτϧू߹Λߥ͘෼ྨ͠ɺΫϥελ͝ͱʹΠϯσοΫεΛ࡞੒ • ΫΤϦ࣌ʹɺݕࡧର৅ΛߜΓࠐΜͰݕࡧͰ͖ΔͨΊܭࢉྔͷ࡟ݮ͕Մೳ • PQͱ૊Έ߹ΘͤΔ͜ͱͰɺPQͷશ݅ݕࡧͷ՝୊Λ؇࿨͢Δ  12 సஔΠϯσοΫεʢInVerted File: IVFʣ  X ∈ RN′  ×D  X1 ∈ RN′  ×D/M  X2 ∈ RN′  ×D/M  XM ∈ RN′  ×D/M  …  ×  ≃  X ∈ RN′  ×D  X1 ∈ RN′  ×D/M  X2 ∈ RN′  ×D/M  XM ∈ RN′  ×D/M  …  ×  ≃  X ∈ RN′  ×D  X1 ∈ RN′  ×D/M  X2 ∈ RN′  ×D/M  XM ∈ RN′  ×D/M  …  ×  ≃ ⋮  X ∈ RN×D
13. • VQɺPQɺIVFΛ௨ͯ͠ɺσʔλྔͷ࡟ݮͱݕࡧͷߴ଎ԽΛਤΔͨΊͷ४උͱ ͯ͠ɺΫϥελϦϯά͕ߦΘΕ͍ͯΔ͜ͱ͕෼͔Δ • FaissͰ͸ΫϥελϦϯάͱͯ͠k-meansΞϧΰϦζϜ͕࢖ΘΕ͓ͯΓɺߴ଎ͳ ࣮૷ͱͳ͍ͬͯΔͱͷ͜ͱ • GoݴޠͰk-meansͷ࣮૷ͷߴ଎ԽΛ௨ͯ͠ɺͦͷಛੑΛཧղ͢Δ  13 ۙࣅۙ๣୳ࡧͱΫϥελϦϯάٕज़
14. 3. GoݴޠͰk-meansΛ࣮૷͢Δ
15. • k-means ͸ɺڭࢣͳֶ͠शͷҰछͰ͋ΓɺσʔλΛ  ݸͷΫϥελʹ෼ׂ͢Δ ΫϥελϦϯάख๏ • ֤Ϋϥελ͸ɺͦͷத৺ʢηϯτϩΠυʣΛ࣋ͪɺσʔλ఺͸࠷΋͍ۙηϯτ ϩΠυʹׂΓ౰ͯΒΕΔɻ • ΞϧΰϦζϜ͸ɺσʔλ఺ͷׂΓ౰ͯͱηϯτϩΠυͷߋ৽Λ܁Γฦ͠ɺऩଋ ͢Δ·Ͱ࣮ߦ͞ΕΔɻ K  15 k-means → → ⋯
16. • ηϯτϩΠυ΁ͷσʔλͷׂΓ౰ͯͱηϯτϩΠυͷߋ৽ • શσʔλ఺ʹରͯ͠ݱࡏͷ֤ηϯτϩΠυͱͷڑ཭Λܭࢉ •  • ࠷΋͍ۙηϯτϩΠυͷΫϥελ͕෼͔ΔͷͰɺΫϥελ͝ͱʹσʔλ఺Λ ଍͠ࠐΉ • શσʔλͷܭࢉޙʹΫϥελ͝ͱͷσʔλ਺Ͱ଍͠ࠐΜͩσʔλΛׂΔ͜ͱ Ͱ৽͍͠ηϯτϩΠυΛಘΔ N × K × D  16 ૉ๿ͳ࣮૷
17. • ηϯτϩΠυ΁ͷσʔλͷׂΓ౰ͯͱηϯτϩΠυͷߋ৽  17 ૉ๿ͳ࣮૷
18. • ઢܗ୅਺ϥΠϒϥϦBLASʢBasic Linear Algebra SubprogramsʣΛར༻͢Δ GonumΛ࢖͏͜ͱͰޮ཰తͳܭࢉ΁ • ϚϧνεϨου΍SIMDΛۦ࢖ͯ͠ߦྻܭࢉΛߴ଎Խͯ͘͠ΕΔ • ͨͩ͠ߦྻܗࣜͰҰׅͰॲཧ ͢ΔͨΊϝϞϦͷ࢖༻ྔ͸ େ͖͍ɻ ·ͨΦʔόʔϔου΋ଘࡏ ͢Δʢ͸ͣʣ  18 ߴ଎ͳ࣮૷ 9
    ⽷
    
    
    
    
    
    
    ⽹
    ⎢
    
    
    
    
    
    
     ⎥
    ⎢
    
    
    
    
    
    
     ⎥
    ⽸
    
    
    
    ⽺
    $
    ⽷
    
    
    
    ⽹
    ⽸
    
    
    
    ⽺
    9$5
    ⽷
    
    
    ⽹
    ⎢ 
    
    
     ⎥
    ⎢ 
    
     ⎥
    ⽸
    
    ⽺
19. • શσʔλ఺ʹରͯ͠ݱࡏͷ֤ηϯτϩΠυͱͷڑ཭ΛܭࢉΛҰׅͰ΍Δ •  • ͨͩ͠ɺ  Ͱɺ֤ߦͷฏํϢʔΫϦουڑ཭ʢXC΁ͷ Ճࢉ͸֤ྻɾ֤ߦ΁ͷ܁Γฦ͠ͱͯ͠ߟ͑Δʣ •  Λ࠶ར༻Ͱ͖Δͷ͕خ͍͠ • ηϯτϩΠυͷߋ৽ •  ɻͨͩ͠  ͸֤σʔλ఺͕ͲͷΫϥελʹ ଐ͢Δ͔Λදݱ͢Δߦྻ ∥X − C∥2 2 = ∥X∥2 2 − 2XC⊤ + ∥C∥2 2 ∥X∥2 2 ∈ RN,∥C∥2 2 ∈ RK ∥X∥2 2 C = (diag(E⊤E))−1E⊤X E ∈ RN×K  19 ߴ଎ͳ࣮૷
20. • Ͱ͖Δ͚ͩGonumΛ࢖ͬͯߦྻ΍ϕΫτϧ୯ҐͰॲཧ • গͳ͘ͱ΋ίʔυ্͸  ʹରԠ͢Δ܁Γฦ͠͸ফ͑ͨ D  20 ߴ଎ͳ࣮૷ ͜ͷล΋ҰׅͰ͏ ·͘΍Γ͔ͨͬͨ
21. 4. ධՁ
22. • Gonum࣮૷ͷk-meansΛ࣮ߦͯ͠୯ ७ͳΫϥελϦϯά͕͏·͍͘͘͜ͱ Λ֬ೝ • x͕ηϯτϩΠυ • ૝ఆ͢ΔΫϥελͷσʔλΛ༧ଌ  22 ՄࢹԽ
23. • 10,000ݸͷσʔλϙΠϯτʹ͍ͭͯɺ2࣍ݩͱ1024࣍ݩͷσʔλΛ4Ϋϥελ ʹ෼ྨ͢ΔࡍͷɺॳظԽʢk-means++ʣɾҰճ͋ͨΓͷߋ৽ɾॳظԽΛؚΊ ͨऩଋ·Ͱͷֶशʹ͍ͭͯ؆қͳൺֱΛ࣮ࢪͨ͠  23 ϕϯνϚʔΫʢ1/2ʣ # 2࣍ݩʢ֤ΧςΰϦʹ্͓͍ͯஈ͕φΠʔϒ࣮૷ɺԼஈ͕Gonum࣮૷ʣ ## ॳظԽ BenchmarkNaiveKMeansClusters4Datapoints10000Features2InitKMeansPlusPlus-11 10000 1157458 ns/op 409769 B/op 8 allocs/op BenchmarkLinearAlgebraKMeansClusters4Datapoints10000Features2InitKMeansPlusPlus-11 8242 1535928 ns/op 2748619 B/op 11009 allocs/op ## Ұճ͋ͨΓͷߋ৽ BenchmarkNaiveKMeansClusters4Datapoints10000Features2Iter1-11 9415 1285607 ns/op 192 B/op 6 allocs/op BenchmarkLinearAlgebraKMeansClusters4Datapoints10000Features2Iter1-11 10000 1157688 ns/op 2364080 B/op 10357 allocs/op ## ऩଋ·Ͱͷֶश BenchmarkNaiveKMeansClusters4Datapoints10000Features2InitKMeansPlusPlusTol1e6-11 1606 6893775 ns/op 410593 B/op 33 allocs/op BenchmarkLinearAlgebraKMeansClusters4Datapoints10000Features2InitKMeansPlusPlusTol1e6-11 1900 6157529 ns/op 7579239 B/op 13279 allocs/op • ௿࣍ݩͷΫϥελϦϯάͰ͸ɺ͍ͣΕ΋GonumΛར༻͢Δ͜ͱͰͷมԽ͸ݟ ΒΕͳ͍ɻҰํͰϝϞϦ࢖༻ྔ͸૿Ճ͢Δ
24. • 10,000ݸͷσʔλϙΠϯτʹ͍ͭͯɺ2࣍ݩͱ1024࣍ݩͷσʔλΛ4Ϋϥελ ʹ෼ྨ͢ΔࡍͷɺॳظԽʢk-means++ʣɾҰճ͋ͨΓͷߋ৽ɾॳظԽΛؚΊ ͨऩଋ·Ͱͷֶशʹ͍ͭͯ؆қͳൺֱΛ࣮ࢪͨ͠  24 ϕϯνϚʔΫʢ2/2ʣ # 1024࣍ݩʢ֤ΧςΰϦʹ্͓͍ͯஈ͕φΠʔϒ࣮૷ɺԼஈ͕Gonum࣮૷ʣ ## ॳظԽ BenchmarkNaiveKMeansClusters4Datapoints10000Features1024InitKMeansPlusPlus-11 22 502432970 ns/op 409768 B/op 8 allocs/op BenchmarkLinearAlgebraKMeansClusters4Datapoints10000Features1024InitKMeansPlusPlus-11 720 16233131 ns/op 2499008 B/op 11002 allocs/op ## Ұճ͋ͨΓͷߋ৽ BenchmarkNaiveKMeansClusters4Datapoints10000Features1024Iter1-11 16 639431708 ns/op 32896 B/op 6 allocs/op BenchmarkLinearAlgebraKMeansClusters4Datapoints10000Features1024Iter1-11 639 18590832 ns/op 1932983 B/op 10380 allocs/op ## ऩଋ·Ͱͷֶश BenchmarkNaiveKMeansClusters4Datapoints10000Features1024InitKMeansPlusPlusTol1e6-11 5 2858952383 ns/op 528193 B/op 29 allocs/op BenchmarkLinearAlgebraKMeansClusters4Datapoints10000Features1024InitKMeansPlusPlusTol1e6-11 249 48778582 ns/op 4435664 B/op 12892 allocs/op • ߴ࣍ݩͷΫϥελϦϯάͰ͸ɺ௿࣍ݩʹൺ΂ͯφΠʔϒͳ࣮૷͸100ഒɺ GonumͰ͸10ഒఔ౓ͷมԽͰ͋ΓɺGonum࣮૷ͷ༏Ґੑ͕ग़ͨɻ
25. 5. ·ͱΊ
26. • ࣮༻తͳϕΫτϧݕࡧΤϯδϯΛࢧ͑ΔΫϥελϦϯάٕज़ʹண໨͠ɺGoݴ ޠͰͷ࣮૷Λ௨ͯ͠ɺͦͷಛੑΛཧղͨ͠ • ߴ଎Խ΍σʔλαΠζͷ࡟ݮͷͨΊͷΞϧΰϦζϜΛલఏͱͯ͠ɺ࣮૷ʹΑͬ ͯ΋ɺ଎౓ʹ͕ࠩग़Δ͜ͱ͕Θ͔ͬͨ • ௿࣍ݩͰ͸ߴ଎Խ࣮૷ͷΦʔόʔϔου͕ߴ଎Խ෼Λଧͪফ͢Մೳੑ͕͋Γɺ ϝϞϦ࢖༻ྔͳͲͷ؍఺͔Βɺಛʹ௿࣍ݩద༻͕ՄೳͳPQͳͲͰ͸φΠʔϒ ͳ࣮૷ͱͷ࢖͍෼͚΋༗༻͔΋͠Εͳ͍͜ͱ΋ࣔࠦ͞Εͨ • ࠓޙ͸PQ͔ΒϕΫτϧݕࡧΤϯδϯͷ։ൃ΋ਐΊ͍ͯ͘ • Go ࡾ  26 ·ͱΊ