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
Go言語での実装を通して学ぶ、高速なベクトル検索を支えるクラスタリング技術/fukuokago...
Search
monochromegane
March 11, 2025
Programming
1
220
Go言語での実装を通して学ぶ、高速なベクトル検索を支えるクラスタリング技術/fukuokago-kmeans
2025.03.11 Fukuoka.go#21
https://fukuokago.connpass.com/event/344467/
monochromegane
March 11, 2025
Tweet
Share
More Decks by monochromegane
See All by monochromegane
Go言語での実装を通して学ぶLLMファインチューニングの仕組み / fukuokago22-llm-peft
monochromegane
0
140
不確実性下における目的と手段の統合的探索に向けた連続腕バンディットの応用 / iot70_gp_rff_mab
monochromegane
2
190
なめらかなシステムと運用維持の終わらぬ未来 / dicomo2025_coherently_fittable_system
monochromegane
0
3.7k
ベクトル検索システムの気持ち
monochromegane
37
11k
Go言語でターミナルフレンドリーなAIコマンド、afaを作った/fukuokago20_afa
monochromegane
2
290
多様かつ継続的に変化する環境に適応する情報システム/thesis-defense-presentation
monochromegane
1
1k
Online Nonstationary and Nonlinear Bandits with Recursive Weighted Gaussian Process
monochromegane
0
710
AIを前提とした体験の実現に向けて/toward_ai_based_experiences
monochromegane
2
1.1k
Go言語でMac GPUプログラミング
monochromegane
1
690
Other Decks in Programming
See All in Programming
All About Angular's New Signal Forms
manfredsteyer
PRO
0
140
いま中途半端なSwift 6対応をするより、Default ActorやApproachable Concurrencyを有効にしてからでいいんじゃない?
yimajo
2
410
Django Ninja による API 開発効率化とリプレースの実践
kashewnuts
0
1.3k
チームの境界をブチ抜いていけ
tokai235
0
170
CSC305 Lecture 06
javiergs
PRO
0
230
育てるアーキテクチャ:戦い抜くPythonマイクロサービスの設計と進化戦略
fujidomoe
1
170
ポスターセッション: 「まっすぐ行って、右!」って言ってラズパイカーを動かしたい 〜生成AI × Raspberry Pi Pico × Gradioの試作メモ〜
komofr
0
1.3k
組込みだけじゃない!TinyGo で始める無料クラウド開発入門
otakakot
0
250
After go func(): Goroutines Through a Beginner’s Eye
97vaibhav
0
390
Go言語はstack overflowの夢を見るか?
logica0419
0
270
Web Components で実現する Hotwire とフロントエンドフレームワークの橋渡し / Bridging with Web Components
da1chi
3
2.4k
CSC509 Lecture 03
javiergs
PRO
0
340
Featured
See All Featured
JavaScript: Past, Present, and Future - NDC Porto 2020
reverentgeek
52
5.6k
jQuery: Nuts, Bolts and Bling
dougneiner
65
7.9k
Build The Right Thing And Hit Your Dates
maggiecrowley
37
2.9k
Facilitating Awesome Meetings
lara
56
6.6k
GraphQLの誤解/rethinking-graphql
sonatard
73
11k
The MySQL Ecosystem @ GitHub 2015
samlambert
251
13k
Rails Girls Zürich Keynote
gr2m
95
14k
Scaling GitHub
holman
463
140k
Fashionably flexible responsive web design (full day workshop)
malarkey
407
66k
Creating an realtime collaboration tool: Agile Flush - .NET Oxford
marcduiker
32
2.3k
ピンチをチャンスに:未来をつくるプロダクトロードマップ #pmconf2020
aki_iinuma
127
53k
Refactoring Trust on Your Teams (GOTO; Chicago 2020)
rmw
35
3.2k
Transcript
ࡾ༔հ / Pepabo R&D Institute, GMO Pepabo, Inc. 2025.03.11 Fukuoka.go#21
GoݴޠͰͷ࣮Λ௨ֶͯ͠Ϳ ߴͳϕΫτϧݕࡧΛࢧ͑Δ ΫϥελϦϯάٕज़
1. ͡Ίʹ 2. ϕΫτϧݕࡧΤϯδϯΛࢧ͑ΔΫϥελϦϯάٕज़ 3. GoݴޠͰk-meansΛ࣮͢Δ 4. ධՁ 5. ·ͱΊ
 2 ࣍
