70 жилийн түүхтэй алгоритмыг халсан нь: Meta FAIR 10-45 дахин хурдан "e-means" кластерингийн алгоритмыг танилцууллаа

Компьютерын ухаан, өгөгдлийн шинжилгээ, машин сургалтын хамгийн анхны хичээлүүдийн нэг дээр бид бүгд k-means кластерингийн алгоритмтай танилцдаг. Анх 1957 онд Стюарт Ллойд (Stuart Lloyd) Bell Labs-д ажиллаж байхдаа боловсруулсан Lloyd-ийн алгоритм нь бараг 70 жилийн турш өгөгдлийг бүлэглэх, вектор дүрслэлийг индексжүүлэх суурь багана байсаар ирсэн билээ.

Гэвч LLM, multimodal загварууд болон хэдэн арван тэрбум хэмжээст өгөгдлийн эрин үед энэхүү сонгодог аргачлал том сорилттой тулгарсан юм. Өнөөдөр Meta FAIR (Fundamental AI Research) багийнхан — үүнд LLaMA-г бүтээгчдийн нэг Хюго Туврон (Hugo Touvron) болон алдарт Faiss сангийн удирдагч Маттис Дуз (Matthijs Douze) нар — k-means-ийг сууриар нь шинэчилсэн "e-means" хэмээх шинэ алгоритмаа зарлаж, албан ёсны кодыг нь Faiss санд нэгтгэлээ.

Энэхүү шинэ алгоритм нь уламжлалт k-means-ийн 25 давталт (epoch)-аар хийдэг ажлыг ердөө 1.2–3 давталтад багтаан гүйцэтгэж, GPU дээр 10-45 дахин, CPU дээр 8-15 дахин хурдан ажиллаж байна.

Lloyd-ийн алгоритмын 70 жилийн гацаа юунд байв?

Уламжлалт k-means буюу Lloyd-ийн арга маш энгийн зарчмаар ажилладаг:

Бүх $N$ ширхэг өгөгдлийн цэгийг хамгийн ойр орших төвүүддээ (centroids) хуваарилна.
Хуваарилагдсан цэгүүдийн дунджийг олж, төвийн байршлыг шинэчилнэ.
Энэ үйлдлийг өгөгдөл шилжихээ болих буюу алдаа (MSE) хамгийн бага болох хүртэл давтана.

Энэ арга жижиг хэмжээний өгөгдөлд төгс ажилладаг ч өнөөгийн тэрбум тэрбум embedding вектор бүхий орчинд асар их зардал дагуулдаг. Нэг удаа төвөө шинэчлэхийн тулд нийт өгөгдлийг бүхэлд нь (full-batch) бүтэн унших хэрэгтэй болдог. Түүнчлэн Lloyd-ийн алгоритм алдаагаа байнга бууруулдаг детерминистик шинжтэй тул эхний хэдэн давталтад үүссэн буруу хуваарилалт буюу орон нутгийн экстремумд (local minima) түгжигдэж, түүнээсээ гарч чаддаггүй сул талтай.

Өмнө нь үүнийг шийдэхээр mini-batch k-means (Sculley, 2010) гарч ирсэн боловч сурах хурд (learning rate), багцын хэмжээ (batch size) зэрэг олон тооны гиперпараметрийг гараар тааруулах шаардлага гардаг тул бодит системүүдэд Lloyd-ийг бүрэн шахаж чадаагүй юм.

"e-means" юуг өөрчлөв: EMA ба Хөдөлгөөнт дундаж

Meta FAIR-ийн судлаачид орчин үеийн гүн сургалтын (Deep Learning) оптимизацийн ололтуудыг кластерингт шингээжээ.

e-means алгоритмын гол цөм нь Exponential Moving Average (EMA) буюу экспоненциал хөдөлгөөнт дундаж дээр суурилсан шинэчлэлт юм:

Өгөгдлийг бүхэлд нь уншиж дуусахыг хүлээлгүйгээр жижиг багц (mini-batch) бүрийн дараа кластерын төвүүдийг шууд шинэчилнэ.
Шинэ багц ирэх бүрд хуучин хуваарилалтуудын жинг экспоненциалаар бууруулж, хамгийн сүүлд харсан өгөгдлийн цэгүүдэд давуу эрх олгоно.
Cosine Schedule Decay: Сургалтын явц дуусах дөхөх үед шинэчлэлтийн далайцыг косинусын хуваариар жигд бууруулснаар кластерууд хамгийн оновчтой цэг дээрээ тогтворжино.

