Luận văn Phân tích không âm của ma trận

i 6= j. Với x = (x1, x2, ..., xn) ∈ Rn , Dx là ma trận đường chéo với các phần tử trên đường chéo là x1, x2, ..., xn. Ma trận A vuông cấp n được gọi là nửa xác định dương nếu xTAx ≥ 0 ∀x ∈ Rn.A được gọi là xác định dương nếu xTAx > 0 với mọi x ∈ Rn, x 6= 0. Nếu A đối xứng và nửa xác định dương thì tất cả các giá trị riêng của A đều không âm. 5Vector hóa của ma trận A ∈ Rm×n là: vec(A) =  A:1 ... A:n  ∈ Rmn. Ví dụ 1.1.1. Cho ma trận A = ( a b c d ) . Vector hóa ma trận A là: vec(A) =  a c b d  . Bằng cách vector hóa ma trận, ta có thể xem một ma trận tổng quát A cỡ m × n như một vector: vec(A) với m × n thành phần và có thể xác định tích trong của hai ma trận thực cùng cỡ như sau: 〈A,B〉 = vec(A)Tvec(B) = ∑ ij aijbij = trace ( ATB ) . Ở đó, vết của ma trận vuôngA (được kí hiệu trace(A)) là tổng của tất cả các phần tử đường chéo của ma trận A. Điều này suy ra một mối quan hệ mà chúng ta sẽ dùng ở chương sau: Mệnh đề 1.1.1. 〈I, ABC〉 = 〈AT , BC〉 = 〈BTAT , C〉 = 〈CTBTAT , I〉 = trace (ABC) . Chứng minh. Ta có: 〈I, ABC〉 = vec(I)Tvec(ABC) = trace (IABC) = trace (ABC) . (1.1)〈 AT , BC 〉 = vec ( AT )T vec(BC) = trace (ABC) . (1.2)〈 BTAT , C 〉 = vec ( BTAT )T vec(C) = trace ( (BTAT )TC ) 6= trace ( (AT )T (BT )TC ) = trace (ABC) . (1.3)〈 CTBTAT , I 〉 = vec ( CTBTAT )T vec(I) = trace ( (CTBTAT )T I ) = trace ( (AT )T (CTBT )T I ) = trace ( A(BT )T (CT )T ) = trace (ABC) . (1.4) Vậy từ (1.1),(1.2),(1.3),(1.4) ta có điều phải chứng minh. Tích Hadamard của hai ma trận A và B cùng cỡ m × n (kí hiệu A ◦ B ) là một ma trận cùng cỡ C với cij = aijbij . Ví dụ 1.1.2. Cho hai ma trận A =  1 2 3 4 3 0 2 1 5  và B =  4 1 1 5 4 3 0 1 2 . Ta có: A ◦B =  4 2 3 20 12 0 0 1 10  . Mệnh đề 1.1.2. Với A,B,C là các ma trận cỡm× n, ta có: (i) A ◦B = B ◦ A ; (ii) A ◦ (B ◦ C) = (A ◦B) ◦ C; (iii) A ◦ (B + C) = (A ◦B) + (A ◦ C); (iv) AT ◦BT = (A ◦B)T . Chứng minh. (i) A ◦B = (aijbij)m×n = (bijaij)m×n = B ◦ A. (ii) A ◦ (B ◦ C) = (aij(bijcij))m×n = ((aijbij)cij)m×n = (A ◦B) ◦ C. (iii) A ◦ (B + C) = (aij(bij + cij))m×n = (aijbij)m×n + (aijcij)m×n = (A ◦B) + (A ◦ C). (iv) AT ◦BT = (ajibji)m×n = (aijbij)Tm×n = (A ◦B)T . 71.1.2 Chuẩn Định nghĩa 1.1.1. Một chuẩn vector trên Rn là một hàm f : Rn → R thỏa mãn các tính chất sau: (i) f(x) ≥ 0, ∀x ∈ Rn; f(x) = 0⇔ x = 0; (ii) f(x+ y) ≤ f(x) + f(y), ∀x, y ∈ Rn; (iii) f(αx) = |α| f(x), ∀α ∈ R,∀x ∈ Rn. Chuẩn của x thường được ký hiệu là ‖x‖ Cho vector x = (x1, x2, ..., xn) T , một số chuẩn vector thông dụng là: • Chuẩn p (p ≥ 1) ‖x‖p = (|x1|p + ...+ |xn|p) 1 p . • Chuẩn 1 (p = 1) ‖x‖1 = |x1|+ ...+ |xn|. • Chuẩn 2 (p = 2) hay gọi là chuẩn Euclide ‖x‖ = ( |x1|2 + ...+ |xn|2 ) 1 2 = ( xTx ) 1 2 . • Chuẩn∞ (p =∞) ‖x‖∞ = max (|x1| , |x2| , ..., |xn|) . Ví dụ 1.1.3. Cho vector x = (1, 2, 4)T . Chuẩn 1 của vector x là: ‖x‖1 = 1 + 2 + 4 = 7. Chuẩn Euclide của vector x là: ‖x‖ = (12 + 22 + 42) 12 = √21. Chuẩn∞ của vector x là: ‖x‖∞ = max (1, 2, 4) = 4. Định nghĩa 1.1.2. Chuẩn ma trận trên Rm×n là hàm số f : Rm×n → R thỏa mãn các tính chất sau: (i) f(A) ≥ 0, ∀A ∈ Rm×n; f(A) = 0⇔ A = 0. 8(ii) f(A+B) ≤ f(A) + f(B), ∀A,B ∈ Rm×n; (iii) f(αA) = |α| f(A), ∀α ∈ R,∀A ∈ Rm×n. Kí hiệu: f(A) = ‖A‖ . Cho ma trận A = (aij)m×n , một số chuẩn ma trận thông dụng là: • Chuẩn 1 (chuẩn cực đại theo cột) ‖A‖1 = max1≤j≤n m∑ i=1 |aij|. • Chuẩn Frobenius. Kí hiệu:‖A‖F ‖A‖F = √√√√ m∑ i=1 n∑ j=1 |aij|2. • Chuẩn∞ (chuẩn cực đại theo hàng) ‖A‖∞ = max1≤i≤m n∑ j=1 |aij|. Ví dụ 1.1.4. Cho ma trận A =  4 2 3 −1 3 −2 0 1 5  a) Chuẩn 1 của ma trận A là: ‖A‖1 = max1≤j≤3 3∑ i=1 |aij| = max 1≤j≤3 (|a1j|+ |a2j|+ |a3j|) = max (|a11|+ |a21|+ |a31| ; |a12|+ |a22|+ |a32| ; |a13|+ |a23|+ |a33| ) = max (4 + 1 + 0; 2 + 3 + 1; 3 + 2 + 5) = max(5; 6; 10) = 10. b) Chuẩn Frobenius của ma trận A là: ‖A‖F = √ 3∑ i=1 3∑ j=1 |aij|2 = ( |4|2 + |2|2 + |3|2 + |−1|2 + |3|2 + |−2|2 + |0|2 + |1|2 + |5|2 ) 1 2 = √ 69. 9c) Chuẩn∞ của ma trận A là: ‖A‖∞ = max1≤i≤3 3∑ j=1 |aij| = max 1≤i≤3 (|ai1|+ |ai2|+ |ai3|) = max (|a11|+ |a12|+ |a13| ; |a21|+ |a22|+ |a23| ; |a31|+ |a32|+ |a33| ) = max (4 + 2 + 3; 1 + 3 + 2; 0 + 1 + 5) = max(9; 6; 6) = 9. 1.1.3 Ma trận không âm Định nghĩa 1.1.3. Ma trận A có tất cả các phần tử không âm được gọi là ma trận không âm. Kí hiệu: A ≥ 0. Rm×n+ là tập hợp các ma trận không âm cỡ m× n. Chúng ta viết: A ≥ 0 nếu aij ≥ 0 ∀ i, j; A > 0 nếu aij > 0 ∀ i, j. Một ma trận không âm gọi là chấp nhận được theo hàng nếu nó không có hàng bằng không. Tương tự, một ma trận không âm gọi là chấp nhận được theo cột nếu nó không có cột bằng không. Một ma trận không âm gọi là ngẫu nhiên cột (hàng) nếu tất cả các tổng cột (hàng) bằng một. Một trong những kết quả quan trọng liên quan đến ma trận không âm được trình bày sau đây: Định lý 1.1.1. Cho A là một ma trận vuông, không âm. Giá trị riêng lớn nhất của A là không âm và tồn tại một vector riêng không âm tương ứng với nó. Vector này thường gọi là vector Perron của ma trận không âm. Cho một tập con V ⊂ Rm×n và ma trận A ∈ Rm×n, phần tử gần nhất của V đến A (tương ứng với khoảng cách) được gọi là hình chiếu của A trên V , kí hiệu bởi PV (A). Nếu ta xét V là tập các ma trận không âm và khoảng cách xem xét là khoảng cách Euclide (chuẩn Frobenius), hình chiếu của A được kí hiệu là [A]+ và được cho bởi: [ [A]+ ] ij = { aij khi aij > 0 0 khi aij ≤ 0 = max(0, aij). 10 Ví dụ 1.1.5. Cho ma trận A = ( 1 0 −2 3 ) . Hình chiếu của ma trận A lên R2×2+ là: [A]+ = ( 1 0 0 3 ) . 1.2 LÝ THUYẾT TỐI ƯU 1.2.1 Tập lồi và hàm lồi Định nghĩa 1.2.1. Một tập con C ⊂ Rn được gọi là tập lồi nếu ∀x1, x2 ∈ C; ∀λ ∈ [0, 1] ta có: λx1 + (1− λ)x2 ∈ C. Ví dụ 1.2.1. Các nửa không gian là các tập lồi. Các tam giác và các hình tròn trong mặt phẳng là tập lồi. Tập hợp các ma trận không âm cỡm× n ( Rm×n+ ) cũng là một tập lồi. Tập Rm×n+ là một trong những đối tượng chính được sử dụng trong luận văn này. Định nghĩa 1.2.2. Một tập C ⊂ Rn được gọi là nón lồi nếu nó đóng với phép cộng và phép nhân với một số không âm. u, v ∈ C ⇒ u+ v ∈ C, u ∈ C, α ≥ 0⇒ αu ∈ C. Ví dụ 1.2.2. Rn+ là nón lồi. Định nghĩa 1.2.3. Một nón đa diện là một nón lồi được sinh bởi một tập các vector V = {v1, v2, ..., vk} ∈ Rn tức là: C = { k∑ i=1 αivi |αi ∈ R+ } . 11 Định nghĩa 1.2.4. Giả sử tập C ⊂ Rn là tập lồi. Hàm số f : C → R. Hàm f được gọi là hàm lồi trên C nếu ∀x1, x2 ∈ C; ∀λ ∈ [0, 1] ta có: f (λx1 + (1− λ)x2) ≤ λf(x1) + (1− λ) f (x2). Hàm f được gọi là hàm lồi chặt trên C nếu ∀λ ∈ (0, 1); ∀x1 6= x2 ∈ C ta có: f (λx1 + (1− λ)x2) < λf(x1) + (1− λ) f (x2). Mệnh đề 1.2.1. Cho ‖ . ‖ là một chuẩn tương ứng với tích vô hướng 〈., .〉 trên Rn. Khi đó: (i) ‖ . ‖ là hàm lồi trên Rn. (ii) ‖ . ‖2 là hàm lồi trên Rn. Chứng minh. (i) Với mọi x, y ∈ Rn, λ ∈ [0, 1], ta có: ‖λx+ (1− λ)y‖ ≤ ‖λx‖+ ‖(1− λ)y‖ = λ ‖x‖+ (1− λ) ‖y‖ . (ii) Với mọi x, y ∈ Rn, λ ∈ [0, 1], ta có: ‖λx+ (1− λ)y‖2 = 〈λx+ (1− λ)y, λx+ (1− λ)y 〉 = λ2‖x‖2 + 2λ(1− λ) 〈x, y〉+ (1− λ)2‖y‖2 = λ‖x‖2 + (1− λ)‖y‖2 + (λ2 − λ)‖x‖2 + ( (1− λ)2 − (1− λ) ) ‖y‖2 + 2λ(1− λ) 〈x, y〉 Khai triển và giản ước ta được kết quả sau: λ‖x‖2 + (1− λ)‖y‖2 + λ(λ− 1)‖x‖2 + λ(λ− 1)‖y‖2 − 2λ(λ− 1) 〈x, y〉 = λ‖x‖2 + (1− λ)‖y‖2 + λ(λ− 1)‖x− y‖2 ≤ λ‖x‖2 + (1− λ)‖y‖2. 1.2.2 Điều kiện tối ưu Xét bài toán: min x∈C f(x) (1.5) với C ⊂ Rn, f : C → R. 12 Định nghĩa 1.2.5. Điểm x∗ ∈ C được gọi là cực tiểu địa phương của bài toán (1.5) nếu ∃ε > 0 sao cho ∀x ∈ C ∩ B(x∗, ε) ta có: f(x) ≥ f(x∗). Điểm x∗ ∈ C được gọi là cực tiểu địa phương ngặt của bài toán (1.5) nếu ∀x ∈ C ∩B(x∗, ε) và x 6= x∗ ta có: f(x) > f(x∗). Định nghĩa 1.2.6. Điểm x∗ ∈ C được gọi là cực tiểu toàn cục của bài toán (1.5) nếu ∀x ∈ C ta có: f(x) ≥ f(x∗). Điểm x∗ ∈ C được gọi là cực tiểu toàn cục ngặt của bài toán (1.5) nếu ∀x ∈ C, x 6= x∗ ta có: f(x) > f(x∗). Tập các hướng chấp nhận được tại x∗ ∈ C là: Z(x∗) = {d ∈ Rn |∃λ∗ > 0 : x∗ + λd ∈ C, ∀ 0 ≤ λ ≤ λ∗} . Định lý 1.2.1. Giả sử tập C ⊂ Rn và f là một hàm khả vi trên C. Nếu x∗ là cực tiểu địa phương của f trên C thì: dT∇f(x∗) ≥ 0, ∀d ∈ Z(x∗). Chứng minh. Lấy d ∈ Z(x∗) . Khi đó, tồn tại λ∗ sao cho ∀λ : 0 ≤ λ ≤ λ∗ thì x∗ + λd ∈ C. x∗ là cực tiểu địa phương có nghĩa là tồn tại ε > 0 sao cho: ∀x ∈ C ∩B(x∗, ε) thì f(x) ≥ f(x∗). Lấy λ1 = min ( λ∗, ε‖d‖ ) Khi đó, ∀ 0 ≤ λ ≤ λ1 ta có:{ x∗ + λd ∈ C x∗ + λd ∈ B(x∗, ε). Nên f (x∗ + λd) ≥ f(x∗),∀0 ≤ λ ≤ λ1 (1.6) Ta lại có: dT∇f(x∗) = lim t→0+ f(x∗+td)−f(x∗) t ≥ 0 (do (1.6)). Định nghĩa 1.2.7. Điểm x∗ ∈ C thỏa mãn: dT∇f(x∗) ≥ 0, ∀d ∈ Z(x∗) được gọi là điểm dừng của bài toán (1.5). 13 Mệnh đề 1.2.2. Giả sử x∗ ∈ int(C) và x∗ là điểm dừng của bài toán (1.5). Khi đó: Z(x∗) = Rn và∇f(x∗) = 0. Chứng minh. Mệnh đề này được suy ra trực tiếp từ Định lý 1.2.1. Định lý 1.2.2. Giả sử C ⊂ Rn là tập lồi và f là hàm lồi. Khi đó, mọi cực tiểu địa phương của bài toán (1.5) cũng là cực tiểu toàn cục. Chứng minh. Giả sử x∗ ∈ C là cực tiểu địa phương của bài toán (1.5). Theo định nghĩa, tồn tại ε > 0 sao cho với mọi y ∈ B(x∗, ε) ∩ C ta có: f(y) ≥ f(x∗). Với mọi x ∈ C, đặt d = x − x∗. Khi đó tồn tại λ ∈ [0, 1] sao cho x∗ + λd ∈ B(x∗, ε) ∩ C. Nên f(x∗ + λd) ≥ f(x∗). Lại có x∗ + λd = x∗ + λ(x− x∗) = λx+ (1− λ)x∗. Do f lồi trênC nên f(x∗+λd) = f(λx+(1−λ)x∗) ≤ λf(x)+(1−λ)f(x∗). Mà f(x∗+λd) ≥ f(x∗) nên f(x∗) ≤ λf(x)+(1−λ)f(x∗)⇔ f(x∗) ≤ f(x). Điều này đúng với mọi x ∈ C. Vậy x∗ là cực tiểu toàn cục của bài toán (1.5). 1.2.3 Điều kiện Kuhn-Tucker Xét bài toán tối ưu min x∈C f(x) (1.7) với C = {x : hi(x) = 0, gj(x) ≤ 0}. Trong đó: hi(x) = 0 (i = 1, 2, ..., k) là k ràng buộc đẳng thức và gj(x) ≤ 0 (j = 1, 2, ...,m) là m ràng buộc bất đẳng thức. Ràng buộc của bài toán này được viết trong hàm Lagrange như sau: L(x, µ1, ..., µk, λ1, ..., λm) = f(x) + k∑ i=1 µihi(x) + m∑ j=1 λjgj(x) Trong đó µi (i = 1, ..., k) và λj ≥ 0 (j = 1, ...,m) gọi là nhân tử Lagrange. Định lý 1.2.3. Cho x∗ là cực tiểu địa phương của bài toán (1.7). Giả sử rằng f, hi, gj : Rn → R là các hàm khả vi liên tục; ∇hi(x∗) và ∇gj(x∗) là độc lập 14 tuyến tính. Khi đó tồn tại µi(i = 1, ..., k) và λj(j = 1, ...,m) thỏa mãn các điều kiện sau: (i)∇f(x∗) + k∑ i=1 µi∇hi(x∗) + m∑ j=1 λj∇gj(x∗) = 0, (ii) λj ≥ 0 (j = 1, ...,m), (iii) λjgj(x ∗) = 0 (j = 1, ...,m). Các điều kiện (i) − (iii) được gọi là điều kiện Kuhn - Tucker (KT) của bài toán (1.7). 15 CHƯƠNG 2 PHÂN TÍCH KHÔNG ÂM CỦAMA TRẬN Trong chương này chúng tôi trình bày bài toán phân tích không âm của ma trận, điều kiện cần tối ưu và đồng thời nêu các ứng dụng trong phân tích dữ liệu. Nội dung của chương được tham khảo từ các tài liệu [3], [4], [5]. 2.1 PHÁT BIỂU BÀI TOÁN Phân tích không âm của ma trận được giới thiệu lần đầu tiên bởi Paatero và Tapper [5]. Nhưng nó đã trở nên nổi tiếng nhờ công trình của Lee và Seung [6]. Họ cho rằng tính không âm là rất quan trọng trong nhận thức của con người và cũng đưa ra hai thuật toán đơn giản để tìm một biểu diễn không âm cho dữ liệu. Bài toán phân tích không âm của ma trận có thể được “phát biểu” như sau: Cho một ma trận không âm A cỡ m × n (tức là aij ≥ 0) và hạng r (r ≤ min(m,n)). Tìm hai ma trận không âm U ∈ Rm×r+ và V ∈ Rn×r+ sao cho “xấp xỉ” A, tức là: A ≈ UV T . Chúng ta sẽ làm rõ khái niệm “xấp xỉ” ở phần sau của mục này. Gọi U:j là các cột của ma trận U và A:i là các cột của ma trận A. Khi đó, ta có: A:i ≈ r∑ j=1 vijU:j. Tức là các cột của ma trận A được xấp xỉ bởi một tổ hợp dạng nón (các hệ số vij > 0) của các vector cột của U . 16 Nếu ta ký hiệu X = { r∑ j=1 λjU:j, λj > 0 } là nón dương sinh bởi các cột U:j của ma trận U , khi đó mỗi cột của ma trận A được xấp xỉ bởi một phần tử trong nón X . Phần tử đó chính là phần tử gần nhất với cột A:i trong nón X . Bằng cách đổi vai trò của U, V ta có thể chỉ ra rằng mỗi hàng của A được xấp xỉ bởi một phần tử của nón dương sinh bởi các cột của V . Người ta có thể dùng nhiều cách để xác định sự khác nhau giữa ma trận dữ liệu A và ma trận mô hình UV T . Nhưng phương pháp được dùng nhiều nhất là chuẩn Frobenius: ∥∥A− UV T∥∥2 F = m∑ i=1 n∑ j=1 ( aij − [UVT]ij )2 còn được gọi là khoảng cách Euclide. Đặt F (U, V ) = 1 2 ∥∥A− UV T∥∥2 F . Mệnh đề 2.1.1. (i) Với mỗi U cố định, hàm F là lồi theo V . (ii) Với mỗi V cố định, hàm F là lồi theo U . Chứng minh. (i) Với U cố định, ta có: F (U, λV1 + (1− λ)V2) = 1 2 ∥∥A− λUV T1 − (1− λ)UV T2 ∥∥2F = 1 2 ∥∥λA+ (1− λ)A− λUV T1 − (1− λ)UV T2 ∥∥2F = 1 2 ∥∥λ(A− UV T1 ) + (1− λ)(A− UV T2 )∥∥2F . Theo Mệnh đề 1.2.1, ‖ . ‖2F là hàm lồi trên Rm×n, do đó: 1 2 ∥∥λ(A− UV T1 ) + (1− λ)(A− UV T2 )∥∥2F ≤ λ1 2 ∥∥A− UV T1 ∥∥2F + (1− λ)12∥∥A− UV T2 ∥∥2F = λF (U, V1) + (1− λ)F (U, V2). Suy ra hàm F là lồi theo V . 17 (ii) Với V cố định, ta có: F (λU1 + (1− λ)U2, V ) = 1 2 ∥∥A− λU1V T − (1− λ)U2V T∥∥2F = 1 2 ∥∥λA+ (1− λ)A− λU1V T − (1− λ)U2V T∥∥2F = 1 2 ∥∥λ(A− U1V T ) + (1− λ)(A− U2V T )∥∥2F Theo Mệnh đề 1.2.1, ‖ . ‖2F là hàm lồi trên Rm×n, do đó: 1 2 ∥∥λ(A− U1V T ) + (1− λ)(A− U2V T )∥∥2F ≤ λ1 2 ∥∥A− U1V T∥∥2F + (1− λ)12∥∥A− U2V T∥∥2F = λF (U1, V ) + (1− λ)F (U2, V ). Suy ra hàm F là lồi theo U . Trong suốt luận văn này, chúng ta sẽ xét bài toán phân tích không âm của ma trận với chuẩn Frobenius. Bài toán chính được phát biểu như sau: Bài toán 2.1.1. (Phân tích không âm của ma trận - NMF). Cho một ma trận không âm A cỡm× n và một số nguyên r < min(m,n), giải bài toán min U∈Rm×r+ V ∈Rn×r+ 1 2 ∥∥A− UV T∥∥2 F Khi đó r được gọi là hạng giảm. Từ giờ trở đi, m và n sẽ được sử dụng để biểu thị cỡ của ma trận A và r là hạng giảm của một phân tích. Nhận xét 2.1.1. Với mỗi U cố định, hàm F (U, V ) là lồi theo V và với mỗi V cố định ,hàm F (U, V ) là lồi theo U . Nhưng hàm F (U, V ) không lồi theo cả hai biến vì vậy bài toán 2.1.1 là bài toán tối ưu không lồi. Về mặt lý thuyết, có nhiều thuật toán để tìm cực tiểu toàn cục của một bài toán tối ưu không lồi. Tuy nhiên, trong thực tế khi giải bài toán NMF, người ta thường chỉ đi tìm cực tiểu địa phương thay vì cực tiểu toàn cục. 2.2 ỨNG DỤNG TRONG PHÂN TÍCH DỮ LIỆU Lý do tại sao NMF trở nên phổ biến là vì nó có khả năng tự động trích xuất các yếu tố thưa thớt và dễ hiểu. Trong phần này, chúng tôi minh họa tính chất 18 này của NMF thông qua các ứng dụng, trong quá trình xử lý ảnh, khai thác văn bản. Ngoài ra NMF còn có các ứng dụng khác bao gồm ảnh siêu phổ, kiểm soát khí thải, sinh học tính toán, tách nguồn mù, tách nguồn đơn kênh, phân cụm, phân tích nhạc. 2.2.1 Xử lý ảnh - Trích xuất đặc điểm khuôn mặt Mỗi bức ảnh đen trắng của một khuôn mặt được lưu trữ dưới dạng một ma trận mà các phần tử của ma trận tương ứng với độ xám hay cường độ tại mỗi điểm ảnh. Mỗi cột của ma trận dữ liệu A ∈ Rp×n+ tương ứng với vector hóa của hình ảnh một khuôn mặt. Ở đó, A(i, j) là cường độ của điểm ảnh thứ i trong khuôn mặt thứ j. NMF sinh ra hai thừa số (U, V ) sao cho mỗi hình ảnh A(:, j) được xấp xỉ bằng cách sử dụng sự tổ hợp tuyến tính của các cột của U . Điều này được minh họa bởi công thức và hình ảnh dưới đây: A(:, j) ≈ r∑ k=1 U(:, k) V (j, k) = UV (:, j) Hình 2.1: Phân tích cơ sở dữ liệu CBCL [Nguồn: [3]]. trong đó: A(:, j): hình ảnh khuôn mặt thứ j, U(:, k): đặc điểm khuôn mặt, V (j, k): mức độ quan trọng của đặc điểm trong hình ảnh thứ j, UV (:, j): xấp xỉ của hình ảnh thứ j. 19 Từ U là không âm, các cột của U có thể được hiểu là hình ảnh (nghĩa là vector cường độ điểm ảnh) mà chúng ta gọi là hình ảnh cơ sở. Vì các trọng số trong các tổ hợp tuyến tính là không âm (V ≥ 0), những hình ảnh cơ sở này chỉ có thể được sử dụng để tái tạo lại mỗi hình ảnh gốc. Ngoài ra, số lượng lớn hình ảnh trong tập dữ liệu phải được xây dựng lại xấp xỉ với chỉ một vài hình ảnh cơ sở (trên thực tế, r nói chung nhỏ hơn rất nhiều so với n). Do đó, phân tích này sẽ khoanh vùng một số đặc điểm đặc trưng đồng thời xuất hiện ở một vài bức ảnh. Trong trường hợp hình ảnh khuôn mặt, hình ảnh cơ sở là các đặc điểm như mắt, mũi, ria mép và môi (như hình 2.1) trong khi các cột của V chỉ ra rằng đặc điểm nào có trong hình ảnh đó. Một ứng dụng tiềm năng của NMF là nhận diện khuôn mặt. Người ta nhận thấy rằng NMF “mạnh hơn” so với PCA (Principal Compoment Analysis - phân tích thành phần chính dựa trên khai triển giá trị kỳ dị). Trong thực tế, người ta thấy rằng với nhiều bức ảnh mà một phần khuôn mặt bị che khuất (ví dụ: người đeo kính râm) thì NMF hoạt động khá tốt vì có thể trích xuất được nhiều đặc điểm không bị che khuất (ria mép, môi). 2.2.2 Khai thác văn bản - Khôi phục chủ đề và tài liệu Đặt mỗi cột của ma trận không âm A tương ứng với một tài liệu và mỗi hàng ứng với một từ. Phần tử (i, j) của ma trận A có thể được cho bằng số lần xuất hiện của từ thứ i trong tài liệu thứ j. Trong trường hợp này, ta gọi mỗi cột của A là vector đếm từ của tài liệu. Trong thực tế, người ta có thể sử dụng các mô hình phức tạp hơn. Ví dụ như mô hình túi từ ở đó mỗi từ trong từ điển được gán với một trọng số. Lưu ý rằng ma trận A nói chung khá thưa (đa số các phần tử bằng 0) vì hầu hết tài liệu chỉ sử dụng một tập hợp con nhỏ các từ trong từ điển. Với ma trận A và hạng phân tích r, NMF tạo ra hai nhân tử (U, V ) sao cho với mọi 1 ≥ j ≥ n, chúng ta có: A(:, j) ≈ r∑ k=1 U(:, k) V (j, k) 20 trong đó: A(:, j): tài liệu thứ j, U(:, k): chủ đề thứ k, V (j, k): tầm quan trọng của chủ đề thứ k trong tài liệu thứ j. Khi đó U ≥ 0 và V ≥ 0. Phân tích này có thể được hiểu như sau: • Vì U là không âm, mỗi cột của U có thể được hiểu như một tài liệu ứng với một túi từ trong từ điển. • Vì các trọng số trong các tổ hợp tuyến tính là không âm (V ≥ 0) nên người ta có thể lấy hợp của các tập hợp các từ được xác định bởi các cột của U để xây dựng lại tất cả các tài liệu gốc. • Hơn nữa, vì số lượng tài liệu trong tập dữ liệu lớn hơn nhiều so với số phần tử cơ sở (tức là, số cột của U ) nên các cột của U sẽ tương ứng với tổ hợp các từ cùng xuất hiện trong nhiều tài liệu. Do đó, các phần tử cơ sở này có thể được hiểu như các chủ đề của tài liệu. Trong khi đó, các trọng số trong các tổ hợp tuyến tính (nghĩa là ma trận V ) sẽ cho ta biết tài liệu thảo luận về chủ đề nào. Như vậy, với một bộ dữ liệu gồm các văn bản, khai triển NMF sẽ giúp ta xác định các chủ đề chính của bộ dữ liệu và đồng thời phân loại các tài liệu theo các chủ đề khác nhau này. 2.3 ĐIỀU KIỆN CẦN TỐI ƯU 2.3.1 Hàm Lagrange Chúng ta viết lại phân tích ma trận không âm như một bài toán tối ưu phi tuyến ở dạng chuẩn tắc: min −U≤0 −V≤0 1 2 ∥∥A− UV T∥∥2 F (2.1) Các ràng buộc −U ≤ 0 và −V ≤ 0 có nghĩa là: −uij ≤ 0 ∀i = 1, 2, ...,m ∀j = 1, 2, ..., r, −vij ≤ 0 ∀i = 1, 2, ..., n ∀j = 1, 2, ..., r. 21 Ta kí hiệu các nhân tử Lagrange tương ứng là: µij ≥ 0 ∀i = 1, 2, ...,m ∀j = 1, 2, ..., r, νij ≥ 0 ∀i = 1, 2, ..., n ∀j = 1, 2, ..., r. Đặt µ = (µij)m×r, ν = (νij)n×r. Khi đó hàm Lagrange tương ứng của bài toán (2.1) là: L(U, V, µ, ν) = 1 2 ∥∥A− UV T∥∥2 F − ∑ i=1,m j=1,r µijuij − ∑ i=1,n j=1,r νijvij 2.3.2 Điều kiện cần tối ưu Điều kiện Kuhn - Tucker của bài toán (2.1) nói rằng nếu (U, V ) là cực tiểu địa phương thì tồn tại µij ≥ 0, νij ≥ 0 sao cho: (i) (Điều kiện chấp nhận được) − U ≤ 0, −V ≤ 0, (2.2) (ii) (Đạo hàm hàm Lagrange bằng 0) ∇LU = 0, ∇LV = 0 (2.3) (iii) (Điều kiện bù) µ ◦ U = 0, ν ◦ V = 0. (2.4) Ở đó, µ ◦ U = 0 là tích Hadamard của µ và U đã định nghĩa ở chương 1. Từ (2.3) ta có: ∇LU = (A− UV T )(V T )T − µ = 0⇔ µ = AV − UV TV ∇LV = (AT − V UT )(UT )T − ν = 0⇔ ν = ATU − V UTU . Kết hợp với µij ≥ 0, νij ≥ 0 và (2.4) ta được các điều kiện sau: U ≥ 0, V ≥ 0, (2.5) ∇FU = AV − UV TV ≥ 0,∇FV = ATU − V UTU ≥ 0, (2.6) U ◦ (AV − UV TV ) = 0, V ◦ (ATU − V UTU) = 0. (2.7) ở đó các nhân tử Lagrange của U (V ) là gradient của F với U (V ) tương ứng. 22 Định nghĩa 2.3.1. (Điểm dừng NMF) Chúng ta gọi (U, V ) là các điểm dừng của bài toán NMF khi và chỉ khi U và V thoả mãn các điều kiện KT (2.5), (2.6), (2.7). Chú ý 2.3.1. Ngoài ra, một điểm dừng (U, V ) của bài toán NMF cũng có thể được định nghĩa bằng cách sử dụng điều kiện trong định lý (1.2.1) trên tập lồi Rm×r+ và Rn×r+ , tức là:〈( ∇FU ∇FV ) , ( X − U Y − V )〉 ≥ 0, ∀X ∈m×r+ , Y ∈n×r+ (2.8) Điều kiện này tương đương với các điều kiện KT (2.5), (2.6), (2.7). Ví dụ 2.3.1. Chúng ta hãy xem xét bài toán không âm đơn giản nhất trong đó ma trận A là một số a. Bài toán (hạng một) là tìm hai số x và y có tích xấp xỉ a. Bài toán (2.1.1) chỉ ra có đúng một xấp xỉ (a − xy)2 = 0 và chúng ta có vô số các nghiệm đưa ra bởi đồ thị xy = a (hình 2.1). y x 0 0 1 a 1 a Hình 2.1: Đồ thị a = xy 23 2.3.3 Đặc trưng của cực tiểu địa phương Điều kiện (2.7) giúp mô tả các điểm dừng của bài toán NMF. Tổng hợp tất cả các phần tử của một trong các điều kiện (2.7), ta được: 0 = ∑ ij ( U ◦ (AV − UV TV )) ij = 〈 U,AV − UV TV 〉 = 〈UV T , A− UV T〉 . (2.9) Từ đó, chúng ta có một số đặc trưng đơn giản của nghiệm NMF: Định lý 2.3.1. Giả sử (U, V ) là một điểm dừng của bài toán NMF thì có UV T ∈ B ( A 2 , 1 2 ‖A‖F ) hình cầu có tâm tại A 2 và bán kính bằng 1 2 ‖A‖F . Chứng minh. Từ (2.9), chúng ta có 〈 UV T , A 〉 = 〈 UV T , UV T 〉 . Do đó:∥∥∥∥A2 − UV T ∥∥∥∥2 = 〈A2 − UV T , A2 − UV T 〉 = 〈 A 2 , A 2 〉 − 2 〈 UV T , A 2 〉 + 〈 UV T , UV T 〉 = 〈 A 2 , A 2 〉 = 1 4 ‖A‖2F tức là UV T ∈ B ( A 2 , 1 2 ‖A‖F ) . Định lý 2.3.2. Giả sử (U, V ) là một điểm dừng của bài toán NMF thì 1 2 ∥∥A− UV T∥∥2 F = 1 2 ( ‖A‖2F − ∥∥UV T∥∥2 F ) Chứng minh. Từ (2.9), chúng ta có: 〈 UV T , A 〉 = 〈 UV T , UV T 〉 . Do đó: 1 2 ∥∥A− UV T∥∥2 F = 1 2 〈 A− UV T , A− UV T〉 = 1 2 ( ‖A‖2F − 2 〈 UV T , A 〉 + ∥∥UV T∥∥2 F ) = 1 2 ( ‖A‖2F − ∥∥UV T∥∥2 F ) . Nhận xét 2.3.1. Định lý (2.3.2) cho ta thấy rằng tại điểm dừng (U, V ) của bài toán NMF, chúng ta có điều kiện sau: ‖A‖2F ≥ ∥∥UV T∥∥2 F . Dấu "=" của bất 24 đẳng thức ‖A‖2F ≥ ∥∥UV T∥∥2 F chỉ xảy ra khi chúng ta có một phân tích chính xác (tức là A = UV T ). 25 CHƯƠNG 3 THUẬT TOÁN VÀ THỬ NGHIỆM SỐ Trong chương này, chúng tôi mô tả hai thuật toán giải bài toán phân tích không âm của ma trận: Thuận toán bình phương tối thiểu luân phiên và Thuật toán Lee và Seung (còn gọi là Quy tắc nhân của Lee và Seung). Thuật toán bình phương tối thiểu luân phiên là thuật toán đầu tiên được đề xuất để giải bài toán phân tích không âm của ma trận. Tuy vậy, trong thực tế tính toán, người ta thường hay sử dụng thuật toán của Lee và Seung. Do vậy, thuật toán bình phương tối thiểu luân phiên chỉ được giới thiệu qua mà không đi sâu vào phân tích chi tiết. Chúng tôi cũng trình bày các kết quả liên quan đến sự hội tụ của thuật toán Lee và Seung trong phần 3.2. Trong phần cuối của chương, chúng tôi đưa ra một vài kết quả thử nghiệm phân tích không âm của ma trận để giảm chiều dữ liệu trong bài toán nhận diện khuôn mặt. Nội dung trình bày trong chương này được tham khảo từ các tài liệu [4],[5],[6]. 3.1 THUẬT TOÁN BÌNH PHƯƠNG TỐI THIỂU LUÂN PHIÊN Thuật toán đầu tiên được đề xuất để giải bài toán phân tích không âm của ma trận là thuật toán bình phương tối thiểu luân phiên. Ta đã biết rằng, khi cố định U (hoặc V ), hàm mục tiêu F (U, .) lồi theo biến V (tương ứng U ). Trong thuật toán bình phương tối thiểu luân phiên, ta cố định U hoặc V và giải bài toán bình phương tối thiểu theo biến còn lại với ràng buộc không âm. Như vậy, bài toán khai triển không âm của ma trận có thể được tách thành các bài toán nhỏ hơn tương ứng với các cột hoặc các hàng của ma trận A. Thuật toán 1. Bình phương tối thiểu luân phiên (Alternating Least Square) Bước 1: Khởi tạo U và V 26 Bước 2: repeat Giải:minV≥0 12 ∥∥A− UV T∥∥2 F Giải:minU≥0 12 ∥∥AT − V UT∥∥2 F until điều kiện dừng. Nhận xét 3.1.1. Nếu hai bài toán con ở bước 2 trong Thuật toán 1 được giải chính xác và duy nhất thì mọi điểm tụ của dãy lặp trong Thuật toán 1 là điểm dừng của bài toán phân tích không âm của ma trận. Tuy nhiên trong thực tế, thuật toán này chạy chậm hơn rất nhiều so với các thuật toán khác để giải bài toán phân tích không âm của ma trận. 3.2 THUẬT TOÁN LEE VÀ SEUNG 3.2.1 Thuật toán Một trong những thuật toán phổ biến nhất để giải bài toán NMF là quy tắc nhân được đưa ra bởi Lee và Seung [6]. Với U cố định xét hàm g(V ) = 1 2 ∥∥A− UV T∥∥2 F . Ta có:∇g(V ) = UT (A− UV T ). Theo thuật toán gradient ta có thể xây dựng V Tij ← V Tij + ηij[(UTA)ij − (UTUVT)ij]. Lee và Seung chọn ηij = V Tij (UTUV T ) ij . Khi đó ta thu được: V Tij ← V Tij . (UTA)ij (UTUV T ) ij ⇒ Vij ← Vij. (A TU)ij (V UTU) ij . 27 Tương tự, cố định V và cực tiểu hàm theo U , ta có thể gán Uij ← Uij. (AV )ij (UV TV ) ij . Thuật toán 2. Quy tắc nhân (Multiplicative Rules) Bước 1: Khởi tạo U 0, V 0 > 0 và k = 0 Bước 2: repeat Uk+1ij = U k ij. (AV k)ij (Uk(V k)TV k) ij V k+1ij