Skip to article frontmatterSkip to article content
Site not loading correctly?

This may be due to an incorrect BASE_URL configuration. See the MyST Documentation for reference.

یادگیری چنده‌گذاری برداری (LVQ)

English · فارسی

یادگیری چنده‌گذاری برداری (LVQ)

گروه علوم کامپیوتر، دانشگاه فردوسی مشهد

جای این صفحه در درس

فصل ۱۳ از hastie2009esl دربارهٔ روش‌های پیش‌نمونه است: به‌جای برازش یک مدل پارامتری، مجموعه‌ای کوچک از نقطه‌ها در فضای ویژگی نگه می‌داریم و بر پایهٔ نزدیکی به آن‌ها دسته‌بندی می‌کنیم. فصل سه نمونه از این‌ها را به ترتیب می‌آورد:

روشپیش‌نمونه‌ها با چه چیزی جای‌گذاری می‌شوندنظارت
خوشه‌بندی K-means (بند ۱۳.۲.۱)هندسهٔ هر کلاس جداگانهبرچسب‌ها فقط بعد از خوشه‌بندی
LVQ (بند ۱۳.۲.۲)هندسهٔ همهٔ کلاس‌ها با همبرچسب‌ها در حین آموزش
مخلوط‌های گاوسی (بند ۱۳.۲.۳)مدل چگالی برای هر کلاسنرم، بر پایهٔ درست‌نمایی

این صفحه بند ۱۳.۲.۲ را دنبال می‌کند. دسته‌بند را بیان می‌کند، الگوریتم را می‌دهد (الگوریتم ۱۳.۱ کتاب)، آن را در چند خط NumPy از صفر پیاده می‌کند، و پیش‌نمونه‌هایی که می‌سازد را با پیش‌نمونه‌های K-means روی همان داده می‌سنجد — همان مقایسه‌ای که کتاب در شکل ۱۳.۱ می‌کند.

در پایان باید بتوانید

  • دسته‌بند نزدیک‌ترین پیش‌نمونه را بیان کنید و بگویید پیش‌نمونه‌ها چه هستند؛

  • قاعدهٔ به‌روزرسانی LVQ1 را از حافظه بنویسید و علامت دو شاخه (جذب/دفع) را توضیح دهید؛

  • توضیح دهید چرا نرخ یادگیری باید به صفر برود، و چرا پیش‌نمونه‌های K-means نقطهٔ آغاز خوبی‌اند؛

  • توصیف کنید پیش‌نمونه‌های K-means در یک تصویر چه تفاوتی با پیش‌نمونه‌های LVQ دارند و چرا این تفاوت نتیجهٔ این است که چه کسی در جای‌گذاری آن‌ها «حرف دارد»؛

  • بهای اینکه روش با یک الگوریتم تعریف شود، نه با کمینه‌سازی یک معیار، را نام ببرید.

۱. دسته‌بند نزدیک‌ترین پیش‌نمونه

تعداد پیش‌نمونهٔ هر کلاس، R، و تعداد کلاس‌ها، K، را ثابت کنید. آموزش K*R پیش‌نمونه m_1, ..., m_{K*R} تولید می‌کند که هر یکی برچسب کلاس c_j دارد. نقطهٔ تازهٔ x با برچسب نزدیک‌ترین پیش‌نمونه دسته‌بندی می‌شود:

G^(x)=cj∗,j∗=arg⁡min⁡j=1,…,KR∥x−mj∥.\hat G(x) = c_{j^*}, \qquad j^* = \arg\min_{j=1,\dots,KR} \lVert x - m_j \rVert .

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

کتاب پیش از به‌کارگیری فاصلهٔ اقلیدسی، ویژگی‌ها را به میانگین ۰ و واریانس ۱ استاندارد می‌کند (ص ۴۶۱)، و ما هم همین کار را می‌کنیم.

۲. مسئله‌ای که LVQ پاسخ می‌دهد

