پرش به محتوا

یادگیری فرهنگ لغت پراکنده

از ویکی‌پدیا، دانشنامهٔ آزاد
کاهش نویز در یک تصویر

رمزگذاری پراکنده (Sparse Coding) یک روش یادگیری بازنمایی (representational learning) است که سعی بر یافتن نمایش پراکنده‎‌ای از داده‌های ورودی (همچنین شناخته‌ شده به عنوان رمزگذاری پراکنده یا Sparse Coding) به صورت ترکیب خطی‌ای از مولفه‌های تشکیل‌دهنده آن‌ها دارد. به این مولفه‌ها اتم گفته می‌شود و در کنار یکدیگر یک لغت‌نامه (ِdictionary) تشکیل می‌دهند. اتم‌های موجود در هر لغت‌نامه لزوما متعامد نیستند، و ممکن است یک مجموعه پوشای بیش از حد کامل (over-complete spanning set) باشند. شرایط این مسئله همچنین اجازه می‌دهد ابعاد سیگنال‌های نمایش‌داده‌شده از سیگنال‌های مشاهده‌شده بیشتر باشد. این دو ویژگی باعث وجود اتم‌های به‌ظاهر بدون استفاده می‌شوند ولی در عین حال، پراکندگی و انعطاف‌پذیری نمایش را بهبود می‌بخشند.

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

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

صورت‌بندی مسئله

[ویرایش]

با داشتن داده ورودی می‌خواهیم دیکشنری و نمایش را طوری به دست آوریم که هم کمینه و هم تا حد ممکن پراکنده (sparse) باشد. این مسئله به صورت زیر بهینه‌سازی زیر فرمول‌بندی می‌شود:

، که در آن ،

محدودیت ، دیکشنری را طوری محدود می‌کند که اتم‌ها مقادیر بالایی به خود نگیرند و از مقادیر کم ولی غیرصفر جلوگیری شود.

مسئله کمینه‌سازی بالا به دلیل 0-"norm" یک مسئله محدب نیست و حل کردن آن NP-hard است.[۱] در بسیاری از مسائل، استفاده از LASSO باعث ایجاد پراکندگی می‌شود[۲] و مسئله بالا با ثابت نگه داشتن یکی از متغیرهای و به یک مسئله بهینه‌سازی محدب تبدیل می‌شود.

الگوریتم‌ها

[ویرایش]

با وجود اینکه مسئله بهینه‌سازی ذکر شده در بالا می‌تواند به عنوان یک مسئله محدب نسبت به لغت‌نامه یا رمزگذاری پراکنده با ثابت بودن یکی از این دو حل شود، اغلب الگوریتم‌ها بر پایه تصحیح مقدار یکی از مولفه‎‌ها و سپس دیگری به صورت تکرارشونده عمل می‌کنند.

مسئله یافتن رمزگذاری پراکنده بهینه با فرض لغت‌نامه با عنوان تقریب پراکنده شناخته می‌شود. الگوریتم‌هایی مانند تطبیق تعقیب و لسو توسعه داده شده و در الگوریتم‌های توضیح داده شده در پایین‌، به کار گرفته می‌شوند.

روش جهت‌های بهینه (MOD)

[ویرایش]

روش جهت‌های بهینه یا MOD یکی از اولین الگوریتم‌های ایجاد شده برای حل مسئله یادگیری لغت‌نامه پراکنده است.[۳] ایده اصلی این الگوریتم حل کردن مسئله کمینه‌سازی منوط به تعداد محدودی از مولفه‌های غیر صفر از نمایش بردار زیر است:

که در آن، نشان‌دهنده نرم فربنیوس است.

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

MOD یک روش بسیار کارآمد برای داده ورودی با ابعاد کم است و تنها به چند تکرار برای همگرایی نیاز دارد. با این حال، به علت پیچیدگی محاسباتی بالای عملیات وارونگی ماتریس، محاسبه سود وارونه در بسیاری از موارد از نظر محاسباتی دشوار است. این مشکل باعث توسعه‌ یافتن روش‌های دیگر یادگیری دیکشنری پراکنده شده است.

K-SVD الگوریتمی است که در بطن خود از SVD برای تصحیح یک به یک اتم‌های موجود در یک دیکشنری استفاده می‌کند و اساسا تعمیمی از الگوریتم خوشه‌بندی کی-میانگین است.در این الگوریتم، هر مولفه داده ورودی را بر حسب ترکیب خطی از حداکثر مولفه به شیوه مشابه با MOD رمزگذاری می‌شود:

در این الگوریتم، ابتدا دیکشنری ثابت نگه داشته می‌شود و بهترین مقدار متناظر با آن به دست می‌آید، سپس اتم‌های دیکشنری به به صورت زیر به شکل تکرار‌شونده تصحیح می‌شوند:

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

نزول گرادیان تصادفی

[ویرایش]

ایده این الگوریتم، تصحیح دیکشنری به وسیله گرادیان تصادفی مرتبه اول و افکندن آن روی مجموعه محدودیت است.[۴][۵] i-امین گام الگوریتم را می‌توان به صورت زیر نوشت:

، که در آن زیرمجموعه تصادفی‌ای از و گرادیان در این گام است.

روش دوگانه لاگرانژ

[ویرایش]

این الگوریتم بر پایه یک مسئله لاگرانژ دوگانه طراحی شده است و روشی کارآمد برای حل این مسئله است.[۶] لاگرانژی زیر را در نظر بگیرید:

، که در آن یک محدودیت روی نرم اتم‌ها است و متغیرهای دوگانه تشکیل‌دهنده ماتریس قطری هستند.

می‌توانیم دوگانه لاگرانژ را به صورت تحلیلی زیر بنویسیم:

پس از اعمال روش بهینه‌سازی برای مقادیر دوگانه، مقدار به دست می‌آید:

حل کردن این مسئله از لحاظ محاسباتی بسیار ساده‌تر است زیرا تعداد متغیرهای دوگانه از تعداد متغیرهای مسئله اولیه بسیار کمتر است.

در این روش، مسئله بهینه‌سازی به شکل زیر فرمول‌بندی می‌شود:

، که در آن خطای مجاز در LASSO بازسازی‌شده است.

با استفاده از این معادله، مقدار با استفاده از کمینه کردن خطای مربع کمینه با محدودیت L1-norrm در بردار حل به دست می‌آید:

و با حل این معادله، حل بهینه به دست می‌آید.[۷]

کاربردها

[ویرایش]

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

این چارچوب همچنین برای کاهش نویز سیگنال ورودی کاربرد دارد زیرا می‌توان دیکشنری‌ای را به دست آورد که قسمت‌های مهم سیگنال‌ ورودی را به صورت پراکنده نمایش دهد ولی نمایش نویز سیگنال ورودی از پراکندگی بسیار کمتری برخوردار باشد.[۸]

یادگیری دیکشنری پراکنده در بسیاری از زمینه‌های تحلیل صدا و سنتز متن[۹] و دسته‌بندی بدون نظارت استفاده شده است.[۱۰]

جستارهای وابسته

[ویرایش]

منابع

[ویرایش]
  1. A. M. Tillmann, "On the Computational Intractability of Exact and Approximate Dictionary Learning", IEEE Signal Processing Letters 22(1), 2015: 45–49.
  2. Donoho, David L. (2006-06-01). "For most large underdetermined systems of linear equations the minimal 𝓁1-norm solution is also the sparsest solution". Communications on Pure and Applied Mathematics. 59 (6): 797–829. doi:10.1002/cpa.20132. ISSN 1097-0312. S2CID 8510060.
  3. Engan, K.; Aase, S.O.; Hakon Husoy, J. (1999-01-01). Method of optimal directions for frame design. 1999 IEEE International Conference on Acoustics, Speech, and Signal Processing, 1999. Proceedings. Vol. 5. pp. 2443–2446 vol.5. doi:10.1109/ICASSP.1999.760624. ISBN 978-0-7803-5041-0. S2CID 33097614.
  4. Aharon, Michal; Elad, Michael (2008). "Sparse and Redundant Modeling of Image Content Using an Image-Signature-Dictionary". SIAM Journal on Imaging Sciences. 1 (3): 228–247. CiteSeerX 10.1.1.298.6982. doi:10.1137/07070156x.
  5. Pintér, János D. (2000-01-01). Yair Censor and Stavros A. Zenios, Parallel Optimization — Theory, Algorithms, and Applications. Oxford University Press, New York/Oxford, 1997, xxviii+539 pages. (US $ 85.00). Journal of Global Optimization. Vol. 16. pp. 107–108. doi:10.1023/A:1008311628080. ISBN 978-0-19-510062-4. ISSN 0925-5001. S2CID 22475558.
  6. Lee, Honglak, et al. "Efficient sparse coding algorithms." Advances in neural information processing systems. 2006.
  7. Kumar, Abhay; Kataria, Saurabh. "Dictionary Learning Based Applications in Image Processing using Convex Optimisation" (PDF).
  8. Aharon, M, M Elad, and A Bruckstein. 2006. "K-SVD: An Algorithm for Designing Overcomplete Dictionaries for Sparse Representation." Signal Processing, IEEE Transactions on 54 (11): 4311-4322
  9. Peyré, Gabriel (2008-11-06). "Sparse Modeling of Textures" (PDF). Journal of Mathematical Imaging and Vision. 34 (1): 17–31. doi:10.1007/s10851-008-0120-3. ISSN 0924-9907. S2CID 15994546.
  10. Ramirez, Ignacio; Sprechmann, Pablo; Sapiro, Guillermo (2010-01-01). Classification and clustering via dictionary learning with structured incoherence and shared features. 2014 IEEE Conference on Computer Vision and Pattern Recognition. Los Alamitos, CA, USA: IEEE Computer Society. pp. 3501–3508. doi:10.1109/CVPR.2010.5539964. ISBN 978-1-4244-6984-0. S2CID 206591234.