تجزیه مقادیر منفرد (SVD) — به زبان ساده

۶۷۴۱ بازدید
آخرین به‌روزرسانی: ۱۸ اردیبهشت ۱۴۰۲
زمان مطالعه: ۹ دقیقه
تجزیه مقادیر منفرد (SVD) — به زبان ساده

روش تجزیه مقادیر منفرد یا 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++}$$ مربوط به این گام از فرایند، به صورت زیر است:

1//subroutine header for performing cluster analysis:
2#include "cluster.h"
3//maximum number of clusters:
4#define MAX_CLUSTER 10
5int main(int argc, char **argv) {
6  char *infile;            //input file
7  char *outfile;           //output file
8  FILE *fs;                //file pointer
9  double **a;              //matrix of training data/U
10  int m;                   //number of rows in matrix
11  int n;                   //number of columns in matrix
12  int nsv;                 //number of singular values
13  if (argc!=4) {
14    printf("syntax: cluster_svd nsv train centers\n");
15    printf("  where:\n");
16    printf("nsv      = number of singular values (0 = use untransformed data)\n");
17    printf("infile   = ASCII input file containing training data\n");
18    printf("output   = ASCII output file containing cluster centers\n");
19    printf("\n");
20    printf("file format:\n");
21    printf("- one line header containing number of rows and number of columns\n");
22    printf("- row major list of each matrix element\n");
23    exit(1);
24  }
25  if (sscanf(argv[1], "%d", &nsv)!=1) {
26    fprintf(stderr, "Error parsing first command line argument\n");
27    exit(1);
28  }
29  infile=argv[2];
30  outfile=argv[3];
31  fs=fopen(infile, "r");
32  if (fs==NULL) {
33    fprintf(stderr, "Error opening input file, %s\n", infile);
34    exit(1);
35  }
36  if (fscanf(fs, "%d %d", &m, &n)!=2) {
37    fprintf(stderr, "Format error in input file: %s line 0", infile);
38    exit(1);
39  }
40  if (nsv>n) {
41    fprintf(stderr, "Command line parameter nsv=%d out of range\n", nsv);
42    exit(1);
43  }
44  a=new double *[m];
45  a[0]=new double[m*n];
46  for (int i=1; i<m; i++) a[i]=a[0]+i*n;
47  for (int i=0; i<m; i++) {
48    for (int j=0; j<n; j++) {
49      if (fscanf(fs, "%lg", a[i]+j)!=1) {
50        fprintf(stderr, "Format error in input file, %s, line %d\n", infile, i);
51        exit(1);
52      }
53    }
54  }
55  fclose(fs);

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

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

1#ifndef SVD_H
2#define SVD_H
3//subroutine for singular value decomposition:
4int                       //returns an error code (0 for success)
5     svd (double **a,     //input matrix--replaced by U on output
6                int m,        //number of rows
7                int n,        //number of columns
8                double *s,    //singular values
9                double **vt); //V--right singular vectors
10#endif

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

1  double *ave;
2  double *s;               //singular values
3  double **vt;             //right singular vectors
4  //first we calculate and remove the arithmetic means:
5  ave=new double[n];
6  for (int i=0; i<n; i++) ave[i]=0;
7  for (int i=0; i<m; i++) {
8    for (int j=0; j<n; j++) {
9      ave[j]+=a[i][j];
10    }
11  }
12  for (int i=0; i<n; i++) ave[i]/=m;
13  for (int i=0; i<m; i++) {
14    for (int j=0; j<n; j++) {
15      a[i][j]-=ave[j];
16    }
17  }
18  if (nsv>0) {
19    //make space for singular values:
20    s=new double[n];
21    //make space for right singular vectors:
22    vt=new double *[n];
23    vt[0]=new double[n*n];
24    for (int i=1; i<n; i++) vt[i]=vt[0]+i*n;
25    //perform the decomposition:
26    int err=svd(a, m, n, s, vt);
27    if (err!=0) {
28      fprintf(stderr, "Error in svd subroutine\n");
29      exit(err);
30    }
31  }

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

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

1#ifndef CLUSTER_H
2#define CLUSTER_H
3int                            //returns number of cluster centers
4    cluster (double ** x,      //training vectors
5                int m,         //number of training vectors
6                int n,         //dimension of each vector
7                int max_nc,    //maximum number of cluster centers
8                double **mu);  //returned cluster centers
9#endif

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

1double **mu_p;      //matrix of cluster centers
2  int nc;           //number of cluster centers
3  //make space for cluster centers:
4  mu_p=new double *[MAX_CLUSTER];
5  mu_p[0]=new double[MAX_CLUSTER*n];
6  for (int i=1; i<MAX_CLUSTER; i++) mu_p[i]=mu_p[0]+i*n;
7  if (nsv>0) {
8    //make space for cluster centers:
9    nc=cluster(a, m, nsv, MAX_CLUSTER, mu_p);
10  } else {
11    //make space for cluster centers:
12    nc=cluster(a, m, n, MAX_CLUSTER, mu_p);
13  }
14  if (nc <= 0) {
15    fprintf(stderr, "Cluster algorithm failed");
16    exit(-1);
17  }

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

تبدیل سیستم

یا

تبدیل سیستم

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

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

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

گام چهارم:

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

1  double **mu;        //cluster centers in un-transformed coords
2  //allocate space for the un-transformed cluster centers:
3  mu=new double *[nc];
4  mu[0]=new double[nc*n];
5  for (int i=1; i<nc; i++) mu[i]=mu[0]+i*n;
6  //perform the coordinate transformation:
7  for (int i=0; i<nc; i++) {
8    for (int j=0; j<n; j++) {
9      mu[i][j]=ave[j];
10      if (nsv>0) {
11        for (int k=0; k<nsv; k++) mu[i][j]+=vt[k][j]*s[k]*mu_p[i][k];
12      } else {
13        mu[i][j]+=mu_p[i][j];
14      }
15    }
16  }
17  //write the results to a file:
18  fs=fopen(outfile, "w");
19  if (fs==NULL) {
20    fprintf(stderr, "Error opening output file, %s\n", outfile);
21    exit(1);
22  }
23  fprintf(fs, "%d %d\n", nc, n);
24  for (int i=0; i<nc; i++) {
25    for (int j=0; j<n; j++) fprintf(fs, "%16.8lg", mu[i][j]);
26    fprintf(fs, "\n");
27  }
28  fclose(fs);
29  //clean up:
30  delete [] mu[0];
31  delete [] mu;
32  delete [] mu_p[0];
33  delete [] mu_p;
34  delete [] ave;
35  delete [] a[0];
36  delete [] a;
37  if (nsv>0) {
38    delete [] s;
39    delete [] vt[0];
40    delete [] vt;
41  }
42  return 0;
43}

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

