Chuẩn của vector và ma trận

Bài này nhắc lại một kiến thức cơ bản trong ĐSTT là chuẩn (norm).

Tạm thời không nhắc đến định nghĩa “sách vở” và sặc mùi hàn lâm của chuẩn, thì hiểu một cách đơn giản, chuẩn là một phép gán cho mỗi vector hoặc ma trận một số không âm sao cho nó thỏa một số tính chất nào đó. Thông thường chuẩn của ma trận A được kí hiệu là \parallel A\parallel. Cần phân biệt kí hiệu này với kí hiệu |A| dùng để kí hiệu trị tuyệt đối hoặc định thức của ma trận.

1. Chuẩn của vector

Cho vector \mathbf{x}, chuẩn của \mathbf{x} kí hiệu là \parallel \mathbf{x}\parallel được định nghĩa là một số không âm thỏa mãn các tính chất sau:

1. \parallel \mathbf{x}\parallel \geq 0\parallel \mathbf{x}\parallel = 0 khi và chỉ khi \mathbf{x=0}.

2. \parallel \alpha\mathbf{x}\parallel = |\alpha|\parallel\mathbf{x}\parallel với mọi \alpha \in \mathbb{R}.

3. \parallel \mathbf{x} + \mathbf{y}\parallel \leq \parallel \mathbf{x} \parallel + \parallel \mathbf{y} \parallel (bất đẳng thức tam giác).

Cho vector \mathbf{x} = \left(x_1, x_2, ..., x_n\right)^\mathbf{T}. Trong thực tế người ta hay sử dụng một số dạng chuẩn sau:

Chuẩn-p

Cho p\geq 0 là số thực, chuẩn-p được định nghĩa là:

\displaystyle \parallel\mathbf{x}\parallel_p = \left(\sum_{i=1}^{n}|x_i|^p\right)^{\frac{1}{p}}

Với p=1, 2, \infty ta được các dạng chuẩn Manhattan, Euclide và chuẩn cực đại, tương ứng theo thứ tự đó.

Với 0 < p < 1, hàm khoảng cách này không thỏa bất đẳng thức tam giác nên nó không phải là một chuẩn.

Chuẩn Manhattan

Trong công thức chuẩn-p, cho p=1 ta được

\displaystyle \parallel\mathbf{x}\parallel_1 =\sum_{i=1}^{n}|x_i|

Chuẩn này còn được gọi là chuẩn Taxicab, chuẩn Manhattan hoặc đơn giản là chuẩn \mathbf{L_1}. Khoảng cách tương ứng thường được gọi là khoảng cách Manhattan, khoảng cách \mathbf{L_1}.

Lưu ý rằng \parallel\mathbf{x}\parallel_1 =\sum_{i=1}^{n}x_i không phải là một chuẩn vì nó có thể cho kết quả âm.

Chuẩn Euclide

Trong công thức chuẩn-p, cho p=2 ta được

\displaystyle \parallel\mathbf{x}\parallel_2 = \left(\sum_{i=1}^{n}|x_i|^2\right)^{\frac{1}{2}}=\sqrt{x_1^2+x_2^2+...+x_n^2} = \sqrt{\mathbf{x}^\mathrm{T}\mathbf{x}}

Chuẩn Euclide còn được gọi là chuẩn \mathbf{L_2}.

Chuẩn vô cực

Trong công thức chuẩn-p, khi p \rightarrow +\infty ta được chuẩn cực đại

\displaystyle \parallel\mathbf{x}\parallel_\infty = \max\left(|x_1|, |x_2|, ..., |x_n|\right)

Ngoài ra người ta còn định nghĩa chuẩn cực tiểu, tương ứng với trường hợp p \rightarrow -\infty:

\displaystyle \parallel\mathbf{x}\parallel_\infty = \min\left(|x_1|, |x_2|, ..., |x_n|\right)

Tương tự ở trên, lưu ý rằng \max\left(x_1, x_2, ..., x_n\right), \min\left(x_1, x_2, ..., x_n\right) đều không phải là chuẩn.

Chuẩn khác