1. ͡Ίʹ
• AIͱ֎෦ใͷՍ͚ڮͱͳΔɺRAGʢRetrieval-Augmented Generationʣʹ ද͞ΕΔΑ͏ʹɺඇߏԽσʔλΛϕΫτϧʹมͯ͠ݕࡧ͢ΔɺϕΫτϧ ݕࡧΤϯδϯͷ༗༻ੑ͕ݟ͞Ε͍ͯΔ • ૉͳϕΫτϧݕࡧΤϯδϯɺϕΫτϧू߹͔ΒΫΤϦͱͳΔϕΫτϧͷۙ ʹҐஔ͢Δ෦ू߹ΛಘΔͨΊʹɺू߹ͷશཁૉʹରͯ͠ྨࣅڑͷ ईΛܭࢉ͢Δ •
ݕࡧରͱͳΔϕΫτϧ͕ߴ࣍ݩʢ  ʣ͔ͭσʔλ͕ଟ͍ ʢ  ʣ߹ɺ૯ͨΓͰ࣮༻తͳݕࡧੑೳΛಘΒΕͳ͍ͨΊɺਫ਼ͱ ͷτϨʔυΦϑΛڐ༰ͨ͠ɺۙࣅۙ୳ࡧͷΞϓϩʔν͕࠾༻͞ΕΔ D > 103 N > 104  4 ͡Ίʹʢ1/2ʣ
• ۙࣅۙ୳ࡧΛ࣮ݱ͢ΔϕΫτϧݕࡧΤϯδϯଟ͘ఏҊ͞Ε͍ͯΔ ʢAnnoyɺFaissɺQdrantɺChromaʣ • ҰํͰɺ͜ΕΒͷΤϯδϯͷੑೳΛҾ͖ग़ͨ͢Ίʹɺۙࣅۙ୳ࡧΞϧΰϦ ζϜΛɺѻ͏σʔλͱͷੑΛؚΊͯཧղ͢Δඞཁ͕͋Δ • ͳΜ͔Α͘Θ͔ΒΜ͕IVFPQͰσϑΥϧτύϥϝʔλͰϤγ • ຊൃදͰɺ͡Ίʹදతͳۙࣅۙ୳ࡧΞϧΰϦζϜΛհ͢Δɻ
࣍ʹɺͦ͜Ͱڞ௨ͯ͠࠾༻͞ΕΔΫϥελϦϯάٕज़ʹண͠ɺGoݴޠͰͷ ࣮Λ௨ͯ͠ɺͦͷಛੑΛཧղ͢Δ  5 ͡Ίʹʢ2/2ʣ
2. ߴͳ ϕΫτϧݕࡧΤϯδϯΛࢧ͑Δ ΫϥελϦϯάٕज़
• ϕΫτϧෳͷ͔ΒͳΔҰͭͷʮྔʯ • ͭ·ΓɺൺΔͨΊͷදݱܗࣜͷҰछ • ϕΫτϧಉ࢜ͷൺֱͷई • ϢʔΫϦουڑ:  •
ίαΠϯྨࣅ:  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 ϕΫτϧݕࡧ
• ϕΫτϧू߹  ʹରͯ͠ΫΤϦϕΫτϧ  ͷۙ  ϕΫτϧΛಘ͍ͨ • 
• ૯ͨΓʢBrute forceʣͰɺσʔλ  ͱ࣍ݩ  ʹԠͯ͡ܭࢉྔ͕૿Ճ • ಉ༷ʹɺσʔλαΠζ͕૿Ճ͠ɺϝϞϦ্ͷల։͕ࠔʹͳΔ • ਫ਼ͱͷτϨʔυΦϑΛڐ༰ͯ͠ɺݕࡧͷ্ͱσʔλαΠζͷݮΛਤ Δۙࣅۙ୳ࡧΞϧΰϦζϜ͕ଟ͘ఏҊ͞Ε͍ͯΔ X q k 𝒩 k (q, X) = argminS⊂X,|S|=k ∑ x∈S d(q, x) N D  8 ۙ୳ࡧ
• ϕΫτϧू߹Λ  ݸͷදϕΫτϧ  Ͱදݱ͢Δ • ͜͜ͰͷྔࢠԽɺࢄԽʢάϧʔϐϯάʣͱଊ͑ͯΑ͍ • ϕΫτϧू߹
 ɺදϕΫτϧͷΠϯσοΫεͷू߹ͱͳΓɺ 256ύλʔϯͰ͋ΕϕΫτϧ͋ͨΓ8bitsͰදݱͰ͖Δ • ݕࡧ࣌ʹɺΫΤϦϕΫτϧͷ࠷͍ۙදϕΫτϧΛ୳ͨ͢Ίɺ୳ࡧେ ෯ʹݮͰ͖Δ • ҰํͰྔࢠԽޡࠩʢΫϥελͰͷࠩҟ͕ͳ͍ɺΫϥελॴଐޡΓʣ͕ൃੜ ͠ɺߴ࣍ݩʹͳΔ΄Ͳɺ͜ΕΛ͑ΔͨΊʹඞཁͳදϕΫτϧ͕૿Ճ͢Δ K C = {c1 , …cK } X  9 ϕΫτϧྔࢠԽʢVector Quantization: VQʣ
