E-means: 10 برابر سریعتر k-میانگین در از دست دادن مساوی

100000 نقطه داده در 200 خوشه، دو گاوسی عریض و سه نقطه کوچک، بریده شده در یک جعبه، روی یک پس زمینه یکنواخت روشن. Lloyd 1 به روز رسانی در برابر 97 در هر دوره برای e-means دارد.

در طیف وسیعی از مقیاس‌ها و مجموعه‌های داده، e-means در 25 دوره، در 1.2 تا 3 دوره، کمتر از Lloyd's از دست می‌دهد. از انتها به انتها اندازه‌گیری می‌شود، یعنی کاهش ساعت دیواری 10-45× در GPU در مقابل اجرای پیشرفته لوید (Flash-KMeans [2])، و 8-15× در CPU در برابر Faiss [1]. سرعت و کیفیت معمولا با یکدیگر در k-means معامله می شوند، در حالی که e-means هم به سرعت و هم از دست دادن بهتر دست می یابند.

با توجه به مجموعه داده ثابتی از n نقطه X = {x 1 , ... , x n } ⊂ R d و یک عدد صحیح k , مشکل k-means یافتن k مرکز C = (c 1 , ..., c k ) است که میانگین مجذور فاصله بین هر نقطه و نزدیکترین مرکز آن را به حداقل می رساند:

این یک مجموعه داده ایستا است، برخلاف یادگیری کتاب کد در داخل VQ-VAE، که در آن توزیع به خوشه دائما در حال حرکت است.

هدف e-means ارائه یک قانون بهینه سازی مدرن برای مسئله k-means است. ما این پروژه را از مشاهدات زیر شروع کردیم:

برای e-means، ما به‌روزرسانی‌های دسته‌ای کوچک را با میانگین‌های متحرک نمایی [6] انتخاب کردیم، که به نظر ما برای مسئله k-means بسیار کارآمد است. برخلاف رویکردهای کوچک دسته‌ای قبلی، e-means نیازی به تنظیم فراپارامتری ندارد زیرا به طور خودکار اندازه دسته و اندازه گام را با قوانین مقیاس‌بندی تنظیم می‌کند (به تنظیم خودکار فراپارامتر با قوانین مقیاس‌بندی مراجعه کنید).

علاوه بر این، e-means راه‌اندازی اولیه و استراتژی احیای خوشه مرده را بهبود می‌بخشد، نرخ فروپاشی برنامه‌ریزی‌شده کسینوس را اضافه می‌کند و مرحله نهایی‌سازی را معرفی می‌کند که از دست دادن آموزش برای یک جریمه زمان اجرا ناچیز در پایان آموزش را کاهش می‌دهد. e-means بسیار موازی‌پذیر است و دارای هسته‌های تخصصی است که مزیت الگوریتمی آن را به افزایش سرعت ساعت دیواری تبدیل می‌کند.

هر دسته کوچک تعداد و مجموع هر خوشه را به روز می کند. مرکز نسبت آنهاست.

روش های اولیه و نهایی سازی جدید اجرا بر اساس میانگین دوره آخر هر خوشه به پایان می رسد.

مرحله α از α 0 به 0.1 α 0 باز می شود، همانطور که نرخ یادگیری این کار را انجام می دهد.

خوشه هایی با اندازه زیر یک آستانه با تقسیم یک خوشه بزرگ احیا می شوند.

هسته‌های GPU نزدیکترین تخصیص مرکز را ترکیب می‌کنند، و صرفه‌جویی در دوره بالا را به سرعت‌های ساعت دیواری منطبق تبدیل می‌کنند.

قانون به روز رسانی مرکز، جزء اصلی e-means است. هدف این بخش ارائه یک نمای کلی از قوانین به روز رسانی برای خوشه بندی k-means است. همه روش ها برای هر خوشه j یک مجموع S j و تعداد N j از نقاط اختصاص داده شده به آن را حفظ می کنند و مرکز را به عنوان نسبت خود در نظر می گیرند:

آنها فقط در نحوه به روز رسانی S j و N j متفاوت هستند. در زیر، s j و n j نشان دهنده مجموع و تعداد نقاط دسته جاری است که به خوشه j اختصاص داده شده است (اگر هیچ کدام صفر نباشد).

الگوریتم لوید [7] هر نقطه را به نزدیکترین مرکز خود اختصاص می دهد و آمار را از ابتدا با استفاده از مجموعه داده کامل به عنوان دسته جمع آوری می کند:

بنابراین c j میانگین دقیق نقاطی است که در حال حاضر به آن اختصاص داده شده است. هر به روز رسانی هزینه یک پاس کامل از داده ها را دارد و این روش چندین بار تکرار می شود (معمولا 20 تا 50 تکرار).

به روز رسانی MacQueen [3] آمارها را بدون حذف آنها جمع آوری می کند:

بنابراین c j میانگین یکنواخت هر نقطه تخصیص داده شده به خوشه j از شروع آموزش است، از جمله نقاط تخصیص داده شده در موقعیت های مرکزی زودتر، احتمالا ضعیف. این موضوع بعدا توسط Staleness-Reduction Mini-Batch K-Means [8] که یک روش ترکیبی بین k-means و MacQueen است، تا حدی مورد توجه قرار گرفت. آنها سرعت های مهمی را به دست آوردند، اما فقط در تعداد بسیار کمی از خوشه ها.

e-means روی مینی دسته ها کار می کند و این مجموع را با میانگین متحرک نمایی جایگزین می کند:

بنابراین تکالیف قدیمی‌تر با نرخ α فراموش می‌شوند و مرکز به جای کل تاریخ، تکالیف اخیر را دنبال می‌کند. این قانون به‌روزرسانی معمولا برای توزیع‌های متحرک استفاده می‌شود، از این رو برای آموزش VQ-VAE استفاده می‌شود [6]. آنچه ما دریافتیم این است که اگر با سایر اجزای e-means ترکیب شود و هایپرپارامترها به درستی تنظیم شوند، برای مجموعه داده های ثابت نیز بسیار کارآمد است.

پروژه e-means از کار قبلی Hugo Touvron و Hervé Jégou در Meta FAIR شروع شد، که دریافتند k-means کوچک دسته ای با نزول گرادیان می تواند الگوریتم لوید را شکست دهد. در حالی که می‌توانستم این نتایج را بازتولید کنم، متوجه شدم که عملکرد به‌روزرسانی‌های centroid مبتنی بر گرادیان نزولی، برخلاف به‌روزرسانی‌های میانگین متحرک نمایی، در نرخ‌های یادگیری بالا ناپایدار است. من گمان می‌کنم که به این دلیل است که به‌روزرسانی‌های EMA تضمین می‌کنند که مرکز همیشه در بدنه محدب نقاط اختصاص داده شده به آن قرار دارد، در حالی که به‌روزرسانی‌های شیب نزول ممکن است از آن بدنه عبور کنند.

به منظور دستیابی به کمترین تلفات در تعداد ثابتی از دوره‌ها، به‌روزرسانی‌های میانگین متحرک نمایی را انتخاب کردیم، از این رو نام e-mean برای روش ما است.

اگر دسته را روی مجموعه داده کامل تنظیم کنید، B = n و α = 1، N j و S j دقیقا به تعداد و مجموع کل خوشه تبدیل می شوند، بنابراین یک e-mean تکرار دقیقا به یک تکرار لوید تبدیل می شود. Lloyd یک مورد شدید از e-means بدون زمان‌بندی کسینوس در نرخ یادگیری است. با این حال، جستجوی فراپارامتر ما نشان داد که این تنظیم شدید بسیار نابهینه است، که توضیح می‌دهد که چرا e-means تا حد زیادی از لوید بهتر عمل می‌کند. در زیر، تلفات برای هر اندازه دسته B و مرحله α اندازه‌گیری می‌شود: لوید در گوشه‌ای فرود می‌آید، به خوبی خارج از منطقه‌ای که تلفات کمترین است.

این مطالعه فراپارامتر ما را برانگیخت تا قوانین مقیاس بندی را استخراج کنیم که به طور خودکار اندازه دسته بهینه B و اندازه گام α را انتخاب می کنند.

برای درک بهتر اینکه چرا e-means در زمان همگرایی به تلفات بهتری نسبت به لوید می‌رسد، چند آموزش در مورد مجموعه داده‌های اسباب‌بازی ترسیم کردیم تا توانایی آن‌ها را برای فرار از حداقل‌های محلی ارزیابی کنیم. با تکرار آموزش‌های بیش از 200 دانه، متوجه شدیم که e-means در مقایسه با Lloyd در پیکربندی‌های پاتولوژیک بسیار کمتر احتمال دارد.

