trên trang này:
- 1. giới thiệu
- 2. một chút về Đại số tuyến tính
- 2.1. eigenvalues và eigenvectors
- 2.2. hệ thống trực giao và trực giao
- 3.1. khai báo svd
- 3.2. nguồn gốc của tên phân tách giá trị số ít
- 3.3. svd nhỏ gọn
- 3.4. svd bị cắt ngắn
- 3.5. phạm vi tốt nhất (k ) gần đúng
- 4.1. nén hình ảnh
- 4.2. svd bị cắt ngắn cho hệ thống tư vấn
1. giới thiệu
Chắc hẳn bạn vẫn còn nhớ một dạng bài toán được giải nhiều khi học Đại số tuyến tính: bài toán đường chéo hóa ma trận. bài toán nói rằng một ma trận vuông ( mathbf {a} in mathbb {r} ^ {n times n} ) được cho là có thể chéo hóa nếu có một ma trận đường chéo ( mathbf {d} ) và ma trận khả nghịch ( mathbf {p} ) sao cho: [ mathbf {a} = mathbf {p} mathbf {d} mathbf {p} ^ {-1} ~~~~ (1 ) ] số phần tử khác không trong ma trận đường chéo ( mathbf {d} ) là hạng của ma trận ( mathbf {a} ).
nhân cả hai vế của ((1) ) với ( mathbf {p} ) ta được:
[ mathbf {ap} = mathbf {pd} ~~~~ (2) ]
lần lượt gọi ( mathbf {p} _i, mathbf {d} _i ) đến cột thứ (i ) của ma trận ( mathbf {p} ) và ( mathbf {d )} ). vì mỗi cột bên trái và bên phải của ((2) ) phải bằng nhau, chúng ta nhận được:
[ mathbf {ap} _i = mathbf {pd} _i = d_ {ii} mathbf {p} _i ~~~~ (3) ] trong đó (d_ {ii} ) là phần tử (i ) trong số ( mathbf {p} _i ).
dấu bằng thứ hai
xảy ra bởi vì ( mathbf {d} ) là một ma trận đường chéo, nghĩa là ( mathbf {d} _i ) chỉ có một thành phần (d_ {ii} ) khác nhau. 0 và nếu bạn nhớ, biểu thức ((3) ) chỉ ra rằng mỗi phần tử (d_ {ii} ) phải là một giá trị riêng của ( mathbf {a} ) và mỗi vectơ cột ( mathbf {p} _i ) phải là ký tự riêng của ( mathbf {a} ) tương ứng với giá trị riêng (d_ {ii} ).
tính toán một ma trận vuông như ((1) ) còn được gọi là phân tích thích hợp.
một điểm quan trọng là phân tích cú pháp thành ((1) ) chỉ có thể áp dụng cho ma trận vuông và không phải lúc nào cũng tồn tại. chỉ tồn tại nếu ma trận ( mathbf {a} ) có các ký tự đầu (n ) độc lập tuyến tính, vì không có ma trận khả nghịch ( mathbf {p} ) nếu không. hơn nữa, phân tích này không phải là duy nhất vì nếu ( mathbf {p}, mathbf {d} ) thoả mãn ((1) ) thì (k mathbf {p}, mathbf {d} ) cũng thỏa mãn rằng (k ) là bất kỳ số thực nào khác 0.
so sánh ma trận là tích của nhiều ma trận đặc biệt khác (phân tích nhân tử ma trận hoặc phân rã ma trận) mang lại nhiều lợi ích quan trọng mà bạn sẽ thấy: giảm số thứ nguyên dữ liệu, nén dữ liệu, hiểu thuộc tính dữ liệu, giải hệ phương trình tuyến tính, phân nhóm và nhiều ứng dụng khác. hệ thống khuyến nghị cũng là một trong nhiều ứng dụng của phân tích nhân tử ma trận.
Trong bài viết này, tôi sẽ giới thiệu cho bạn một trong những phương pháp nhân tử hóa ma trận rất hay của đại số tuyến tính. phương pháp đó được gọi là phân rã giá trị số ít (svd). như bạn sẽ thấy, bất kỳ ma trận nào, không nhất thiết là hình vuông, đều có thể được phân tích dưới dạng tích của ba ma trận đặc biệt.
Dưới đây, tôi sẽ mô tả svd, cũng như các thuộc tính và ứng dụng điển hình của nó.
Trước hết, chúng ta cần xem lại một chút về Đại số tuyến tính. Lưu ý rằng các mảng trong bài viết này được ngầm định là có thật .
2. một chút về đại số tuyến tính
2.1. eigenvalues và eigenvectors
cho ma trận vuông ( mathbf {a} in mathbb {r} ^ {n times n} ), nếu nó là vô hướng ( lambda ) và vectơ ( mathbf {x) } neq mathbf {0} in mathbb {r} ^ n ) thỏa mãn:
[ mathbf {ax} = lambda mathbf {x} ] thì ( lambda ) được gọi là giá trị riêng của ( mathbf {a} ) và ( mathbf {x} ) được gọi là eigenvector tương ứng với eigenvalue đó.
một số thuộc tính:
-
nếu ( mathbf {x} ) là ký tự riêng của ( mathbf {a} ) tương ứng với ( lambda ) thì (k mathbf {x}, k neq 0 ) cũng là một eigenvector tương ứng với eigenvalue đó.
tất cả các ma trận vuông có thứ tự (n ) có (n ) giá trị riêng (bao gồm cả các lần lặp) và có thể là số phức.
đối với ma trận đối xứng, tất cả các giá trị riêng đều là số thực.
đối với một ma trận xác định dương, tất cả các giá trị riêng của nó là các số thực dương. đối với ma trận bán xác định dương, tất cả các giá trị riêng của nó đều là số thực không âm.
Thuộc tính cuối cùng có thể được suy ra từ định nghĩa của một (nửa) ma trận xác định dương. trên thực tế, hãy để ( mathbf {u} neq mathbf {0} ) là ký hiệu riêng tương ứng với một giá trị riêng ( lambda ) của ma trận ( mathbf {a} ) của định nghĩa dương, chúng tôi có: [ mathbf {au} = lambda mathbf {u} rightarrow mathbf {u} ^ t mathbf {au} = lambda mathbf {u} ^ t mathbf {u} = lambda | | mathbf {u} || _2 ^ 2 ]
vì ( mathbf {a} ) là bán xác định dương, cho tất cả ( mathbf {u} neq mathbf {0} ): ( mathbf {u} ^ t mathbf {au} geq 0 ); ( mathbf {u} neq 0 ) thì (|| mathbf {u} || _2 ^ 2 & gt; 0 ). từ đó nó theo sau rằng ( lambda ) là một số không âm.
2.2. hệ thống trực giao và trực giao
một hệ thống cơ sở ({ mathbf {u} _1, mathbf {u} _2, dot, mathbf {u} _m in mathbb {r} ^ m} ) được cho là trực giao ( trực giao) nếu mỗi vectơ khác không và tích của hai vectơ khác nhau bằng 0:
[ mathbf {u} _i neq mathbf {0}; ~~ mathbf {u} _i ^ t mathbf {u} _j = 0 ~ forall ~ 1 leq i neq j leq m ]
một hệ cơ sở ({ mathbf {u} _1, mathbf {u} _2, dot, mathbf {u} _m in mathbb {r} ^ m} ) được gọi là trực chuẩn (orthonormal) nếu là một hệ trực giao và độ dài Euclide (chuẩn 2) của mỗi vectơ là 1:
[ begin {eqnarray} mathbf {u} _i ^ t mathbf {u} _j = left { begin {array} 1 & amp; text {if} & amp; i = j newline 0 & amp; text {else} end {array} right. ~~~~ (4) end {eqnarray} ]
gọi ( mathbf {u} = [ mathbf {u} _1, mathbf {u} _2, dot, mathbf {u} _m] ) với ({ mathbf {u} _1, mathbf {u} _2, dot, mathbf {u} _m in mathbb {r} ^ m} ) là trực giao, do đó ((4) ) có thể được suy ra ngay lập tức:
[ mathbf {uu} ^ t = mathbf {u} ^ t mathbf {u} = mathbf {i} ]
trong đó ( mathbf {i} ) là một ma trận đơn nhất có bậc (m ). chúng ta gọi ( mathbf {u} ) là ma trận trực giao. các mảng thuộc loại này không được gọi là mảng chính tắc, không có định nghĩa cho mảng chính tắc.
một số thuộc tính:
-
( mathbf {u} ^ {- 1} = mathbf {u} ^ t ): nghịch đảo của ma trận trực giao là chuyển vị của nó.
nếu ( mathbf {u} ) là một ma trận trực giao, thì chuyển vị của nó ( mathbf {u} ^ t ) cũng là một ma trận trực giao.
Định thức của ma trận trực giao là (1 ) hoặc (- 1 ). điều này có thể được suy ra từ ( det ( mathbf {u}) = det ( mathbf {u} ^ t) ) và ( det ( mathbf {u}) det ( mathbf {u} ^ t) = det ( mathbf {i}) = 1 ).
ma trận trực giao biểu diễn chuyển động quay của một vectơ. giả sử có hai vectơ ( mathbf {x, y} in mathbb {r} ^ m ) và một ma trận trực giao ( mathbf {u} in mathbb {r} ^ {m times m} ). chúng tôi sử dụng ma trận này để xoay hai vectơ trên, chúng tôi nhận được ( mathbf {ux}, mathbf {uy} ). tích số chấm của hai vectơ mới là: [( mathbf {ux}) ^ t ( mathbf {uy}) = mathbf {x} ^ t mathbf {u} ^ t mathbf {uy} = mathbf {x} ^ t mathbf {y} ] để phép quay không thay đổi tích số chấm giữa hai vectơ.
giả sử rằng ( hat { mathbf {u}} in mathbb {r} ^ {m times r}, r & lt; m ) là một ma trận con của ma trận trực giao ( mathbf {u } ) được tạo bởi cột (r ) của ( mathbf {u} ), chúng ta nhận được ( hat { mathbf {u}} ^ t hat { mathbf {u}} = mathbf {i} _ {r} ). điều này có thể được suy ra từ ((4) ).
3. phân tách giá trị số ít
Vì trong phần này chúng ta cần biết kích thước của từng mảng, tôi sẽ thay đổi ký hiệu một chút để chúng ta dễ hình dung hơn. chúng ta sẽ biểu thị một ma trận với các kích thước của nó, ví dụ ( mathbf {a} _ {m times n} ) có nghĩa là ma trận ( mathbf {a} in mathbb {r} m times n} ).
3.1. bài phát biểu svd
Mọi ma trận ( mathbf {a} _ {m times n} ) đều có thể được phân tích cú pháp thành:
[ mathbf {a} _ {m times n} = mathbf {u} _ {m times m} mathbf { sigma} _ {m times n} ( mathbf {v} _ {n lần n}) ^ t ~~~~ (5) ]
trong đó, ( mathbf {u}, mathbf {v} ) là ma trận trực giao, ( mathbf { sigma} ) là ma trận đường chéo không vuông với các phần tử trước theo đường chéo ( sigma_1 geq sigma_2 geq dot geq sigma_r geq 0 = 0 = dot = 0 ) và (r ) là thứ hạng của ma trận ( mathbf {a} ). lưu ý rằng mặc dù ( sigma ) không phải là ma trận vuông, chúng ta vẫn có thể coi nó là ma trận đường chéo nếu các thành phần khác không của nó chỉ được đặt theo đường chéo, nghĩa là ở những vị trí chỉ có đường chéo. số hàng và chỉ số cột giống nhau.
số phần tử khác không trong ( sigma ) là thứ hạng của ma trận ( mathbf {a} ).
nếu bạn muốn xem bằng chứng về sự tồn tại của svd, bạn có thể xem nó tại đây.
Lưu ý rằng biểu diễn ((5) ) không phải là duy nhất vì chúng ta chỉ cần thay đổi dấu của cả ( mathbf {u} ) và ( mathbf {v} ) nên (( 5) ) vẫn hài lòng. tuy nhiên, mọi người vẫn sử dụng ‘the svd’ thay vì ‘a svd’.
Hình 1 mô tả svd của ma trận ( mathbf {a} _ {m times n} ) trong hai trường hợp: (m & lt; n ) và (m & gt; n ). trường hợp (m = n ) có thể được phân loại vào một trong hai trường hợp trước.
3.2. tên nguồn gốc phân tách giá trị số ít
Tạm thời bỏ qua thứ nguyên của mỗi mảng, từ (5) ), chúng ta có: [ begin {eqnarray} mathbf {aa} ^ t & amp; = & amp; mathbf {u} mathbf { sigma} mathbf {v} ^ t ( mathbf {u} mathbf { sigma} mathbf {v} ^ t) ^ t newline & amp; = & amp; mathbf {u} mathbf { sigma} mathbf {v} ^ t mathbf {v} mathbf { sigma} ^ t mathbf {u} ^ t newline & amp; = & amp; mathbf {u} mathbf { sigma} mathbf { sigma} ^ t mathbf {u} ^ t = mathbf {u} mathbf { sigma} mathbf { sigma} ^ t mathbf {u } ^ {- 1} ~~~~~ (6) end {eqnarray} ]
dấu bằng
cuối cùng xảy ra vì ( mathbf {v} ^ t mathbf {v} = mathbf {i} ) vì ( mathbf {v} ) là một ma trận trực giao.
Lưu ý rằng ( sigma sigma ^ t ) là ma trận đường chéo với các phần tử đường chéo ( sigma_1 ^ 2, sigma_2 ^ 2, dot ). thì ((6) ) là sự phân rã thích hợp của ( mathbf {a} mathbf {a} ^ t ). hơn nữa, ( sigma_1 ^ 2, sigma_2 ^ 2, dot ) là các giá trị riêng của ( mathbf {a} mathbf {a} ^ t ).
ma trận ( mathbf {a} mathbf {a} ^ t ) luôn là một ma trận bán xác định dương, vì vậy các giá trị riêng của nó không âm. ( sigma_i ) là căn bậc hai của các giá trị riêng của ( mathbf {a} mathbf {a} ^ t ) còn được gọi là các giá trị số ít của ( mathbf {a} ). sự phân hủy giá trị số ít của tên bắt nguồn từ đây.
Ngoài ra, mỗi cột của ( mathbf {u} ) là một ký hiệu riêng của ( mathbf {a} mathbf {a} ^ t ). chúng tôi gọi mỗi cột này là vectơ số ít bên trái của ( mathbf {a} ). Tương tự, ( mathbf {a} ^ t mathbf {a} = mathbf {v} sigma ^ t sigma mathbf {v} ^ t ) và các cột của ( mathbf {v} ) còn được gọi là vectơ số ít thẳng của ( mathbf {a} ).
trong python, để tính toán svd của một mảng, chúng tôi sử dụng mô-đun linalg của numpy như sau:
Lưu ý rằng biến trả về s chỉ bao gồm các phần tử trên đường chéo của ( sigma ). biến v trả về là ( mathbf {v} ^ t ) trong ((5) ).
3.3. svd nhỏ gọn
viết lại biểu thức ((5) ) dưới dạng tổng của ma trận hạng 1: [ mathbf {a} = sigma_1 mathbf {u} _1 mathbf {v} ^ t_1 + sigma_2 mathbf {u} _2 mathbf {v} _2 ^ 2 + điểm + sigma_r mathbf {u} _r mathbf {v} _r ^ t ]
Lưu ý rằng mỗi ( mathbf {u} _1 mathbf {v} ^ t_i, 1 leq i leq r ) là một ma trận có hạng 1.
rõ ràng trong biểu diễn này, ma trận ( mathbf {a} ) chỉ phụ thuộc vào (r ) cột đầu tiên của ( mathbf {u, v} ) và (r) ) thì không – giá trị 0 trên đường chéo của ma trận ( sigma ). vì vậy chúng tôi có cách phân tích cú pháp nhỏ gọn hơn và gọi nó là svd nhỏ gọn:
[ mathbf {a} = { mathbf {u}} _ r { sigma} _r ({ mathbf {v}} _ r) ^ t ]
trong đó ( mathbf {u} _r, mathbf {v} _r ) là ma trận được tạo bởi (r ) cột đầu tiên của ( mathbf {u} ) và (tương ứng. toánbf {v} ). ( sigma_r ) là một ma trận con được tạo bởi (r ) hàng đầu tiên và (r ) cột đầu tiên của ( sigma ). nếu ma trận ( mathbf {a} ) có thứ hạng nhỏ hơn nhiều so với số hàng và cột (r ll m, n ), chúng ta sẽ được lợi rất nhiều về mặt lưu trữ.
Một ví dụ với (m = 4, n = 6, r = 2 ) được hiển thị bên dưới.
3.4. svd bị cắt ngắn
lưu ý rằng trong ma trận ( sigma ), các giá trị của đường chéo không âm và giảm dần ( sigma_1 geq sigma_2 geq dot, geq sigma_r geq 0 = 0 = dấu chấm = 0 ). thông thường chỉ một số nhỏ ( sigma_i ) có giá trị lớn, các giá trị còn lại thường nhỏ và gần bằng 0, vì vậy chúng ta có thể tính gần đúng ma trận ( mathbf {a} ) bằng tổng của ma trận ( mathbf {a} ) của ma trận (k & lt; r ) có hạng 1:
[ mathbf {a} khoảng mathbf {a} _k = mathbf {u} _k sigma_k ( mathbf {v} _k) ^ t = sigma_1 mathbf {u} _1 mathbf {v } ^ t_1 + sigma_2 mathbf {u} _2 mathbf {v} _2 ^ 2 + dot + sigma_k mathbf {u} _k mathbf {v} k ^ t ~~~~ (7) ] dưới cùng đây là một định lý thú vị. định lý này nói rằng sai số do tính gần đúng ở trên là căn bậc hai của tổng bình phương của các giá trị đơn lẻ mà chúng ta bỏ qua ở cuối ( sigma ). ở đây, sai số được định nghĩa là chuẩn xác định của hiệu số của hai ma trận:
lý thuyết: [|| mathbf {a} – mathbf {a} _k || _f ^ 2 = sum_ {i = k + 1} ^ r sigma_i ^ 2 ~ ~~ (8) ]
kiểm tra:
sử dụng các thuộc tính (|| mathbf {x} || _f ^ 2 = text {trace} ( mathbf {x} mathbf {x} ^ t) ) và ( text {trace} ( mathbf {xy}) = text {trace} ( mathbf {yx}) ) cho tất cả các ma trận ( mathbf {x, y} ) chúng ta có:
[ begin {eqnarray} || mathbf {a} – mathbf {a} _k || _f ^ 2 & amp; = & amp; || sum_ {i = k + 1} ^ r sigma_i mathbf {u} _i mathbf {v} _i ^ t || _f ^ 2 & amp; (9) newline & amp; = & amp; text {trace} left { left ( sum_ {i = k + 1} ^ r sigma_i mathbf {u} _i mathbf {v} _i ^ t right) left ( sum_ {j = k + 1} ^ r sigma_j mathbf {u} _j mathbf {v} _j ^ t right) ^ t right } & amp; (10) newline & amp; = & amp; text {trace} left { sum_ {i = k + 1} ^ r sum_ {j = k + 1} ^ r sigma_i sigma_j mathbf {u} _i mathbf {v} _i ^ t mathbf {v} _j mathbf {u} _j ^ t right } & amp; (11) newline & amp; = & amp; text {trace} left { sum_ {i = k + 1} ^ r sigma_i ^ 2 mathbf {u} _i mathbf {u} _i ^ t right } & amp; (12) newline & amp; = & amp; text {trace} left { sum_ {i = k + 1} ^ r sigma_i ^ 2 mathbf {u} _i ^ t mathbf {u} _i right } & amp; (13) newline & amp; = & amp; text {trace} left { sum_ {i = k + 1} ^ r sigma_i ^ 2 right } & amp; (14) newline & amp; = & amp; sum_ {i = k + 1} ^ r sigma_i ^ 2 & amp; (15) end {eqnarray} ]
Dấu bằng
trong ((12) ) là vì ( mathbf {v} ) là một ma trận trực giao (xem ((4) )).
dấu bằng
trong ((13) ) là do hàm ( text {trace} ) có tính chất giao hoán.
Dấu bằng trong ((15) ) là do biểu thức trong ngoặc đơn cho ((14) ) là một đại lượng vô hướng.
thay thế (k = 0 ) ta được: [|| mathbf {a} || _f ^ 2 = sum_ {i = 1} ^ r sigma_i ^ 2 ~~~~ (16) ]
từ đó:
[ frac {|| mathbf {a} – mathbf {a} _k || _f ^ 2} {|| mathbf {a} || _f ^ 2} = { frac { sum_ { i = k + 1} ^ r sigma_i ^ 2} { sum_ {j = 1} ^ r sigma_j ^ 2}} ~~~~ (17) ]
do đó, sai số khi tính gần đúng sẽ nhỏ hơn nếu phần giá trị số ít bị cắt bớt nhỏ hơn phần giá trị số ít được giữ lại. đây là một định lý quan trọng để giúp xác định ma trận xấp xỉ dựa trên lượng thông tin bạn muốn giữ lại.
ví dụ: nếu chúng tôi muốn giữ ít nhất 90% thông tin trong ( mathbf {a} ), trước tiên chúng tôi tính toán ( sum_ {j = 1} ^ r sigma_j ^ 2 ), sau đó chọn (k ) là số nhỏ nhất sao cho:
[ frac { sum_ {i = 1} ^ k sigma_i ^ 2} { sum_ {j = 1} ^ r sigma_j ^ 2} geq 0.9 ]
khi (k ) nhỏ, ma trận ( mathbf {a} _k ) có hạng (k ), là một ma trận có hạng nhỏ. do đó, svd bị cắt ngắn cũng được coi là một phương pháp gần đúng phạm vi thấp.
3.5. khoảng gần đúng nhất (k )
có thể chỉ ra rằng (phân tách giá trị đơn lẻ – Princeton) ( mathbf {a} _k ) là giải pháp của bài toán tối ưu hóa:
[ begin {eqnarray} min _ { mathbf {b}} & amp; & amp; || mathbf {a} – mathbf {b} || _f newline text {s.t.} & amp; & amp; text {range} ( mathbf {b}) = k ~~~~~~~~~~~~~~~ (17) end {eqnarray} ]
và như được hiển thị ở trên (|| mathbf {a} – mathbf {a} _k || _f ^ 2 = sum_ {i = k + 1} ^ r sigma_i ^ 2 ).
nếu chúng ta sử dụng tiêu chuẩn 2 của ma trận thay vì tiêu chuẩn frobenius để đo lỗi, ( mathbf {a} _k ) cũng là giải pháp của bài toán tối ưu hóa:
[ begin {eqnarray} min _ { mathbf {b}} & amp; & amp; || mathbf {a} – mathbf {b} || _2 newline text {s.t.} & amp; & amp; text {range} ( mathbf {b}) = k ~~~~~~~~~~~~~~ (18) end {eqnarray} ]
và lỗi: (|| mathbf {a} – mathbf {a} _k || _2 ^ 2 = sigma_ {k + 1} ^ 2 ). định nghĩa của chuẩn 2 của ma trận là:
[|| mathbf {a} || _2 = max_ {|| mathbf {x} || _2 = 1} || mathbf {ax} || _2 ]
Đây là lý do tại sao căn bậc hai của tổng bình phương của các phần tử của ma trận không được gọi là chuẩn 2 như đối với vectơ.
nếu bạn muốn biết thêm: [|| mathbf {a} || _2 = sigma_1 ] tức là chuẩn 2 của ma trận là giá trị kỳ dị lớn nhất của ma trận đó.
định mức frobenius và định mức 2 là hai định mức được sử dụng nhiều nhất trong ma trận. do đó, xem xét cả hai định mức, svd bị cắt ngắn cho giá trị gần đúng nhất. vì vậy svd bị cắt ngắn còn được gọi là giá trị gần đúng nhất trong phạm vi thấp.
4. một số ứng dụng svd
4.1. nén hình ảnh
Hãy xem xét ví dụ trong Hình 3 bên dưới:
Hình 3 mô tả chất lượng hình ảnh khi các giá trị khác nhau của (k ) được chọn. khi (k ) gần bằng 100, lượng thông tin bị mất ít hơn 2%, hình ảnh thu được có chất lượng giống như hình ảnh gốc.
để lưu hình ảnh với svd bị cắt ngắn, chúng tôi sẽ lưu các ma trận ( mathbf {u} _k in mathbb {r} ^ {m times k}, sigma_k in mathbb {r} ^ { k times k}, mathbf {v} _k in mathbb {r} ^ {n times k} ). tổng số phần tử cần lưu trữ là (k (m + n + 1) ) với lưu ý rằng chúng ta chỉ cần lưu trữ các giá trị trên đường chéo của ( sigma_k ). giả sử rằng mỗi phần tử được lưu trữ bởi một số thực 4 byte, thì số byte được lưu trữ là (4k (m + n + 1) ). nếu chúng ta so sánh giá trị này với hình ảnh gốc có kích thước (mn ), mỗi giá trị là một số nguyên 1 byte, tỷ lệ nén là:
[ frac {4k (m + n + 1)} {mn} ] khi (k ll m, n ), chúng ta nhận được thang điểm nhỏ hơn 1 trong ví dụ của chúng ta (m = 960 , n = 1440, k = 100 ), chúng tôi có tỷ lệ nén khoảng 0,69, giúp tiết kiệm khoảng 30% bộ nhớ.
4.2. svd bị cắt ngắn cho hệ thống giới thiệu
Như đã đề cập ở điểm 1, svd là một phương pháp nhân tử hóa ma trận, vì vậy nó cũng có thể được áp dụng cho các bài toán hệ thống đề xuất như trong bài 25.
ý tưởng hoàn toàn giống nhau, chúng tôi sẽ tính gần đúng ma trận tiện ích chuẩn hóa (dựa trên người dùng hoặc dựa trên mặt hàng). giá trị của ma trận xấp xỉ thứ hạng thấp hơn là giá trị dự đoán.
kết quả (rmse) có cùng cơ sở dữ liệu như bài 25 là:
-
những người làm phim 100k, dựa trên người dùng: 1018 (tốt hơn 1,06 cho phép phân tích nhân tử của ma trận).
100k phim, dựa trên các bài báo: 1,014 (tốt hơn 1,05)
Phim dài 1m, dựa trên yếu tố: 0,95 (tốt hơn 0,98)
do đó, svd bị cắt ngắn cho kết quả tốt hơn một chút so với phân tích nhân tử của ma trận được giải quyết bằng phương pháp giảm dần.
một lời giải thích thú vị về mối quan hệ giữa svd và mảng tiện ích người dùng
5. thảo luận
-
Ngoài hai ứng dụng trên, svd cũng có liên quan mật thiết đến phép nghịch đảo giả moore penrose. (Xem thêm Moore-Penrose pseudoinverse (toán 33a – ucla)). giả nghịch đảo đóng một vai trò quan trọng trong việc giải hệ phương trình tuyến tính. một ví dụ đã được đề cập trong bài học 3: hồi quy tuyến tính.
còn nhiều thuộc tính và ứng dụng thú vị khác của svd, chúng ta sẽ tìm hiểu từng chút một. đầu tiên là giảm kích thước với phân tích thành phần chính. chúng ta sẽ nói về vấn đề này trong bài tiếp theo.
khi ma trận ( mathbf {a} ) lớn, việc tính toán svd của nó mất nhiều thời gian. Làm thế nào để tính toán svd bị cắt ngắn với (k ) tính toán svd nhỏ như tôi sử dụng trong bài viết là không thể. thay vào đó, có một phương pháp lặp để tính toán hiệu quả các giá trị riêng và ký tự riêng của một ma trận lớn và chúng ta chỉ cần tìm (k ) giá trị riêng lớn nhất của ( mathbf {aa} ^ t ) và giá trị riêng tương ứng eigenvectors, điều này sẽ tiết kiệm rất nhiều thời gian. độc giả có thể đọc thêm về phương pháp lũy thừa của các giá trị gần đúng. Phương pháp này cũng là phần chính của thuật toán xếp hạng trang nổi tiếng của Google. Tôi sẽ có một bài đăng về điều này nếu tôi thấy phù hợp.
mã nguồn
6. tài liệu tham khảo
[1] phân tích giá trị số ít – đại học stanford
[2] phân tích giá trị số ít – hoàng tử
[3] cs168: hộp công cụ thuật toán hiện đại, bài học số 9: phân rã giá trị số ít (svd) và xấp xỉ ma trận hạng thấp – stanford
[4] nghịch đảo moore-penrose (toán 33a – ucla)
Xem thêm:
-
-
-