Kết hợp các dạng chuẩn trên, ta có thể có nhiều dạng chuẩn mới. Chẳng hạn

\parallel\mathbf{x}\parallel = 2|x_1| + \sqrt{3|x_2|^2 + \max\left(|x_3|,|x_4|\right)^2}

cũng là một dạng chuẩn.

Hình 1 cho một cái nhìn về vòng tròn đơn vị trong không gian 2 chiều, ứng với mỗi dạng chuẩn. (“vòng tròn đơn vị” – unit circle – là tập tất cả các điểm trong không gian có chuẩn bằng 1).

"Vòng tròn đơn vị" của dạng chuẩn vô cực, Euclide và Manhattan.

2. Chuẩn của ma trận

Cho ma trận \mathbf{A} kích thước m\times n, chuẩn của \mathbf{A} kí hiệu \parallel\mathbf{A}\parallel theo định nghĩa là một số không âm thỏa:

1. \parallel \mathbf{A}\parallel \geq 0\parallel \mathbf{A}\parallel = 0 khi và chỉ khi \mathbf{A}=\mathbf{0}_{m\times n}.

2. \parallel \alpha\mathbf{A}\parallel = |\alpha|\parallel\mathbf{A}\parallel với mọi \alpha.

3. \parallel \mathbf{A} + \mathbf{B}\parallel \leq \parallel \mathbf{A} \parallel + \parallel \mathbf{B} \parallel (bất đẳng thức tam giác).

Không giống như vector, các dạng chuẩn đều được “phái sinh” từ một chuẩn duy nhất là chuẩn-p, các dạng chuẩn của ma trận có thể xem như thuộc vào một (vài) trong 3 “nguồn gốc” sau đây:

Chuẩn toán tử (operator norm)

Nếu ma trận A thuộc không gian vector K^{m\times n} thì chuẩn của A tương ứng với chuẩn-p của vector là

\parallel\mathbf{A}\parallel_p=\max_{\mathbf{x\neq 0}}\frac{\parallel\mathbf{Ax}\parallel_p}{\parallel\mathbf{x}\parallel_p}

với x\in K^n.

Trường hợp đặc biệt, với p=1 thì chuẩn toán tử trở thành chuẩn cực đại theo cột:

\parallel\mathbf{A}\parallel_1=max_{1\leq j\leq n}\sum_{i=1}^m|a_{ij}|,

để tìm chuẩn này, ta cộng giá trị tuyệt đối của các phần tử trong cùng một cột, sau đó lấy kết quả lớn nhất.

Với p=\infty, chuẩn toán tử trở thành chuẩn cực đại theo dòng:

\parallel\mathbf{A}\parallel_\infty=max_{1\leq i\leq m}\sum_{j=1}^n|a_{ij}|.

Với p=2m=n, ta được dạng chuẩn Euclide của ma trận (thực ra được gọi là spectrum norm), được tính bằng giá trị lớn nhất trong các singular value của \mathbf{A}. (Singular value sẽ được đề cập trong một bài khác, khi viết về SVD).

\parallel\mathbf{A}\parallel_2=\max\left(svd\left(\mathbf{A}\right)\right)

Ví dụ:

Với A = \left( \begin{array}{ccc} 4 & 1 & 3 \\ 5 & 7 & 9 \\ 1 & 9 & 2 \end{array} \right) thì

\parallel\mathbf{A}\parallel_1=17 (tổng của cột thứ 2)

\parallel\mathbf{A}\parallel_2\approx 15.11 (vì svd\left(\mathbf{A}\right)\approx\left( \begin{array}{ccc} 15.11 & 5.97 & 1.72\end{array} \right)^\mathrm{T})

\parallel\mathbf{A}\parallel_\infty = 21 (tổng của dòng thứ 2).

Chuẩn từng phần tử (“Entrywise” norm)

Áp dụng một cách “trực tiếp” chuẩn-p của vector đối với từng phần tử của ma trận, ta được loại chuẩn tương đối trực quan này.

\displaystyle \parallel\mathbf{A}\parallel_p = \left(\sum_{i=1}^n\sum_{j=1}^m|a_{ij}|^p\right)^\frac{1}{p}