توضیح ما برای آن این است که مینی‌بچ‌ها به‌روزرسانی‌های پر سر و صدای بیشتری را ارائه می‌کنند که به احتمال زیاد چشم‌انداز بهینه‌سازی را بررسی می‌کنند و از حداقل‌های محلی فرار می‌کنند. لوید، با زیان همیشه رو به کاهش خود، احتمال بیشتری دارد که از حداقل های محلی موجود استفاده کند و هرگز از آنها فرار نکند.

یکی از ویژگی‌های ضروری e-means این است که پزشکان نیازی به تنظیم هیچ فراپارامتر اضافی در مقایسه با الگوریتم لوید ندارند. ما دو قانون مقیاس‌بندی را برای تنظیم اندازه دسته‌ای B و اندازه گام α 0 از ویژگی‌های هر مسئله (n، k، T) تنظیم کردیم و دریافتیم که آنها تعمیم قوی در مجموعه داده‌های دیده نشده و مقیاس‌های مسئله را نشان می‌دهند.

پشیمانی = (MSE با قانون - بهترین MSE در شبکه) / بهترین MSE، میانه بیش از تنظیمات. مجموعه داده های نگهداری شده: SIFT، SPACEV، و مجموعه داده های VIBE [9] arXiv و AG-News. اندازه نگه داشته شده: یک مقدار از n خارج از تناسب و پیش بینی شده است.

ما دو معادله را برای انتخاب دسته پیشنهاد می کنیم، قانون پیش فرض و قانون کیفیت. «قانون کیفیت» توان عملیاتی را با کیفیت خوشه‌بندی بهتر در مقابل قانون «پیش‌فرض» عوض می‌کند. در زیر داده‌های آموزشی را برای قوانین مقیاس‌بندی خود رسم می‌کنیم: اعتبارسنجی MSE در برابر اندازه مرحله α 0 (چپ) و اندازه دسته‌ای B (راست).

مثال اسباب بازی که اهمیت احیای خوشه مرده را نشان می دهد.

مشکل اصلی با mini-batch k-means این است که مستعد خوشه‌های «مرده» است، مرکزهایی که در طول بهینه‌سازی به صفر امتیاز اختصاص داده می‌شوند. این باعث کاهش اندازه مؤثر کتاب کد می شود، که به ویژه برای کتاب های کد بزرگ که امروزه به طور فزاینده ای مورد استفاده قرار می گیرند، مشکل ساز است.

یک کاهش متداول، شروع مجدد خوشه هایی است که زیر یک آستانه اندازه معین قرار می گیرند، همانطور که در EnCodec [10] انجام شد، جایی که مرکزهای مرده به سادگی با نمونه های تصادفی گرفته شده از دسته ورودی جایگزین می شوند. در حالی که این کمک می کند، مشکل را به طور کامل حل نمی کند. به‌جای نمونه‌برداری از نقاط دلخواه از دسته، خوشه‌های مرده را با تقسیم خوشه‌های بزرگ و موجود احیا می‌کنیم: از یک خوشه فعال با احتمالی متناسب با اندازه آن نمونه‌برداری می‌کنیم و آن را به دو قسمت تقسیم می‌کنیم.

ما دریافتیم که این رویکرد، اقتباس شده از Faiss k-means، به طور قابل توجهی در حذف خوشه‌های مرده و حفظ ظرفیت کتاب کد مؤثرتر است.

1 میلیون بردار، k = 16384، 5 دوره، میانگین بیش از 5 دانه. فقط سیاست احیاء متفاوت است. یک خوشه زمانی مرده محسوب می شود که کمتر از ده بردار در پایان به آن اختصاص داده شود، یک هزارم یک خوشه متوسط. عدم تعادل: اندازه های خوشه چقدر ناهموار هستند (1 = همه برابر). از جدول فرسایش احیای کاغذ.

ما e-means را بر روی 24 مجموعه داده و پیکربندی مختلف تعبیه شده و مصنوعی تأیید کردیم (به مقاله مراجعه کنید). برای ویدیو ما 234 پیکربندی از e-means را در برابر k-means اجرا کردیم (16 مجموعه داده، 100k تا 100M نقطه): هر منحنی را در نقشه نتایج کاوش کنید.

اگر از e-means استفاده می کنید، لطفا مقاله را ذکر کنید ( arXiv:2611.09501 ):