دستور سرراست بند ۱۳.۲.۱ این است: دادهٔ آموزشی هر کلاس را جداگانه با R مرکز خوشه‌بندی کن، همهٔ مرکزها را نگه دار، و با نزدیک‌ترین مرکز دسته‌بندی کن. کار می‌کند، و ضعف دیدنی‌ای دارد که کتاب می‌گوید (ص ۴۶۲):

… پیش‌نمونه‌ها نزدیک مرزهای کلاس‌اند و همین به خطاهای دسته‌بندی برای نقطه‌های نزدیک این > مرزها می‌انجامد. این از کاستی آشکار این روش می‌آید: برای هر کلاس، کلاس‌های دیگر در > جای‌گذاری پیش‌نمونه‌های آن کلاس حرفی برای گفتن ندارند.

پیش‌نمونه‌ای که درون یک کلاس حساب شده هیچ خبری از کلاس همسایه ندارد، پس با خیال راحت روی مرز می‌نشیند. LVQ دقیقاً همین را درست می‌کند: قاعدهٔ به‌روزرسانی برچسب نقطهٔ آموزشی و برچسب نزدیک‌ترین پیش‌نمونه را می‌بیند، پس پیش‌نمونه‌ای که نقطه‌های کلاس اشتباه را می‌برد دفع می‌شود.

۳. یک مسئلهٔ شبیه‌سازی‌شدهٔ سه‌کلاسی

برای دیدن تفاوت به داده‌ای نیاز داریم که کلاس‌هایش به هم برسند، چون با کلاس‌های خوب‌جدا هر روشی یکسان به نظر می‌رسد. شبیه‌سازی بند ۲.۳.۳ از ESL را به کار می‌بریم — همان که پشت شکل ۱۳.۱ است — این بار با سه کلاس به‌جای دو:

  • سه کلاس، دو ویژگی؛

  • هر کلاس ۱۰ میانگین دارد که از توزیع نرمالی با مرکز مختص کلاس — (1.5,0)، (0,1.5) و (1.5,1.5) — و کوواریانس I/4 کشیده شده‌اند؛

  • هر مشاهده با برگزیدن تصادفی یکی از آن ده میانگین (احتمال 1/10) و افزودن نوفهٔ گاوسی با کوواریانس I/5 ساخته می‌شود.

این همان «مدلی میان دو سناریو» در ص ۱۶ است: کلاس‌ها نه خطی‌جداپذیرند و نه دور از هم، و مرز بیز واقعاً خمیده است. پراکندگی ده میانگین (I/4) از I کتاب تنگ‌تر است، که مسئله را سخت نگه می‌دارد بدون آنکه ناامیدکننده کند: حتی یک قاعدهٔ خوب روی کسر قابل‌توجهی از نقطه‌ها خطا می‌کند، ولی هیچ‌جا نزدیک دو-از-سه یک سکهٔ انداختن میان سه کلاس نیست.

Source
Source
((300, 2), array([100, 100, 100]))
Source
<Figure size 600x500 with 1 Axes>

۴. پیش‌نمونه‌های K-means (نقطهٔ آغاز)

R = 5 پیش‌نمونه در هر کلاس، که با خوشه‌بندی جداگانهٔ نقطه‌های هر کلاس ساخته می‌شوند. هر پیش‌نمونه برچسب کلاسی را به ارث می‌برد که در آن حساب شده است.

Source
prototypes: (15, 2)
<Figure size 600x500 with 1 Axes>

۵. الگوریتم LVQ

الگوریتم ۱۳.۱ (یادگیری چنده‌گذاری برداری — LVQ)، به‌صورت چاپ‌شده در hastie2009esl، ص ۴۶۲

  1. برای هر کلاس R پیش‌نمونهٔ آغازین برگزینید m_1^(k), ..., m_R^(k)، k = 1..K — مثلاً با نمونه‌گیری تصادفی R نقطهٔ آموزشی از هر کلاس، یا با اجرای K-means روی هر کلاس.

  2. نقطهٔ آموزشی x_i را به‌طور تصادفی (با جایگذاری) نمونه‌گیری کنید و بگذارید (j,k) نزدیک‌ترین پیش‌نمونه m_j^(k) به x_i را نشان دهد.

    • (a) اگر g_i = k — همان کلاس — پیش‌نمونه را به‌سوی نقطهٔ آموزشی برانید:

      mj(k)←mj(k)+ε (xi−mj(k))m_j^{(k)} \leftarrow m_j^{(k)} + \varepsilon\,(x_i - m_j^{(k)})
    • (b) اگر g_i != k — کلاسی دیگر — پیش‌نمونه را از نقطهٔ آموزشی دور کنید:

      mj(k)←mj(k)−ε (xi−mj(k))m_j^{(k)} \leftarrow m_j^{(k)} - \varepsilon\,(x_i - m_j^{(k)})
  3. گام ۲ را تکرار کنید، و نرخ یادگیری ε را با هر تکرار به‌سوی صفر کم کنید.

