Ôn tập Đại số tuyến tính
Ôn tập Đại số tuyến tính
Theo blog: http://machinelearningcoban.com
Vũ Hữu Tiệp, 2017
1 Lưu ý về ký hiệu
Trong các bài viết của tôi, các số vô hướng được biểu diễn bởi các chữ cái viết ở dạng không
in đậm, có thể viết hoa, ví dụ x1, N, y, k. Các vector được biểu diễn bằng các chữ cái thường
in đậm, ví dụ y, x1. Nếu không giải thích gì thêm, các vector được mặc định hiểu là các
vector cột. Các ma trận được biểu diễn bởi các chữ viết hoa in đậm, ví dụ X, Y, W.
Đối với vector, x = [x1, x2, . . . , xn] được hiểu là một vector hàng. Trong khi x = [x1; x2; . . . ; xn]
được hiểu là vector cột. Chú ý sự khác nhau giữa dầu phẩy (,) và dấu chấm phẩy (;). Đây
chính là ký hiệu được Matlab sử dụng.
Tương tự, trong ma trận, X = [x1, x2, . . . , xn] được hiểu là các vector cột xj được đặt cạnh
nhau theo thứ tự từ trái qua phải để tạo ra ma trận X. Trong khi X = [x1; x2; . . . ; xm] được
hiểu là các vector xi được đặt chồng lên nhau theo thứ tự từ trên xuống dưới dể tạo ra ma
trận X. Các vector được ngầm hiểu là có kích thước phù hợp để có thể xếp cạnh hoặc xếp
chồng lên nhau.
Cho một ma trận W, nếu không giải thích gì thêm, chúng ta hiểu rằng wi là vector cột
thứ i của ma trận đó. Chú ý sự tương ứng giữa ký tự viết hoa và viết thường.
2 Norms (chuẩn)
Trong không gian một chiều, việc đo khoảng cách giữa hai điểm đã rất quen thuộc: lấy trị
tuyệt đối của hiệu giữa hai giá trị đó. Trong không gian hai chiều, tức mặt phẳng, chúng ta
thường dùng khoảng cách Eclid để đo khoảng cách giữa hai điểm. Khoảng cách này chính
là cái chúng ta thường nói bằng ngôn ngữ thông thường là đường chim bay. Đôi khi, để đi
từ một điểm này tới một điểm kia, con người chúng ta không thể đi bằng đường chim bay
được mà còn phụ thuộc vào việc đường đi nối giữa hai điểm có dạng như thế nào nữa.
Việc đo khoảng cách giữa hai điểm dữ liệu nhiều chiều, tức hai vector, là rất cần thiết trong
Machine Learning. Chúng ta cần đánh giá xem điểm nào là điểm gần nhất của một điểm
khác; chúng ta cũng cần đánh giá xem độ chính xác của việc ước lượng; và trong rất nhiều
ví dụ khác nữa.
Và đó chính là lý do mà khái niệm norm (chuẩn) ra đời. Có nhiều loại norm khác nhau mà
1
các bạn sẽ thấy ở dưới đây:
Để xác định khoảng cách giữa hai vector y và z, người ta thường áp dụng một hàm số lên
vector hiệu x = y − z. Một hàm số được dùng để đo các vector cần có một vài tính chất
đặc biệt.
2.1 Định nghĩa
Một hàm số f() ánh xạ một điểm x từ không gian n chiều sang tập số thực một chiều được
gọi là norm nếu nó thỏa mãn ba điều kiện sau đây:
1. f(x) ≥ 0. Dấu bằng xảy ra ⇔ x = 0.
2. f(αx) = kαkf(x), ∀α ∈ R
3. f(x1) + f(x2) ≥ f(x1 + x2), ∀x1, x2 ∈ Rn
Điều kiện thứ nhất là dễ hiểu vì khoảng cách không thể là một số âm. Hơn nữa, khoảng
cách giữa hai điểm y và z bằng 0 nếu và chỉ nếu hai điểm nó trùng nhau, tức x = y − z = 0.
Điều kiện thứ hai cũng có thể được lý giải như sau. Nếu ba điểm y, v và z thẳng hàng,
hơn nữa v − y = α(v − z) thì khoảng cách giữa v và y sẽ gấp kαk lần khoảng cách giữa v
và z.
Điều kiện thứ ba chính là bất đẳng thức tam giác nếu ta coi x1 = w − y, x2 = z − w với
w là một điểm bất kỳ trong cùng không gian.
2.2 Một số chuẩn thường dùng
Giả sử các vectors x = [x1; x2; . . . ; xn], y = [y1; y2; . . . ; yn].
Nhận thấy rằng khoảng cách Euclid chính là một norm, norm này thường được gọi là norm
2:
q
kxk2 = x21 + x22 + . . . x2n
(1)
Với p là một số không nhỏ hơn 1 bất kỳ, hàm số sau đây:
1
p
p
p
p
kxkp = (kx1k + kx2k + . . . kxnk )
(2)
được chứng minh thỏa mãn ba điều kiện bên trên, và được gọi là norm p.
2
kx − yk1 = |x1 − y1| + |x2 − y2|
x
x2
|x1 − y1|
y
y2
z
y1
Figure 1: Minh họa norm 1 và norm 2
x1
Nhận thấy rằng khi p → 0 thì biểu thức bên trên trở thành số các phần tử khác 0 của x.
không thỏa mãn điều kiện 2 và 3 của norm. Giả-chuẩn này, thường được ký hiệu là kxk0,
khá quan trọng trong Machine Learning vì trong nhiều bài toán, chúng ta cần có ràng buộc
“sparse”, tức số lượng thành phần “active” của x là nhỏ.
Có một vài giá trị của p thường được dùng:
1. Khi p = 2 chúng ta có norm 2 như ở trên.
2. Khi p = 1 chúng ta có:
kxk1 = kx1k + kx2k + . . . kxnk
(3)
là tổng các trị tuyệt đối của từng phần tử của x. Norm 1 thường được dùng như xấp
xỉ của norm 0 trong các bài toán có ràng buộc "sparse". Dưới đây là một ví dụ so
sánh norm 1 và norm 2 trong không gian hai chiều:
Norm 2 (màu xanh) chính là đường thằng "chim bay" nối giữa hai vector x và y.
Khoảng cách norm 1 giữa hai điểm này (màu đỏ) có thể diễn giải như là đường đi từ
x tới y trong một thành phố mà đường phố tạo thành hình bàn cờ. Chúng ta chỉ có
cách đi dọc theo cạnh của bàn cờ mà không được đi thẳng.
3. Khi p → ∞, ta có norm p chính là trị tuyệt đối của phần tử lớn nhất của vector đó:
kxk∞ = max kxik
(4)
i=1,2,...,n
3
2.3 Chuẩn của ma trận
Với một ma trận A ∈ Rm×n, chuẩn thường được dùng nhất là chuẩn Frobenius, ký hiệu là
kAkF là căn bậc hai của tổng bình phương tất cả các phần tử của ma trận đó.
v
u
m
n
X X
u
t
kAkF =
a2ij
i=1 j=1
3 Đạo hàm của hàm nhiều biến
Trong mục này, chúng ta sẽ giả sử rằng các đạo hàm tồn tại. Chúng ta sẽ xét hai trường
hợp: i) Hàm số nhận giá trị là ma trận (vector) và cho giá trị là một số thực vô hướng; và
ii) Hàm số nhận giá trị là một số vô hướng hoặc vector và cho giá trị là một vector.
3.1 Hàm cho giá trị là một số vô hướng
n
Đạo hàm (gradient) của một hàm số f(x) : R → R theo vector x được định nghĩa như
sau:
∂f(x)
∂x1
∂f(x)
∂x2
n
∇xf(x) ,
∈ R
(5)
.
.
.
∂f(x)
∂xn
∂f(x)
∂xi
trong đó
là đạo hàm của hàm số theo thành phần thứ i của vector x. Đạo hàm này
được lấy khi giả sử tất cả các biến còn lại là hằng số.
Nếu không có thêm biến nào trong hàm số, ∇xf(x) thường được viết gọn là ∇f(x).
Điều quan trọng cần nhớ: đạo hàm của hàm số này là một vector có cùng chiều với
vector đang lấy đạo hàm. Tức nếu vector viết ở dạng cột thì đạo hàm cũng phải viết ở
dạng cột.
Đạo hàm bậc hai (second-order gradient) của hàm số trên còn được gọi là Hessian và được
định nghĩa như sau:
4
∂2f(x)
∂x21
∂2f(x)
∂x1x2
∂2f(x)
∂x22
∂2f(x)
. . .
. . .
∂x1xn
∂2f(x)
∂x2x1
∂ f(x)
∂x2xn
2
2
n
.
.
.
.
.
.
.
.
.
.
.
.
∇ f(x) ,
∈ S
(6)
∂2f(x)
∂2f(x)
∂2f(x)
. . .
∂xnx1
∂xnx2
∂x2n
n
n×n
với S ∈ R
là tập các ma trận vuông đối xứng có số cột là n.
n×m
Đạo hàm của một hàm số f(X) : R
→ R theo ma trận X được định nghĩa là:
∂f(X)
∂x11
∂f(X)
∂x21
∂f(X)
∂x12
∂f(X)
∂x22
∂f(X)
∂x1m
∂f(X)
∂x2m
. . .
. . .
.
n×m
∇f(X) =
∈ R
(7)
.
.
.
.
.
.
.
.
.
.
.
∂f(X)
∂f(X)
∂f(X)
. . .
∂xn1
∂xn2
∂xnm
Một lần nữa, đạo hàm của một hàm số theo ma trận là một ma trận có chiều giống với ma
trận đó.
Hiểu một cách đơn giản, đạo hàm của một hàm số (có đầu ra là 1 số vô hướng) theo một
ma trận được tính như sau. Trước tiên, tính đạo hàm của hàm số đó theo từng thành phần
của ma trận khi toàn bộ các thành phần khác được giả sử là hằng số. Tiếp theo, ta ghép các
đạo hàm thành phần tính được thành một ma trận đúng theo thứ tự như trong ma trận đó.
Chú ý rằng vector là một trường hợp của ma trận.
2
Ví dụ: Xét hàm số: f : R → R, f(x) = x21 + 2x1x2 + sin(x1) + 2.
Đạo hàm bậc nhất theo x của hàm số đó là:
"
#
ꢀ
ꢁ
∂f(x)
∂x1
∂f(x)
∂x2
2x1 + 2x2 + cos(x1)
2x1
∇f(x) =
=
Đạo hàm bậc hai theo x, hay Hessian là:
"
#
∂2f(x)
∂f2(x)
∂x1x2
∂f2(x)
∂x22
ꢀ
ꢁ
∂x21
2 − sin(x1) 2
2
∇ f(x) =
=
∂2f(x)
∂x2x1
2
0
Chú ý rằng Hessian luôn là một ma trận đối xứng.
5
3.2 Hàm cho giá trị là một vector
Những hàm số cho giá trị là một vector được gọi là vector-valued function trong tiếng Anh.
n
Giả sử một hàm số với đầu vào là một số thực v(x) : R → R :
v1(x)
v2(x)
v(x) =
(8)
(9)
.
.
.
vn(x)
Đạo hàm của nó là một vector hàng như sau:
h
i
∂v1(x)
∂x
∂v2(x)
∂x
∂vn(x)
∂x
∇v(x) ,
. . .
Đạo hàm bậc hai của hàm số này có dạng:
h
i
∂2v1(x)
∂x2
∂2v2(x)
∂x2
∂2vn(x)
∂x2
2
∇ v(x) ,
(10)
(11)
. . .
n
Ví dụ: Cho vector a ∈ R và vector-valued function v(x) = xa, thế thì:
∇v(x) = aT , ∇ v(x) = 0 ∈ Rn×n
2
với 0 là ma trận với các thành phần đều là 0.
k
n
Xét một vector-valued function với đầu vào là một vector h(x) : R → R , đạo hàm bậc
nhất của nó là:
∂h1(x)
∂x1
∂h1(x)
∂x2
∂h2(x)
∂x1
∂h2(x)
∂x2
∂hn(x)
∂x1
∂hn(x)
∂x2
. . .
. . .
.
∇h(x) ,
(12)
(13)
.
.
.
.
.
.
.
.
.
.
.
∂h1(x)
∂h2(x)
∂hn(x)
. . .
∂xk
∂xk
∂xk
ꢂ
ꢃ
=
∇h1(x) ∇h2(x) . . . ∇hn(x) ∈ Rk×n
m
n
Một quy tắc dễ nhớ ở đây là nếu một hàm số g : R → R thì đạo hàm của nó là
m×n
một ma trận thuộc R
.
Đạo hàm bậc hai của hàm số trên là một ma trận ba chiều, tôi xin không đề cập ở đây.
<hr> Với các hàm số matrix-valued nhận giá trị đầu vào là ma trận, tôi cũng xin không đề
cập ở đây. Tuy nhiên, ở phần dưới, khi tính toán đạo hàm cho các hàm cho giá trị là số
6
thực, chúng ta vẫn có thể sẽ sử dụng khái niệm này.
Trước khi đến phần tính đạo hàm của các hàm số thường gặp, chúng ta cần biết hai tính
chất quan trọng khá giống với đạo hàm của hàm một biến được học trong chương trình cấp
ba.
3.3 Hai tính chất quan trọng
3.3.1 Product rules
Để cho tổng quát, ta giả sử biến đầu vào là một ma trận (vector và số thực là các trường
hợp đặt biệt của ma trận). Giả sử rằng các hàm số có chiều phù hợp để các phép nhân thực
hiện được. Ta có:
ꢄ
ꢅ
∇ f(X)T g(X) = (∇f(X)) g(X) + (∇g(X)) f(X)
(14)
Biểu thức này giống như biểu thức chúng ta đã quá quen thuộc:
(f(x)g(x))0 = f0(x)g(x) + g0(x)f(x)
Chú ý rằng với vector và ma trận, chúng ta không được sử dụng tính chất giao hoán.
3.3.2 Chain rules
Khi có các hàm hợp thì:
∇Xg(f(X)) = ∇XfT ∇f g
(15)
Quy tắc này cũng giống với quy tắc trong hàm một biến:
(g(f(x))0 = f0(x)g0(f)
Nhắc lại rằng khi tính toán với ma trận, chúng ta cần chú ý tới chiều của các ma trận, và
nhân ma trận không có tính chất giao hoán.
7
3.4 Đạo hàm của các hàm số thường gặp
3.4.1 f(x) = aT x
n
Giả sử a, x ∈ R , ta viết lại:
f(x) = aT x = a1x1 + a2x2 + · · · + anxn
Có thể nhận thấy rằng:
∂f(x)
= ai, ∀i = 1, 2 . . . , n
∂xi
Vậy nên:
a1
a2
.
.
.
∇f(x) =
= a
an
Thêm nữa, vì aT x = xT a nên:
3.4.2 f(x) = Ax
∇(xT a) = a
n
m
n
Đây là một vector-valued function f : R → R với x ∈ R , A ∈ Rm×n. Giả sử rằng ai là
hàng thứ i của ma trận A. Ta có:
a1x
a2x
.
.
.
Ax =
amx
Theo định nghĩa (13.2), và công thức (17), ta có thể suy ra:
ꢂ
ꢃ
∇x(Ax) = aT1 a2T . . . aTm = AT
(16)
Từ đây ta có thể suy ra đạo hàm của hàm số f(x) = x = Ix, với I là ma trận đơn vị với
chiều phù hợp, là:
∇x = I
8
3.4.3 f(x) = xT Ax
n
với x ∈ R , A ∈ Rn×n. Áp dụng Product rules (14) ta có:
ꢄꢄ
ꢅ
ꢅ
∇f(x) = ∇ xT (Ax)
= (∇(x)) Ax + (∇(Ax)) x
= IAx + AT x
= (A + AT )x
(17)
2
Nếu A là một ma trận đối xứng, ta sẽ có:
2
∇xT Ax = 2Ax, ∇ xT Ax = 2A
(18)
(19)
Nếu A là ma trận đơn vị, tức f(x) = xT Ix = xT x = kxk2, ta có:
2
2
2
2
∇kxk2 = 2x, ∇ kxk2 = 2I
2
3.4.4 f(x) = kAx − bk2
Có hai cách tính đạo hàm của hàm số này:
Cách 1: Trước hết, biến đổi:
2
f(x) = kAx − bk2 = (Ax − b)T (Ax − b) = (xT AT − bT )(Ax − b)
= xT AT Ax − 2bT Ax + bT b
Lấy đạo hàm cho từng số hạng rồi cộng lại ta có:
2
∇kAx − bk2 = 2AT Ax − 2AT b = 2AT (Ax − b)
2
Cách 2: Dùng Chain rule. Sử dụng ∇(Ax − b) = AT và ∇kxk2 = 2x và công thức chain
3.4.5 f(x) = aT xxT b
Bằng cách viết lại f(x) = (aT x)(xT b), ta có thể dùng Product rules (14) và ra kết quả:
∇(aT xxT b) = axT b + baT x = abT x + baT x = (abT + baT )x
9
trong đây tôi đã sử dụng tính chất yT z = zT y và tích của một số thực với một vector cũng
bằng tích của vector và số thực đó.
3.5 Bảng các đạo hàm thường gặp
3.5.1 Cho vector
Table 1: Đạo hàm theo vector
f(x)
aT x
∇f(x)
a
A + AT )x
2x
xT Ax
xT x = kxk2
2
kAx − bk2 2AT (Ax − b)
2
aT xT xb
aT xxT b
2aT bx
(abT + baT )x
3.5.2 Cho ma trận
Table 2: Đạo hàm theo ma trận
f(X)
∇f(X)
2
kXkF
2X
AX
AT
kAX − BkF 2AT (AX − B)
2
kXA − BkF 2(XA − B)AT
2
aT XT Xb
aT XXT b
aT YXT b
aT YT Xb
aT XYT b
aT XT Yb
X(abT + baT )
(abT + baT )X,
baT Y
YabT
abT Y
YbaT
3.6 Tài liệu tham khảo
[1] Matrix calculus
10
10 trang
14920
Free
Bạn đang xem tài liệu "Ôn tập Đại số tuyến tính", để tải tài liệu gốc về máy hãy click vào nút Download ở trên
File đính kèm:
- on_tap_dai_so_tuyen_tinh.pdf