• ߴ࣍ݩϕΫτϧΛ  ݸͷ࣍ݩαϒϕΫτϧʹׂ͠ɺಠཱͯ͠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  ≃
• PQʹ͓͚ΔݕࡧɺΫΤϦϕΫτϧΛ  αϒϕΫτϧʹׂ͠ɺରԠ͢Δα ϒϕΫτϧू߹ʹ͓͚Δ࠷͍ۙදϕΫτϧͱͷڑΛՃࢉ͢Δ •  • ΫΤϦαϒϕΫτϧͱදαϒϕΫτϧಉ࢜ͷΈ߹ΘͤࣄલʹϧοΫΞο ϓςʔϒϧͱͯ͠ܭࢉՄೳͰ͋ΓɺશϕΫτϧू߹ʹର͢ΔڑܭࢉͷޮԽ
Խ͕ՄೳʢͪΖΜϕΫτϧׂʹΑΔޡࠩ͋Δʣ • ҰํͰɺڑܭࢉશϕΫτϧू߹ͷσʔλ  ճൃੜ͢Δ M d(q, x) = M ∑ m=1 d(q(m), C(m)) N  11 ੵྔࢠԽʢProduct Quantization: PQʣʢ2/2ʣ
• ϕΫτϧू߹Λߥ͘ྨ͠ɺΫϥελ͝ͱʹΠϯσοΫεΛ࡞ • ΫΤϦ࣌ʹɺݕࡧରΛߜΓࠐΜͰݕࡧͰ͖ΔͨΊܭࢉྔͷݮ͕Մೳ • 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
• VQɺPQɺIVFΛ௨ͯ͠ɺσʔλྔͷݮͱݕࡧͷߴԽΛਤΔͨΊͷ४උͱ ͯ͠ɺΫϥελϦϯά͕ߦΘΕ͍ͯΔ͜ͱ͕͔Δ • FaissͰΫϥελϦϯάͱͯ͠k-meansΞϧΰϦζϜ͕ΘΕ͓ͯΓɺߴͳ ࣮ͱͳ͍ͬͯΔͱͷ͜ͱ • GoݴޠͰk-meansͷ࣮ͷߴԽΛ௨ͯ͠ɺͦͷಛੑΛཧղ͢Δ  13
ۙࣅۙ୳ࡧͱΫϥελϦϯάٕज़
3. GoݴޠͰk-meansΛ࣮͢Δ
• k-means ɺڭࢣͳֶ͠शͷҰछͰ͋ΓɺσʔλΛ  ݸͷΫϥελʹׂ͢Δ ΫϥελϦϯάख๏ • ֤Ϋϥελɺͦͷத৺ʢηϯτϩΠυʣΛ࣋ͪɺσʔλ࠷͍ۙηϯτ ϩΠυʹׂΓͯΒΕΔɻ •
ΞϧΰϦζϜɺσʔλͷׂΓͯͱηϯτϩΠυͷߋ৽Λ܁Γฦ͠ɺऩଋ ͢Δ·Ͱ࣮ߦ͞ΕΔɻ K  15 k-means → → ⋯
• ηϯτϩΠυͷσʔλͷׂΓͯͱηϯτϩΠυͷߋ৽ • શσʔλʹରͯ͠ݱࡏͷ֤ηϯτϩΠυͱͷڑΛܭࢉ •  • ࠷͍ۙηϯτϩΠυͷΫϥελ͕͔ΔͷͰɺΫϥελ͝ͱʹσʔλΛ ͠ࠐΉ •
શσʔλͷܭࢉޙʹΫϥελ͝ͱͷσʔλͰ͠ࠐΜͩσʔλΛׂΔ͜ͱ Ͱ৽͍͠ηϯτϩΠυΛಘΔ N × K × D  16 ૉͳ࣮
• ηϯτϩΠυͷσʔλͷׂΓͯͱηϯτϩΠυͷߋ৽  17 ૉͳ࣮
• ઢܗϥΠϒϥϦBLASʢBasic Linear Algebra SubprogramsʣΛར༻͢Δ GonumΛ͏͜ͱͰޮతͳܭࢉ • ϚϧνεϨουSIMDΛۦͯ͠ߦྻܭࢉΛߴԽͯ͘͠ΕΔ • ͨͩ͠ߦྻܗࣜͰҰׅͰॲཧ
͢ΔͨΊϝϞϦͷ༻ྔ େ͖͍ɻ ·ͨΦʔόʔϔουଘࡏ ͢Δʢͣʣ  18 ߴͳ࣮ 9 ⽷⽹ ⎢ ⎥ ⎢ ⎥ ⽸⽺ $ ⽷⽹ ⽸⽺ 9$5 ⽷⽹ ⎢ ⎥ ⎢ ⎥ ⽸⽺
• શσʔλʹରͯ͠ݱࡏͷ֤ηϯτϩΠυͱͷڑΛܭࢉΛҰׅͰΔ •  • ͨͩ͠ɺ  Ͱɺ֤ߦͷฏํϢʔΫϦουڑʢ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 ߴͳ࣮
• Ͱ͖Δ͚ͩGonumΛͬͯߦྻϕΫτϧ୯ҐͰॲཧ • গͳ͘ͱίʔυ্  ʹରԠ͢Δ܁Γฦ͠ফ͑ͨ D  20 ߴͳ࣮
͜ͷลҰׅͰ͏ ·͘Γ͔ͨͬͨ
4. ධՁ
• Gonum࣮ͷk-meansΛ࣮ߦͯ͠୯ ७ͳΫϥελϦϯά͕͏·͍͘͘͜ͱ Λ֬ೝ • x͕ηϯτϩΠυ • ఆ͢ΔΫϥελͷσʔλΛ༧ଌ  22
ՄࢹԽ
• 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Λར༻͢Δ͜ͱͰͷมԽݟ ΒΕͳ͍ɻҰํͰϝϞϦ༻ྔ૿Ճ͢Δ
• 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࣮ͷ༏Ґੑ͕ग़ͨɻ
5. ·ͱΊ
• ࣮༻తͳϕΫτϧݕࡧΤϯδϯΛࢧ͑ΔΫϥελϦϯάٕज़ʹண͠ɺGoݴ ޠͰͷ࣮Λ௨ͯ͠ɺͦͷಛੑΛཧղͨ͠ • ߴԽσʔλαΠζͷݮͷͨΊͷΞϧΰϦζϜΛલఏͱͯ͠ɺ࣮ʹΑͬ ͯɺʹ͕ࠩग़Δ͜ͱ͕Θ͔ͬͨ • ࣍ݩͰߴԽ࣮ͷΦʔόʔϔου͕ߴԽΛଧͪফ͢Մೳੑ͕͋Γɺ ϝϞϦ༻ྔͳͲͷ؍͔Βɺಛʹ࣍ݩద༻͕ՄೳͳPQͳͲͰφΠʔϒ ͳ࣮ͱͷ͍͚༗༻͔͠Εͳ͍͜ͱࣔࠦ͞Εͨ
• ࠓޙPQ͔ΒϕΫτϧݕࡧΤϯδϯͷ։ൃਐΊ͍ͯ͘ • Go ࡾ  26 ·ͱΊ
None