سه نکته‌ای که کتاب در پی می‌آورد:

  • LVQ الگوریتمی برخط است: مشاهده‌ها یکی‌یکی می‌رسند و هر یک تنها یک پیش‌نمونه را به‌روز می‌کند.

  • کاهش ε باید شرایط تقریب تصادفی بند ۱۱.۴ را برآورده کند (ε_t -> 0، sum ε_t = infinity، sum ε_t^2 < infinity)؛ برنامه‌ای مانند ε_t = ε_0 / (1 + t) این‌ها را برآورده می‌کند.

  • رویهٔ بالا LVQ1 است؛ گونه‌های دیگر (LVQ2، LVQ3) هم هستند. عیب کل خانواده این است که با یک الگوریتم تعریف می‌شوند، نه با کمینه‌سازی یک معیار ثابت، و همین تحلیل خواصشان را سخت‌تر می‌کند. نسخه‌های تازه‌تر بر پایهٔ تابع هزینه (LVQ تعمیم‌یافته) دقیقاً برای ترمیم همین ساخته شدند.

کتاب جواب K-means را هم به‌عنوان مقدار آغازین به کار می‌برد و نتیجهٔ شکل ۱۳.۱ خود (پنل پایین) را می‌گیرد: پیش‌نمونه‌ها از مرزهای تصمیم فاصله گرفته‌اند و از پیش‌نمونه‌های کلاس‌های رقیب دور شده‌اند.

Source
Source
training error before LVQ: 0.240
training error after  LVQ: 0.170
<Figure size 1200x500 with 2 Axes>

به ستاره‌ها در دو پنل نگاه کنید. در پنل چپ چند پیش‌نمونه درون قلمرو رنگ دیگر نشسته‌اند؛ در پنل راست به منطقهٔ خودشان کشیده و از مرز دور شده‌اند. این تمام اثر علامت در گام ۲ است، که چند هزار بار تکرار شده.

Source
<Figure size 700x400 with 1 Axes>

سنجش «فاصله از مرز»

یک عدد تنها ادعا را آزمودنی می‌کند: برای هر پیش‌نمونه فاصله تا نزدیک‌ترین پیش‌نمونهٔ کلاسی متفاوت را حساب کنید و میانه را بگیرید. LVQ باید آن را زیاد کند، چون پیش‌نمونه‌ای که به دشمن نزدیک است همان است که گام دفع پیوسته می‌زندش.

Source
median distance to the nearest other-class prototype
  before LVQ : 0.800
  after  LVQ : 1.493

۶. آیا روی دادهٔ دیده‌نشده کمک می‌کند؟

پیش‌نمونه‌هایی که نقطه‌های آموزشی را ترک می‌کنند ممکن است نقطه‌های سودمند را هم ترک کنند، پس خطای آموزش به‌تنهایی چیزی ثابت نمی‌کند. آزمون صادقانه نمونهٔ تازه‌ای از همان توزیع است که با دانهٔ دیگری ساختیم.

Source
prototypes              train error  test error
K-means prototypes            0.240       0.277
LVQ1 prototypes               0.170       0.227

عددها چند واحد جابه‌جا می‌شوند، در همان جهتی که کتاب می‌گوید، و اندازهٔ بهبود خودش بخشی از درس است: LVQ یک ترمیم ارزان و محلی برای جواب K-means است، نه یک ردهٔ مدل دیگر. جایی که کلاس‌ها خوب‌جدا هستند تقریباً هیچ چیز را عوض نمی‌کند؛ جایی که هم‌پوشانی دارند مرز را از نو می‌کشد.