Để ý rằng người ta vẫn kí hiệu là \parallel\mathbf{A}\parallel_p mặc dù chuẩn này hoàn toàn khác với chuẩn toán tử bên trên.

Trường hợp đặc biệt p = 2 được gọi là chuẩn Frobenius, và p = \infty chính là chuẩn cực đại.

Chuẩn Frobenius có nhiều cách định nghĩa khác nhau:

\parallel\mathbf{A}\parallel_F=\sqrt{\sum_{i=1}^n\sum_{j=1}^m|a_{ij}|^2}=\sqrt{tr\left(\mathbf{A^*A}\right)}=\sqrt{\sum_{i=1}^{\min\left(m,n\right)}\sigma_i^2}

với \mathbf{A^*} là ma trận conjugate transpose của \mathbf{A}, tr\left(\mathbf{X}\right) là tổng các phần tử trên đường chéo chính của \mathbf{X}\sigma_i là các singular value của A.

Để ý sự tương tự giữa \sqrt{tr\left(\mathbf{A^*A}\right)} và công thức chuẩn Euclide của vector \sqrt{\mathbf{x}^\mathrm{T}\mathbf{x}}.

Chuẩn Schatten

Ta biết, nếu chưa thì sẽ biết trong một entry khác, các singular values của ma trận tạo thành một vector, và áp dụng chuẩn-p của vector cho vector các singular values của ma trận \mathbf{A} ta được chuẩn Schatten

\parallel\mathbf{A}\parallel_p=\left(\sum_{i=1}^{\min\left(m,n\right)}\sigma_i^p\right)^\frac{1}{p}

Một lần nữa ta dùng kí hiệu \parallel\mathbf{A}\parallel_p, nhưng cần nhớ là 3 dạng chuẩn-p này có cách định nghĩa ban đầu hoàn toàn khác nhau (mặc dù một số trường hợp đặc biệt cho thấy cả 3 là như nhau).

Trường hợp p=\infty sẽ là chuẩn cực đại của vector như bình thường. p=2 chính là định nghĩa của chuẩn Frobenius.

Cuối cùng p=1 là chuẩn hạt nhân (nuclear norm, hay Ky Fan norm – lấy theo tên một nhà Toán học gốc Hoa):

\parallel\mathbf{A}\parallel_*=tr\left(\sqrt{\mathbf{A^*A}}\right)=\sum_{i=1}^{\min\left(m,n\right)}\sigma_i

_____________________________________

Hầu như tất cả các dạng chuẩn này đều được cài đặt sẵn trong MATLAB, hoặc có thể được tính chỉ bằng một vài hàm đơn giản.

Vậy những dạng chuẩn này thường dùng làm gì? Câu trả lời là….

Đáng lẽ sẽ có phần 2, nói về một số khái niệm thông thường nhưng là không thông thường đối với những ai không chuyên ngành Toán, tuy nhiên xin dành lại cho một entry khác đầy đủ hơn.

Advertisements

