ریاضی , علوم پایه 707 بازدید

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

تجزیه مقادیر منفرد (Singular Value Decomposition) یا SVD با نام‌های مختلفی شناخته می‌شود. این روش، ابتدا به عنوان «تجزیه عامل» (Factor Analysis) نامیده می‌شد. تحلیل مؤلفه‌های اصلی (Principal Component) یا PC و تجزیه توابع متعامد تجربی (Empirical Orthogonal Function) یا EOF نیز از دیگر اصطلاحات نزدیک به این روش است. همه این‌ نام‌ها از نظر مفهوم ریاضی معادل هستند، هرچند در فرایند محاسبه آن‌ها تفاوت‌های زیادی وجود دارد.

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

محاسبات تجزیه مقادیر منفرد

به طور خلاصه می‌توان گفت که تجزیه مقادیر منفرد روشی است که یک ماتریس را به سه ماتریس دیگر تجزیه می‌کند. برای مثال، ماتریس $$A$$ را می‌توان به صورت زیر نوشت:

رابطه (۱)
رابطه (۱)

که در آن:

  • $$A$$ یک ماتریس $$ m \times n $$؛
  • $$U$$ یک ماتریس متعامد $$m \times m$$؛
  • $$S$$ یک ماتریس قطری $$ m \times n$$
  • و $$V$$ یک ماتریس متعامد $$ n \times n$$ است.

شکل بصری ابعاد ماتریس‌ها به صورت زیر است:

ابعاد ماتریس‌ها

ماتریس قطری مقادیر منفرد مربعی نیست، اما شکل آن مشابه $$A$$ است.

شکل زیر نیز، یک نمایش بصری از تجزیه مقادیر منفرد را نشان می‌دهد.

نمایش بصری تجزیه مقادیر منفرد

دلیل آنکه ماتریس آخر به صورت ترانهاده نوشته شده، در ادامه مشخص می‌شود. مفهوم عبارت «متعامد» و نیز دلیل متعامد بودن دو ماتریس کناری را نیز بیان خواهیم کرد.

فرض می‌کنیم $$m \ge n $$ باشد. رابطه ماتریسی (۱) را با استفاده از نمادگذاری سری‌ها بازنویسی می‌کنیم. با نوشتن رابطه ماتریسی به صورت یک سری، اگر هم فرایند محاسبات ساده نشود، همه چیز کاملاً صریح خواهد شد:

سری

توجه کنید که چگونه ماتریس قطری $$S$$ را به یک بردار تبدیل کرده‌ایم و به صورت یک سری نوشته‌ایم. متغیرهای $$\{ s_{i}\}$$ مقادیر تکین یا منفرد نام دارند و معمولاً از بزرگترین به کوچکترین نوشته می‌شوند:‌

مقادیر منفرد

ستون‌های $$U$$، بردارهای منفرد چپ و ستون‌های $$V$$، بردارهای منفرد راست نامیده می‌شوند.

از جبر خطی می‌دانیم $$U$$ و $$V$$ وقتی متعامد هستند که رابطه زیر برقرار باشد:

ماتریس‌های متعامد

که در آن، $$I$$ ماتریس واحد یا همانی است. درایه‌های قطری ماتریس $$I$$، یک هستند و بقیه درایه‌های آن برابر با صفرند. ماتریس $$U$$ فقط در یک جهت متعامد است؛ یعنی نمی‌توان گفت $$ UU^T=I$$.

با استفاده از ویژگی تعامد، می‌توانیم رابطه (۱) را به فرم دو معادله مقدار ویژه بنویسیم:

رابطه (۲)
رابطه (۲)
رابطه (۳)
رابطه (۳)

از آن‌جایی که تعداد سطر‌های $$ A^TA$$ کوچکتر یا مساوی $$AA^T$$ است، یک روند متداول و با محاسبات کمتر، قرار دادن معادله (۳) در یک محاسبه‌گر مقدار ویژه برای یافتن $$V$$ و $$S^2$$ و در نتیجه، یافتن $$U$$ با تصویر کردن $$A$$ در $$V$$ است:

رابطه (۴)
رابطه (۴)

توجه کنید که وقتی $$A$$ ترانهاده شود، مکان $$U$$ و $$V$$ تغییر می‌کند:

ترانهاده A

بنابراین، اگر $$m<n$$ باشد، می‌توانیم ترانهاده $$A$$ را محاسبه کرده، تجزیه را انجام داده، سپس نقش $$U$$ و $$V$$ را تغییر دهیم.

در این حاالت، $$U$$ یک ماتریس مربعی $$m \times m $$ است، زیرا حداکثر $$m$$ مقدار ویژه غیرصفر می‌تواند داشته باشد. در حالی که $$V$$ یک ماتریس $$n \times n$$ است.

مفهوم SVD چیست؟

در بخش قبل، ریاضیات مربوط به SVD را بیان کردیم. اما همان‌طور که متوجه شده‌اید، این ریاضیات درک شهودی از این روش به ما نمی‌دهد.