۷. نکته‌های عملی

مقدار آغازین. ESL از جواب K-means شروع می‌کند، و در عمل هر کسی هم باید: شروع از نقطه‌های آموزشی تصادفی کار بسیار بیشتری برای به‌روزرسانی‌های برخط باقی می‌گذارد. سلول بعد تفاوت را روی همان داده نشان می‌دهد.

نرخ یادگیری. ε_0 تعیین می‌کند پیش‌نمونه در یک مشاهده چه‌قدر جابه‌جا شود؛ epochs تعیین می‌کند برنامه چه‌قدر ادامه یابد. زیادی بزرگ و پیش‌نمونه‌ها نوسان می‌کنند، زیادی کوچک و هرگز نمی‌رسند. ε_t = ε_0/(1+t) پیش‌فرض ایمنی است.

R، تعداد پیش‌نمونه در هر کلاس. پیش‌نمونهٔ بیشتر مرز ریزتری و مدل بزرگ‌تری می‌دهد؛ R = 1 ‌LVQ را به دسته‌بند نزدیک‌ترین مرکز فرو می‌کاهد و قاعدهٔ به‌روزرسانی را به تصحیحی شبیه پرسپترون روی مرکزها.

مقیاس ویژگی‌ها. فاصلهٔ اقلیدسی بدون آن بی‌معناست؛ همچون ESL با آماره‌های آموزش استاندارد کنید.

نمونه‌گیری با جایگذاری. گام ۲ هر بار نقطهٔ آموزشی تصادفی می‌کشد، نه یک گذر روی فهرست به‌هم‌ریخته، پس کلاس‌های پرنقطه‌تر بیشتر دیده می‌شوند. برای دادهٔ نامتوازن این بایاسی است که خوب است بدانید.

Source
random start, eps0=0.1     test error = 0.250
k-means start, eps0=0.1    test error = 0.227
k-means start, eps0=0.5    test error = 0.207

۸. روی دادهٔ واقعی: گل‌های زنبق

چهار ویژگی، سه کلاس، R = 3 پیش‌نمونه در هر کلاس. وقتی R برابر تعداد کلاس‌ها و داده خوش‌رفتار باشد، پیش‌نمونه‌ها نزدیک میانگین کلاس‌ها می‌افتند، پس LVQ چیز کمی برای ترمیم دارد — و همین دلیل نیاز به مسئلهٔ شبیه‌سازی‌شدهٔ بالا بود تا اثر دیده شود.

Source
nearest centroid (R=1)     test error = 0.244
K-means prototypes (R=3)   test error = 0.000
LVQ1 prototypes (R=3)      test error = 0.000

۹. نام از کجا می‌آید

«چنده‌گذاری» ایدهٔ قدیمی‌تر پشت روش است: یک بردار را با اندیس نزدیک‌ترین پیش‌نمونه جانشین کنید و فقط همان اندیس را ذخیره کنید. با K پیش‌نمونه هر اندیس log2(K) بیت هزینه دارد به‌جای بیت‌های یک بردار کامل، پس مجموعهٔ پیش‌نمونه‌ها کتاب‌کد می‌شود و روش به فشرده‌سازی اتلافی بدل می‌شود.

نام در عنوان LVQ مانده، ولی کاربرد فشرده‌سازی درس دیگری است: از K-means بدون هیچ برچسبی بهره می‌برد و با بیت و دسی‌بل سنجیده می‌شود، نه با نرخ خطا. پس صفحهٔ خودش را دارد:

چنده‌گذاری برداری و فشرده‌سازی تصویر — بند ۱۴.۳.۹ از ESL، با مبادلهٔ نرخ/اعوجاج که روی تصویری آزمونی سنجیده می‌شود.