Mini-batch-аас үүсэх санамсаргүй чичиргээ (gradient noise) нь төвүүдийг тааруухан орон нутгийн экстремумээс (локал минимум) мултран гарахад тусалдаг. Туршилтаас үзэхэд тэгш бус тархалттай өгөгдөл дээр Lloyd алгоритм кластеруудыг 40 гаруй хувьд нь буруу хуваарилж гацдаг бол e-means ердөө 0–3.5 хувьд л гацаж байв.

Гараар параметр таах шаардлагагүй: "Scaling Laws"

Инженерүүдийн хувьд энэ ажлын хамгийн сайшаалтай хэсэг нь Scaling Laws (Хуваарийн хууль) юм.

Өмнөх mini-batch аргууд шиг "Batch size ямар байх вэ?", "Learning rate-ээ хэдээр авах вэ?" гэж олон хоногоор grid search хийх шаардлагагүй. Судлаачид дараах өгөгдлүүдээс шууд оновчтой параметрүүдийг бодож гаргадаг математик томьёог бэлджээ:

Өгөгдлийн нийт тоо ($N$)
Кластерын тоо ($k$)
Давталтын тоо ($T$)

Энэхүү томьёо нь ямар ч танихгүй шинэ өгөгдлийн санд алдаагүй таарч, Lloyd-ийн k-means-ээс илүү бага алдагдал (lower loss/MSE) зааж чаджээ. Өөрөөр хэлбэл, e-means нь хурдан байгаад зогсохгүй Lloyd-оос ч илүү оновчтой кластер үүсгэдэг.

10 тэрбум вектор, 16 сая кластер: Системүүдэд яагаад чухал вэ?

Өнөөгийн RAG системүүд, вектор өгөгдлийн сангууд (Faiss, pgvector, Milvus, Qdrant) бүгд том хэмжээний вектор хайлтыг хурдасгахын тулд IVF (Inverted File) болон PQ (Product Quantization) индексийг ашигладаг. Энэ хоёр индексийн суурь сургалт нь 100% k-means кластеринг дээр түшиглэдэг юм.

Хамгийн том туршилтын жишээ болгож багийнхан 10 тэрбум embedding-тэй DINO10B датасетийг 16 сая кластерт хуваажээ. Уламжлалт аргаар хэдэн арван өдөр тооцоолох байсан энэ аварга даалгаврыг e-means ердөө 2.5 давталтын дотор, Lloyd-ийн 25 давталт хийснээс ч илүү чанартайгаар гүйцэтгэж дуусгасан байна.

Энэ нь дараах чиглэлүүдэд асар том зардал болон цаг хугацааны хэмнэлт авчирна:

Vector DB индексчлэл: Сая сая хэрэглэгчийн баримтыг индексжүүлж кластер үүсгэх хугацаа 10-40 дахин богиносно.
AI Pre-training өгөгдөл цэвэрлэх: Их хэмжээний текстийг семантик давхардлаас салгах (deduplication) ажил хэдхэн цагийн дотор дуусна.
Загвар шахах ба Quantization: Түгээмэл жин шахалтын (vector quantization) кодын дэвтэр (codebook) сургах хугацаа эрс багасна.

Хөгжүүлэгчид хэрхэн турших вэ?

Meta FAIR багийнхан уг алгоритмыг аль хэдийн нээлттэй эх бүхий faiss санд нэгтгээд байна. Хэрэв та өөрийн төсөлд ашиглахыг хүсвэл хэдхэн мөр кодоор эхлүүлэх боломжтой:

import numpy as np
from faiss.contrib.e_means import Emeans

# Хэмжээс d=128, кластерын тоо k=1024, давталт T=5
em = Emeans(d=128, k=1024, niter=5)

# Сургалт хийх ба векторын кластер хаягуудыг авах
centroids, labels = em.train(vectors)

Компьютерын шинжлэх ухаанд хэдэн арван жилээр хөдөлшгүй мэт оршсон сонгодог суурь алгоритмууд хүртэл орчин үеийн AI архитектур, масштабтай уялдан шинэчлэгдэж эхэлсний хамгийн тод баталгаа нь "e-means" болж байна. Хэрэв та вектор хайлт, кластерингтай ажилладаг бол өнөөдрөөс эхлэн Lloyd-ийг архивлан, шинэ стандартыг туршаад үзээрэй.

Эх сурвалж: Meta FAIR / e-means: outperforming k-means in one-tenth the epochs (arXiv:2611.09501)