^^

بر اساس رای ۴۴ نفر
آیا این مطلب برای شما مفید بود؟
اگر بازخوردی درباره این مطلب دارید یا پرسشی دارید که بدون پاسخ مانده است، آن را از طریق بخش نظرات مطرح کنید.
منابع:
Stats and Bots
۵ دیدگاه برای «تجزیه مقادیر منفرد (SVD) — به زبان ساده»

بسیار مفید بود فقط همونطور که دوست عزیز دیگه ای هم فرمودن لطفا حداقل در پرانتز واژه های لاتین معادل اصطلاحات رو استفاده کنید. خسته نباشید عالی و کاربردی!

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

مطالب تهیه شده توسط اساتید فرادرس بسیار روان وجالب هستند.تشکر از زحماتتون . اگر اصطلاحات وبرگردان هایی که به فارسی شده ذکر گردندکه برگردان چه کلمه لاتینی است خیلی خوب میشه تا بتوان درکنارآشنایی تحقیق بیشتری روی آن ها انجام داد.

سلام

خیلی مفید و کاربردی بود
یکی از کاربردهای آن در شبیه سازی های داینامیک هست و با کمک svd میشه شبیه سازی های برف یا شن یا حتی اجسام elastic رو انجام داد

برای پیاده سازی این سیستم مطلب شما در فهم svd خیلی کمکم کرد

این واقعا چیزی بود که من بشه نیاز داشتم.
ممنون.

نظر شما چیست؟

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