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

کاهش نویز در یک تصویر

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

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

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

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

با داشتن داده ورودی $X=[x_1,...,x_K],x_i\in {ℝ}^d$ می‌خواهیم دیکشنری $𝐃\in {ℝ}^{d\times n}:D=[d_1,...,d_n]$ و نمایش$𝐑\in {ℝ}^n:R=[r_1,...,r_n]$ را طوری به دست آوریم که $\Vert X-𝐃R{\Vert }_F^2$ هم کمینه و هم تا حد ممکن پراکنده (sparse) باشد. این مسئله به صورت زیر بهینه‌سازی زیر فرمول‌بندی می‌شود:

$\underset{𝐃\in 𝒞,r_i\in {ℝ}^n}{\text{argmin}}\sum _{i=1}^K\Vert x_i-𝐃r_i{\Vert }_2^2+\lambda \Vert r_i{\Vert }_0$، که در آن $𝒞\equiv \{𝐃\in {ℝ}^{d\times n}:\Vert d_i{\Vert }_2\le 1\mathrm{\forall }i=1,...,n\}$، $\lambda >0$

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

مسئله کمینه‌سازی بالا به دلیل ℓ₀-"norm" یک مسئله محدب نیست و حل کردن آن NP-hard است. در بسیاری از مسائل، استفاده از LASSO باعث ایجاد پراکندگی می‌شود و مسئله بالا با ثابت نگه داشتن یکی از متغیرهای $𝐃$ و $𝐑$ به یک مسئله بهینه‌سازی محدب تبدیل می‌شود.

الگوریتم‌ها

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

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

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

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

$\underset{𝐃,R}{\min }\{\Vert X-𝐃R{\Vert }_F^2\}\text{s.t.}\mathrm{\forall }i\Vert r_i{\Vert }_0\le T$

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

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

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

K-SVD

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

$\underset{𝐃,R}{\min }\{\Vert X-𝐃R{\Vert }_F^2\}\text{s.t.}\mathrm{\forall }i\Vert r_i{\Vert }_0\le T_0$

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

$\Vert X-𝐃R{\Vert }_F^2={|X-\sum _{i=1}^K{d}_i{x}_T^i|}_F^2=\Vert E_k-d_k{x}_T^k{\Vert }_F^2$

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

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

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

${𝐃}_i={\text{proj}}_{𝒞}\{{𝐃}_{i-1}-{\delta }_i{\mathrm{\nabla }}_{𝐃}\sum _{i\in S}\Vert x_i-𝐃r_i{\Vert }_2^2+\lambda \Vert r_i{\Vert }_1\}$، که در آن $S$ زیرمجموعه تصادفی‌ای از $\{1...K\}$ و ${\delta }_i$ گرادیان در این گام است.

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

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

$ℒ(𝐃,\mathrm{\Lambda })=\text{tr}((X-𝐃R{)}^T(X-𝐃R))+\sum _{j=1}^n{\lambda }_j\left(\sum _{i=1}^d{𝐃}_{ij}^2-c\right)$، که در آن $c$ یک محدودیت روی نرم اتم‌ها است و ${\lambda }_i$ متغیرهای دوگانه تشکیل‌دهنده ماتریس قطری $\mathrm{\Lambda }$ هستند.

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

$𝒟(\mathrm{\Lambda })=\underset{𝐃}{\min }ℒ(𝐃,\mathrm{\Lambda })=\text{tr}(X^{T}X-X{R}^T(R{R}^T+\mathrm{\Lambda }{)}^{-1}(X{R}^T{)}^T-c\mathrm{\Lambda })$

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

${𝐃}^T=(R{R}^T+\mathrm{\Lambda }{)}^{-1}(X{R}^T{)}^T$

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

LASSO

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

$\underset{r\in {ℝ}^n}{\min }\{\Vert r{\Vert }_1\}\text{subject to}\Vert X-𝐃R{\Vert }_F^2<ϵ$، که در آن $ϵ$ خطای مجاز در LASSO بازسازی‌شده است.

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

$\underset{r\in {ℝ}^n}{\min }\frac{1}{2}\Vert X-𝐃r{\Vert }_F^2+\lambda \Vert r{\Vert }_1$

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

کاربردها

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

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

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

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

• تقریب پراکنده
• PCA پراکنده
• K-SVD
• Matrix factorization
• Neural sparse coding