خلاصه

  • روش پیش‌نمونه با برچسب نزدیک‌ترین پیش‌نمونه دسته‌بندی می‌کند؛ K*R پیش‌نمونه یک مرز تصمیم خمیده را رمزگذاری می‌کند.

  • خوشه‌بندی هر کلاس به‌تنهایی (بند ۱۳.۲.۱) پیش‌نمونه‌ها را جایی می‌گذارد که آن کلاس چگال است، بی‌اعتنا به بقیه، پس روی مرزها می‌لغزند — همان کاستی‌ای که کتاب صریح نامش را می‌برد.

  • LVQ (بند ۱۳.۲.۲) برخط و برچسب‌آگاه است: نقطه نزدیک‌ترین پیش‌نمونهٔ کلاس خودش را جذب و نزدیک‌ترین پیش‌نمونهٔ کلاسی دیگر را دفع می‌کند، با گامی ε که به صفر می‌رسد.

  • این LVQ1 است؛ LVQ2 و LVQ3 گسترشش می‌دهند، و کل خانواده تابع هدف ثابتی ندارد — همان بهای روش.

  • شروع از پیش‌نمونه‌های K-means (انتخاب ESL) بسیار بهتر از شروع از نقطه‌های تصادفی است، و اثر LVQ یک ترمیم محلی مرز است.

  • همان ایدهٔ «نزدیک‌ترین پیش‌نمونه + ذخیرهٔ اندیس»، اگر روی بلوک‌های تصویر به کار رود، چنده‌گذاری برداری است: خاستگاه نام، و روشی فشرده‌ساز که صفحهٔ خودش را دارد.

تمرین‌ها

  1. R = 1 بگذارید و LVQ را روی دادهٔ شبیه‌سازی‌شده اجرا کنید. قاعدهٔ به‌روزرسانی چه می‌شود، و چرا مرز تقریباً مستقیم می‌ماند؟

  2. برنامهٔ ε_t = ε_0/(1+t) را با ثابت ε = 0.1 جانشین کنید. خطای آموزش را برحسب دوره رسم کنید: چه می‌بینید، و کدام یک از سه شرط تقریب تصادفی نقض می‌شود؟

  3. R = 2, 5, 10, 20 پیش‌نمونه در هر کلاس را به کار ببرید و خطای آزمون را رسم کنید. منحنی کجا صاف می‌شود، و هزینهٔ هر پیش‌نمونه چیست؟

  4. گونهٔ فقط‌جذب: شاخهٔ دفع را حذف کنید و از شروع K-means آموزش دهید. نتیجه را با جملهٔ کتاب دربارهٔ اینکه چه کسی در جای‌گذاری پیش‌نمونه‌ها حرف دارد توضیح دهید.

  5. خطای بیز مسئلهٔ شبیه‌سازی‌شده را تحلیلی حساب کنید (یا با مدل 1-NN بسیار بزرگ برآورد کنید) و با خطای دو مجموعهٔ پیش‌نمونه بسنجید.

  6. برای آزمایش فشرده‌سازی، bs = 2 و bs = 8 را با همان تعداد بیت بر پیکسل امتحان کنید. کدام اندازهٔ بلوک تصویر بهتری می‌دهد، و چرا ساختار کاشی در بازسازی دیده می‌شود؟

منابع

  • روش، الگوریتمش (الگوریتم ۱۳.۱) و مثال شبیه‌سازی‌شده: بند ۱۳.۲.۲ و ۱۳.۲ از hastie2009esl (چاپ دوم، صص ۴۶۱–۴۶۳)؛ کاربرد فشرده‌سازی در صفحهٔ خودش است (بند ۱۴.۳.۹ همان کتاب). شکل‌های این صفحه با کد بالا ساخته می‌شوند و مقایسهٔ شکل ۱۳.۱ از ESL را بازتولید می‌کنند.

  • مقاله‌های اصلی LVQ از Kohonen همان ارجاع‌هایی هستند که آنجا داده شده؛ بازفرمول‌بندی GLVQ همان ترمیم بر پایهٔ تابع هزینه برای ایراد «معیار ثابت ندارد» است.

  • مستندات sklearn.cluster.KMeans برای پیاده‌سازی‌ای که پیش‌نمونه‌های آغازین را می‌سازد.