برای درک شهودی تجزیه مقادیر منفرد، می‌توان ماتریس $$A$$ را به عنوان یک تبدیل خطی در نظر گرفت. این تبدیل را نیز می‌توان به سه زیرتبدیل تجزیه کرد: ۱) چرخش یا دوران ۲) تغییر مقیاس ۳) چرخش. این سه گام متناظر با سه ماتریس $$U$$، $$S$$ و $$V$$ هستند. شکل زیر، این موضوع را به خوبی نشان می‌دهد.

تجزیه مقادیر تکین

در ادامه، در قالب یک مثال ساده دو بعدی با SVD بیشتر آشنا می‌شویم. روندی که بررسی خواهیم کرد، قابل تعمیم به ابعاد بزرگتر است.

مثال عددی

دو بردار دو بعدی $$ \mathbf {x}_1 =(x_1, y_1)$$ و $$ \mathbf {x}_2 =(x_۲, y_۲)$$ را در نظر بگیرید. همان‌‌طور که در شکل زیر نشان داده شده است، می‌توانیم یک بیضی را با قطر بزرگ $$a$$ و قطر کوچک $$b$$ به این دو بردار منطبق کنیم. برای سادگی و کاهش محاسبات، معادلات را با استفاده از جبر ماتریسی می‌نویسیم.

بیضی

معادله بیضی را با اندازه و دوران دلخواه و با کش دادن و چرخش یک دایره واحد می‌نویسیم. فرض کنید $$ \mathbf{x}’ = ( x’ , y’ ) $$ مختصات حاصل باشد که تحت تبدیل زیر قرار گرفته‌ است:

مختصات جدید

که در آن، $$R$$ ماتریس دوران است:‌

ماتریس چزخش

و $$M$$ یک ماتریس قطری است که شامل قطر‌های بزرگ و کوچک بیضی است:

ماتریس M

بردار را در حالت کلی و به صورت جمله به جمله می‌نویسیم:

عبارت جمله به جمله

که در آن، $$m_i$$ برابر با $$i$$اُمین درایه قطری ماتریس $$M$$ است و برای حالت دو بعدی داریم:

بردار دو بعدی

توجه کنید که دوران به صورت ساعتگرد است. زاویه‌ها نسبت به مرجع نیز به صورت پادساعتگرد تعیین می‌شوند.

معادله دایره واحد به صورت زیر است:

معادله دایره واحد

مجموعه‌ $$ \mathbf{x}$$ها را در سطر‌های ماتریس $$X$$ قرار می‌دهیم:

رابطه (۵)
رابطه (۵)

در نهایت، معادله ماتریسی به صورت زیر خواهد بود:

معادله ماتریسی

عبارت اخیر، در حقیقت، بازنویسی معادله (۳) است. اگر $$A$$ را به عنوان مجموعه‌ای از نقاط در نظر بگیریم، آن‌گاه مقادیر منفرد، محورهای یک بیضی برازش شده با کمترین مربعات هستند، در حالی که $$V$$ دوران آن است. ماتریس $$U$$ تصویر هر نقطه در $$A$$ روی محورها است.

کاربردها

مجموع مربعات مقادیر منفرد باید برابر با واریانس کلی در $$A$$ باشد. بنابراین، اندازه هر یک از این مقادیر بیان می‌کند که چه مقدار از واریانس کلی برای هر بردار منفرد محاسبه می‌شود.

به عنوان جایگزین، می‌توان یک SVD بریده را که شامل ۹۹ درصد واریانس است تشکیل داد:

محاسبه ماتریس
رابطه (۶)

که در آن، $$p<n$$ تعداد مقادیر منفردی است که آن‌ها را نگه داشته‌ایم. معمولاً این تعداد کمتر از ۱۰ مقدار منفرد برجسته ($$p = 10 $$) خواهد بود. این، یکی از قابلیت‌های تجزیه مقادیر منفرد برای استخراج حداقل مؤلفه‌ها است.

حل معادلات ماتریسی

با بازنویسی معادله (۱) می‌توانیم دستگاه معادلات خطی را حل کنیم:

دستگاه معادلات ماتریسی
رابطه (۷)

معادلات بالا را می‌توانیم به صورت مجموع سری زیر بنویسیم:

معادلات به صورت سری

این معادلات را می‌توان به ماتریس‌های غیرمربعی تعمیم داد. از آن‌جایی که یک ماتریس $$ m \times n $$ که در آن $$m>n $$ است، تنها $$n$$ مقدار منفرد خواهد داشت، در استفاده از تجزیه مقادیر منفرد، با حل یک ماتریس $$ m \times m $$ معادل با $$n$$ مقدار منفرد مواجه خواهیم بود. برای ماتریس‌های غیرمربعی، معکوس ماتریس با استفاده از تجزیه مقادیر منفرد، برابر با حل معادله معمولی زیر خواهد بود:

معادله
رابطه (8)

این معادله، جواب $$x$$ را که نزدیکترین به مبدأ است و کمترین فاصله را از آن دارد به دست می‌دهد. معادله معمولی، جواب مسئله کمینه‌سازی زیر است:

مسئله کمینه‌سازی
معادله (9)

کاهش داده

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

اگر تعداد و انواع مناسبی از ویژگی‌ها برای حل یک مساله خاص به الگوریتم‌های یادگیری ماشین داده شود، این الگوریتم‌ها به خوبی کار می‌کنند. اما، در صورتی که تعداد ویژگی‌ها (متغیرها) بسیار زیاد باشد، اغلب الگوریتم‌های یادگیری ماشین در حل مسئله دچار مشکل می‌شوند، زیرا با مسئله «داده‌های ابعاد بالا» (High Dimensional Data) مواجه خواهیم بود. در اینجا است که بحث «کاهش ابعاد» (Dimensionality Reduction) مطرح می‌شود.

قبلاً در معادله (۶)، گفتیم که چگونه یک SVD با کاهش تعداد مقادیر تکین می‌تواند یک ماتریس را بسیار دقیق تقریب بزند. از این ویژگی می‌توان برای فشرده‌سازی داده‌ها با فرم‌های کوتاه شده $$U$$، $$S$$ و $$V$$ به جای $$A$$ و برای کاهش متغیر از جایگزینی $$A$$ با $$U$$ استفاده کرد. البته در پایان، بر اساس معادله (۴) باید با ضرب $$S$$ و $$V$$ نتایج را به دستگاه مختصات اصلی تبدیل کرد.

در ادامه، مثالی را درباره این موضوع بیان و برنامه کامپیوتری آن را نیز ارائه می‌کنیم.

مثال کاهش متغیر

فرض کنید ماتریس $$A$$ با ابعاد $$m \times n $$، مجموعه‌ای از داده‌های آموزش را با هر بردار آموزش در هر سطر رابطه (۵)‌ ذخیره می‌کند و $$n$$ طول هر بردار و عددی بسیار بزرگ است.

می‌خواهیم $$A$$ را به الگوریتم خوشه‌بندی وارد کنیم که خروجی آن، یک عدد ثابت از مراکز خوشه است. از آن‌جایی که $$n$$ بسیار بزرگ است، اجرای الگوریتم بسیار طول خواهد کشید یا ناپایدار خواهد شد. بنابراین، تعداد متغیرها را با استفاده از SVD کاهش می‌دهیم. مراحل زیر، فرایند انجام این کار را نشان می‌دهند.

گام اول: خواندن داده‌ها

در ابتدا، باید داده‌ها را برای تکمیل ماتریس $$A$$ بخوانیم. برنامه $$\mathrm{C++}$$ مربوط به این گام از فرایند، به صورت زیر است:

گام دوم:‌ تعریف SVD

از برنامه تجزیه مقدار تکین آماده در فایل هِدِر (header)، $$\mathrm{svd.h}$$ استفاده می‌کنیم:

معمولاً مقادیر تکین، با توجه به نوع ماتریس و بردار مورد استفاده، اغلب پیچیده‌تر از این است. البته این برنامه، برای قرار دادن همه موارد در یک تابع فشرده مناسب است. در ادامه بخش قبل، داریم:‌

گام سوم: تحلیل خوشه

الگوریتم خوشه‌بندی، یک مجموعه از مراکز خوشه $$c$$ را تولید می‌کند، به گونه‌ای که $$ \{ \mu _i ; i \in [1,c] \}$$:

در ادامه، مراکز خوشه‌ها را تعیین می‌کنیم:

از آن‌جایی که الگوریتم خوشه‌بندی از داده‌های آموزش جدید استفاده می‌کند، مراکز خوشه‌ها در سیستم جدید به صورت زیر محاسبه می‌شوند:‌

تبدیل سیستم

یا

تبدیل سیستم

با نوشتن جزء به جزء جملات، داریم:

تبدیل سیستم
رابطه (۱۰)

که در آن، $$p$$ تعداد مختصات‌ها در سیستم کاهش یافته است.

گام چهارم:

در این مرحله، مراکز خوشه را در دستگاه مختصات قبلی ذخیره کرده و سپس، معادله (۱۰) را اعمال می‌کنیم.

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

^^

به عنوان حامی، استارتاپ، محصول و خدمات خود را در انتهای مطالب مرتبط مجله فرادرس معرفی کنید.

telegram
twitter

سید سراج حمیدی

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

بر اساس رای 2 نفر

آیا این مطلب برای شما مفید بود؟

یک نظر ثبت شده در “تجزیه مقادیر منفرد (SVD) — به زبان ساده

نظر شما چیست؟

نشانی ایمیل شما منتشر نخواهد شد. بخش‌های موردنیاز علامت‌گذاری شده‌اند *