29 comments

  1. hi Vu, cho mjh hoi chuan Euclide o đay co phai la chuan Euclidian ko? neu ko phai thi c co bit chuan Euclidian la chuan j ko? no dc tinh nhu the nao? thanks c

  2. Hi Huệ,
    Chuẩn Euclidean, còn gọi là chuẩn L2. Trong bài này mình gọi là chuẩn Euclide, chính là nó đó 🙂

  3. Good article! Giờ cho anh chém gió tí nha 😛

    Từ cái này viết thêm về metric space và pseudo-metric space đi. Đợt trước làm manifold learning anh cũng có tìm hiểu sơ qua mấy cái thứ này. Tiếc là không có thời gian và động lực ghi lại 😀

    Liên quan đến mấy cái norm space, topological space, ta có cái space hay thường dùng là metric space mà trên đó một metric (độ đo) được định nghĩa. Ví dụ sát sườn là không gian metric Euclid.

    Ngoài distance giữa 2 điểm, ta còn có thể đo khoảng cách giữa hai tập hợp, từ đó có độ đo Hausdorff.

    Nếu đo khoảng cách giữa hai phân phối (distribution), ta có độ đo quen thuộc Kullback-Leibler divergence (trong Information Theory). KL-div không có tính đối xứng, tức là đo từ P sang Q khác với từ Q sang P 😀 KL-div dùng để tính mức độ tương đồng giữa phân phối gốc P (thường unknown) và phân phối xấp xỉ Q.

    Bhattacharyya distance cũng dùng để đo sự tương đồng giữa hai phân phối, nhưng nó không tuân thủ BDT Cauchy-Schwatz.

    Nếu đo giữa hai điểm có cùng phân phối, Mahalanobis distance là một cách. Nếu để ý sẽ phát hiện ra nó nằm trong công thức của phân phối Gauss 😀

    Quay lại cái divergence, thể tổng quát hóa của nó là họ f-divergence, đo sự tương đồng giữa hai phân phối bất kỳ. Tuy nhiên cái này thì không rõ lắm, chỉ biết một divergence khá tổng quát là Bregman. Bregman divergence là cái nhìn từ một định lý trong Convex Optimization, trong đó giá trị Bregman bằng độ khác biệt giữa trị thật của hàm lồi F tại điểm q so với khai triển Taylor của hàm F đó cũng tại q (tham khảo lại Wiki cho nhớ :)) Cái định lý này rất đẹp trong tối ưu lồi.

    Mà cái norm này mà muốn hiểu sâu chắc phải đọc thêm Hilbert space quá T_T Bữa có nếm cuốn này chương đầu, sau rồi bỏ cuộc vì dài hơi quá.

    Lướt qua vậy đủ thấy sự liên quan khủng khiếp và phức tạp giữa các khái niệm và ngành, i.e. Optimization, Information Theory, Statistics.

    Chém gió vậy đủ rồi, thế mấy cái metric này có nghĩa địa gì trong bài toàn computer vision hay machine learning không? Một ứng dụng thú vị là bài toán distance function learning trong ML, cho phép “học” cách tính độ tương đồng giữa hai ảnh thay vì dùng một độ đo vô cảm nào đó. 😀 Một lần nữa, nó được khai triển ở dạng tối ưu lồi có ràng buộc một objective function T_T

  4. Giờ e cũng chả nhớ tại sao em lại viết bài này nữa 😀 Lúc đến đoạn cuối muốn liệt kê vài ứng dụng của norm nhưng cũng không rõ ứng dụng là gì, tuy nhiên vì lâu lâu lại thấy nhắc tới nó nên gom hết lại về 1 chỗ cho lành.

    Còn metric/distance function đúng là 1 phần quan trọng để hiểu nhiều thuật toán trong ML, nhưng mà ko dc học bài bản nên phải chịu thôi ^^

  5. Hi Long,
    Như mình nói trong bài, chuẩn cho ma trận được định nghĩa bằng 3 cách khác nhau, gồm operator norm, entrywise norm và Schatten norm. Mỗi cách đều có định nghĩa dạng \parallel A\parallel_p, tùy giá trị của p là 1, 2 hay inf thì sẽ có cách tính khác nhau.
    Như vậy bạn phải nói rõ là bạn dùng định nghĩa nào mới được.
    Còn ma trận vuông thì cứ tính bình thường thôi, có điều m = n.

  6. Hi Như,
    Chuẩn vô cực chỉ là tổng trị tuyệt đối các phần tử trên cùng 1 dòng của ma trận, sau đó lấy tổng lớn nhất. Trong bài đã có ví dụ rồi.
    Trong Matlab, em có thể dùng hàm abs() để tính trị tuyệt đối, và sum() để tính tống, sau đó dùng hàm max() để tìm tổng lớn nhất.

  7. Em cám ơn anh! Nhưng anh ơi, bài tập của em không được phép sử dụng hàm có sẳn trong matlab. Em phải viết một đoạn code để giải quyết bài toán này. Vậy thì phải làm như thế nào anh?

  8. Anh ơi, em đang làm bài tập matlab nhưng có một số thuật toán liên quan đến ĐSTT em loay hoay mãi mà không biết làm sao? Anh có thể viết code giúp em được không? Em cảm ơn anh nhiều! ĐỂ tài là:
    STT Câu hỏi Yêu cầu, hướng dẫn Đầu vào Đầu ra
    1 Chéo hóa ma trận vuông A. Cho phép sử dụng hàm matlab:
    [V,D]=eig(A).
    Nhập ma trận vuông A. Thông báo nếu A không vuông.
    Thông báo nếu không chéo hóa được.
    Ma trận chéo D và ma trận khả nghịch P.
    2 Cho vécto a và b: tính độ dài vécto
    a; tích vô hướng; tích có hướng và
    góc giữa hai vécto a và b.
    Cho phép sử dụng các hàm của
    matlab: norm(a); a’*b; cross(a,b);
    acos((a*b’)/(norm(a)*norm(b))).
    Nhập các vécto a, b.
    Sử dụng tích vô hướng
    chính tắc.
    độ dài, tích vô hướng, tích có hướng, góc,
    khoảng cách.
    3 Cho ánh xạ tuyến tính f biết ma
    trận của f trong cơ sở E là A. Tìm
    ảnh của vécto x.
    Cho phép sử dụng các hàm matlab:
    giải hệ: X=A\b; rank() để kiểm tra
    tính độc lập tuyến tính, nhân hai ma
    trận với nhau.
    Nhập cơ sở E.
    Nhập ma trận A.
    Nhập vécto x.
    Thông báo nếu E không là cơ sở.
    Thông báo nếu E, A, x tương thích.
    Xuất ra f(x).
    4 Tổng các phần tử trên đường chéo
    của ma trận vuông được gọi là vết
    của ma trận này. Cho A là ma trận
    tùy ý. Vết của ma trận
    T
    A A được
    gọi là chuẩn Frobenius của ma trận
    A. Lập chương trình tính chuẩn
    Frobenius của ma trận tùy ý.
    Chỉ được phép sử dụng hàm matlab:
    tính tích của hai ma trận
    T
    A và A.
    Nhập ma trận A tùy ý. Chuẩn Frobenius của ma trận A.
    5 Dùng biến đổi sơ cấp đối với hàng,
    đưa ma trận về dạng bậc thang.
    Không được phép dùng các lệnh đưa
    về bậc thang và tìm hạng của matlab.
    Nhập ma trận A tùy ý. Dạng bậc thang của ma trận A.

  9. Hi you. Bạn có thew63 giải quyết thấu đáo bài toán của SV này không ? CHo $A,B\in M_{m*n}$ thì người ta định nghĩa :
    $$\left \| A \right \|=max\left \{ \left |a_{ij} \right |\right \}$$
    CHứng mninh rằng khi $m=n$ thì$ \left \| AB \right \|\leq \left \| A \right \|\left \| B \right \|$

    1. Ủa vậy cho em hỏi chuẩn x trong không gian l^p(lebesgue) thì tính chuẩn nó như thế nào trong matlab, vd ||x||_2 = (int_{a}^{b}(x_n)^2)^1/2, tks

  10. ủa vậy thì đối với chuẩn l^p trong không gian lebesgue, với chuẩn ||x|| = (int_{a}^{b}(x_n)^p)^(1/p) thì công thức trong matlab là hàm nào, em không thấy vậy a

  11. “Hình 1 cho một cái nhìn về vòng tròn đơn vị trong không gian 2 chiều, ứng với mỗi dạng chuẩn. (“vòng tròn đơn vị” – unit circle – là tập tất cả các điểm trong không gian có chuẩn bằng 1).”

    dạ chào anh, em mới tìm hiểu vê ML, em đang tìm hiểu về overfiting, phần regularization. Em không hiểu là cụ thể L1 và L2 nó giảm overfiting như thế nào . regularized loss function mới sẽ có đặt điểm gì khác biệt so với loss function ban đầu . Khi nào chúng ta nên dùng L1 và khi nào nên dùng L2. Em có giải thích giúp em bằng việc so sánh 2 hàm này được không.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s