convexity_vn.md

Tính lồi

🏷️sec_convexity

Tính lồi đóng vai trò then chốt trong việc thiết kế các thuật toán tối ưu. Điều này phần lớn là do tính lồi giúp việc phân tích và kiểm tra thuật toán trở nên dễ dàng hơn. Nói cách khác, nếu thuật toán hoạt động kém ngay cả khi có tính lồi thì ta không nên kì vọng rằng sẽ thu được kết quả tốt trong trường hợp khác. Hơn nữa, mặc dù các bài toán tối ưu hóa trong học sâu đa phần là không lồi, chúng lại thường thể hiện một số tính chất lồi gần các cực tiểu. Điều này dẫn đến các biến thể tối ưu hóa thú vị mới như :cite:Izmailov.Podoprikhin.Garipov.ea.2018.

Kiến thức Cơ bản

Chúng ta hãy bắt đầu với các kiến thức cơ bản trước.

Tập hợp

Tập hợp là nền tảng của tính lồi. Nói một cách đơn giản, một tập hợp $X$ trong không gian vector là lồi nếu với bất kì $a, b \in X$, đoạn thẳng nối $a$ và $b$ cũng thuộc $X$. Theo thuật ngữ toán học, điều này có nghĩa là với mọi $\lambda \in [0, 1]$, ta có

$$\lambda \cdot a + (1-\lambda) \cdot b \in X \text{với mọi} a, b \in X.$$

Điều này nghe có vẻ hơi trừu tượng. Hãy xem qua bức ảnh :numref:fig_pacman. Tập hợp đầu tiên là không lồi do tồn tại các đoạn thẳng không nằm trong tập hợp. Hai tập hợp còn lại thì không gặp vấn đề như vậy.

🏷️fig_pacman

Chỉ một mình định nghĩa thôi thì sẽ không có tác dụng gì trừ khi bạn có thể làm gì đó với chúng. Trong trường hợp này, ta có thể nhìn vào phép hợp và phép giao trong :numref:fig_convex_intersect. Giả sử $X$ và $Y$ là các tập hợp lồi, khi đó $X \cap Y$ cũng sẽ lồi. Để thấy được điều này, hãy xét bất kì $a, b \in X \cap Y$. Vì $X$ và $Y$ lồi, khi đó đoạn thẳng nối $a$ và $b$ sẽ nằm trong cả $X$ và $Y$. Do đó, chúng cũng cần phải thuộc $X \cap Y$, từ đó chứng minh được định lý đầu tiên của chúng ta.

🏷️fig_convex_intersect

Ta sẽ củng cố kết quả này thêm một chút với mệnh đề: giao của các tập lồi $X_i$ là một tập lồi $\cap_{i} X_i$. Để thấy rằng điều ngược lại là không đúng, hãy xem xét hai tập hợp không giao nhau $X \cap Y = \emptyset$. Giờ ta chọn ra $a \in X$ và $b \in Y$. Đoạn thẳng nối $a$ và $b$ trong :numref:fig_nonconvex chứa một vài phần không thuộc cả $X$ và $Y$, vì chúng ta đã giả định rằng $X \cap Y = \emptyset$. Do đó đoạn thẳng này cũng không nằm trong $X \cup Y$, từ đó chứng minh rằng hợp của các tập lồi nói chung không nhất thiết phải là tập lồi.

🏷️fig_nonconvex

Thông thường, các bài toán trong học sâu đều được định nghĩa trong các miền lồi. Ví dụ $\mathbb{R}^d$ là tập lồi (xét cho cùng, đoạn thẳng nối hai điểm bất kỳ thuộc $\mathbb{R}^d$ vẫn thuộc $\mathbb{R}^d$). Trong một vài trường hợp, chúng ta sẽ làm việc với các biến có biên, ví dụ như khối cầu có bán kính $r$ được định nghĩa bằng ${\mathbf{x} | \mathbf{x} \in \mathbb{R}^d \text{ và } |\mathbf{x}|_2 \leq r}$.

Hàm số

Giờ ta đã biết về tập hợp lồi, ta sẽ làm việc tiếp với các hàm số lồi $f$. Cho một tập hợp lồi $X$, một hàm số được định nghĩa trên tập đó $f: X \to \mathbb{R}$ là hàm lồi nếu với mọi $x, x' \in X$ và mọi $\lambda \in [0, 1]$, ta có

$$\lambda f(x) + (1-\lambda) f(x') \geq f(\lambda x + (1-\lambda) x').$$

Để minh họa cho điều này, chúng ta sẽ vẽ đồ thị của một vài hàm số và kiểm tra xem hàm số nào thỏa mãn điều kiện trên. Ta sẽ cần phải nhập một vài gói thư viện.

%matplotlib inline
from d2l import mxnet as d2l
from mpl_toolkits import mplot3d
from mxnet import np, npx
npx.set_np()

Hãy định nghĩa một vài hàm số, cả lồi lẫn không lồi.

#@tab all
f = lambda x: 0.5 * x**2  # Convex
g = lambda x: d2l.cos(np.pi * x)  # Nonconvex
h = lambda x: d2l.exp(0.5 * x)  # Convex

x, segment = d2l.arange(-2, 2, 0.01), d2l.tensor([-1.5, 1])
d2l.use_svg_display()
_, axes = d2l.plt.subplots(1, 3, figsize=(9, 3))
for ax, func in zip(axes, [f, g, h]):
    d2l.plot([x, segment], [func(x), func(segment)], axes=ax)

Như dự đoán, hàm cô-sin là hàm không lồi, trong khi hàm parabol và hàm số mũ là hàm lồi. Lưu ý rằng để điều kiện trên có ý nghĩa thì $X$ cần phải là tập hợp lồi. Nếu không, kết quả của $f(\lambda x + (1-\lambda) x')$ sẽ không được định nghĩa rõ. Các hàm lồi có một số tính chất mong muốn sau.

Bất đẳng thức Jensen

Một trong những công cụ hữu dụng nhất là bất đẳng thức Jensen. Nó là sự tổng quát hóa của định nghĩa về tính lồi:

$$\begin{aligned} \sum_i \alpha_i f(x_i) & \geq f\left(\sum_i \alpha_i x_i\right) \text{ và } E_x[f(x)] & \geq f\left(E_x[x]\right), \end{aligned}$$

với $\alpha_i$ là các số thực không âm sao cho $\sum_i \alpha_i = 1$. Nói cách khác, kỳ vọng của hàm lồi lớn hơn hàm lồi của kỳ vọng. Để chứng minh bất đẳng thức đầu tiên này, chúng ta áp dụng định nghĩa của tính lồi cho từng số hạng của tổng. Kỳ vọng có thể được chứng minh bằng cách tính giới hạn trên các đoạn hữu hạn.

Một trong các ứng dụng phổ biến của bất đẳng thức Jensen liên quan đến log hợp lý của các biến ngẫu nhiên quan sát được một phần. Ta có

$$E_{y \sim P(y)}[-\log P(x \mid y)] \geq -\log P(x).$$

Điều này xảy ra vì $\int P(y) P(x \mid y) dy = P(x)$. Nó được sử dụng trong những phương pháp biến phân. $y$ ở đây thường là một biến ngẫu nhiên không quan sát được, $P(y)$ là dự đoán tốt nhất về phân phối của nó và $P(x)$ là phân phối đã được lấy tích phân theo $y$. Ví dụ như trong bài toán phân cụm, $y$ có thể là nhãn cụm và $P(x \mid y)$ là mô hình sinh khi áp dụng các nhãn cụm.

Tính chất

Các hàm lồi có một vài tính chất hữu ích dưới đây.

Không có Cực tiểu Cục bộ

Cụ thể, các hàm lồi không có cực tiểu cục bộ. Hãy giả định điều ngược lại là đúng và chứng minh nó sai. Nếu $x \in X$ là cực tiểu cục bộ thì sẽ tồn tại một vùng lân cận nào đó của $x$ mà $f(x)$ là giá trị nhỏ nhất. Vì $x$ chỉ là cực tiểu cục bộ nên phải tồn tại một $x' \in X$ nào khác mà $f(x') < f(x)$. Tuy nhiên, theo tính lồi, các giá trị hàm số trên toàn bộ đường thẳng $\lambda x + (1-\lambda) x'$ phải nhỏ hơn $f(x')$ với $\lambda \in [0, 1)$

$$f(x) > \lambda f(x) + (1-\lambda) f(x') \geq f(\lambda x + (1-\lambda) x').$$

Điều này mâu thuẫn với giả định rằng $f(x)$ là cực tiểu cục bộ. Ví dụ, hàm $f(x) = (x+1) (x-1)^2$ có cực tiểu cục bộ tại $x=1$. Tuy nhiên nó lại không phải là cực tiểu toàn cục.

#@tab all
f = lambda x: (x-1)**2 * (x+1)
d2l.set_figsize()
d2l.plot([x, segment], [f(x), f(segment)], 'x', 'f(x)')

Tính chất "các hàm lồi không có cực tiểu cục bộ" rất tiện lợi. Điều này có nghĩa là ta sẽ không bao giờ "mắc kẹt" khi cực tiểu hóa các hàm số. Dù vậy, hãy lưu ý rằng điều này không có nghĩa là hàm số không thể có nhiều hơn một cực tiểu toàn cục, hoặc liệu hàm số có tồn tại cực tiểu toàn cục hay không. Ví dụ, hàm $f(x) = \mathrm{max}(|x|-1, 0)$ đạt giá trị nhỏ nhất trên khoảng $[-1, 1]$. Ngược lại, hàm $f(x) = \exp(x)$ không có giá trị nhỏ nhất trên $\mathbb{R}$. Với $x \to -\infty$ nó sẽ tiệm cận tới $0$, tuy nhiên không tồn tại giá trị $x$ mà tại đó $f(x) = 0$.

Hàm số và Tập hợp Lồi

Các hàm số lồi định nghĩa các tập hợp lồi là các tập-dưới (below-sets) như sau:

$$S_b := {x | x \in X \text{ and } f(x) \leq b}.$$

Ta hãy chứng minh nó một cách vắn tắt. Hãy nhớ rằng với mọi $x, x' \in S_b$, ta cần chứng minh $\lambda x + (1-\lambda) x' \in S_b$ với mọi $\lambda \in [0, 1]$. Nhưng điều này lại trực tiếp tuân theo định nghĩa về tính lồi vì $f(\lambda x + (1-\lambda) x') \leq \lambda f(x) + (1-\lambda) f(x') \leq b$.

Hãy nhìn vào đồ thị hàm $f(x, y) = 0.5 x^2 + \cos(2 \pi y)$ bên dưới. Nó rõ ràng là không lồi. Các tập mức tương ứng cũng không lồi. Thực tế, chúng thường được cấu thành từ các tập hợp rời rạc.

#@tab all
x, y = d2l.meshgrid(d2l.linspace(-1, 1, 101), d2l.linspace(-1, 1, 101))
z = x**2 + 0.5 * d2l.cos(2 * np.pi * y)

# Plot the 3D surface
d2l.set_figsize((6, 4))
ax = d2l.plt.figure().add_subplot(111, projection='3d')
ax.plot_wireframe(x, y, z, **{'rstride': 10, 'cstride': 10})
ax.contour(x, y, z, offset=-1)
ax.set_zlim(-1, 1.5)

# Adjust labels
for func in [d2l.plt.xticks, d2l.plt.yticks, ax.set_zticks]:
    func([-1, 0, 1])

Đạo hàm và tính Lồi

Bất cứ khi nào đạo hàm bậc hai của một hàm số tồn tại, việc kiểm tra tính lồi của hàm số là rất đơn giản. Tất cả những gì cần làm là kiểm tra liệu $\partial_x^2 f(x) \succeq 0$, tức là liệu toàn bộ trị riêng của nó đều không âm hay không. Chẳng hạn, hàm $f(\mathbf{x}) = \frac{1}{2} |\mathbf{x}|^2_2$ là lồi vì $\partial_{\mathbf{x}}^2 f = \mathbf{1}$, tức là đạo hàm của nó là ma trận đơn vị.

Có thể nhận ra rằng chúng ta chỉ cần chứng minh tính chất này cho các hàm số một chiều. Xét cho cùng, ta luôn có thể định nghĩa một hàm số $g(z) = f(\mathbf{x} + z \cdot \mathbf{v})$. Hàm số này có đạo hàm bậc một và bậc hai lần lượt là $g' = (\partial_{\mathbf{x}} f)^\top \mathbf{v}$ và $g'' = \mathbf{v}^\top (\partial^2_{\mathbf{x}} f) \mathbf{v}$. Cụ thể, $g'' \geq 0$ với mọi $\mathbf{v}$ mỗi khi ma trận Hessian của $f$ là nửa xác định dương, tức là tất cả các trị riêng của ma trận đều lớn hơn hoặc bằng không. Do đó quay về lại trường hợp vô hướng.

Để thấy tại sao $f''(x) \geq 0$ đối với các hàm lồi, ta dùng lập luận

$$\frac{1}{2} f(x + \epsilon) + \frac{1}{2} f(x - \epsilon) \geq f\left(\frac{x + \epsilon}{2} + \frac{x - \epsilon}{2}\right) = f(x).$$

Vì đạo hàm bậc hai được đưa ra bởi giới hạn trên sai phân hữu hạn, nó dẫn tới

$$f''(x) = \lim_{\epsilon \to 0} \frac{f(x+\epsilon) + f(x - \epsilon) - 2f(x)}{\epsilon^2} \geq 0.$$

Để chứng minh điều ngược lại, ta dùng lập luận rằng $f'' \geq 0$ ngụ ý rằng $f'$ là một hàm tăng đơn điệu. Cho $a < x < b$ là ba điểm thuộc $\mathbb{R}$. Chúng ta sử dụng định lý giá trị trung bình để biểu diễn

$$\begin{aligned} f(x) - f(a) & = (x-a) f'(\alpha) \text{ với } \alpha \in [a, x] \text{ và } \\ f(b) - f(x) & = (b-x) f'(\beta) \text{ với } \beta \in [x, b]. \end{aligned}$$

Từ tính chất đơn điệu $f'(\beta) \geq f'(\alpha)$, ta có

$$\begin{aligned} f(b) - f(a) & = f(b) - f(x) + f(x) - f(a) \\ & = (b-x) f'(\beta) + (x-a) f'(\alpha) \\ & \geq (b-a) f'(\alpha). \end{aligned}$$

Theo hình học, nó dẫn đến $f(x)$ nằm dưới đường thẳng nối $f(a)$ và $f(b)$, do đó chứng minh được tính lồi. Ta sẽ bỏ qua việc chứng minh một cách chính quy và thay bằng đồ thị bên dưới.

#@tab all
f = lambda x: 0.5 * x**2
x = d2l.arange(-2, 2, 0.01)
axb, ab = d2l.tensor([-1.5, -0.5, 1]), d2l.tensor([-1.5, 1])
d2l.set_figsize()
d2l.plot([x, axb, ab], [f(x) for x in [x, axb, ab]], 'x', 'f(x)')
d2l.annotate('a', (-1.5, f(-1.5)), (-1.5, 1.5))
d2l.annotate('b', (1, f(1)), (1, 1.5))
d2l.annotate('x', (-0.5, f(-0.5)), (-1.5, f(-0.5)))

Ràng buộc

Một trong những tính chất hữu ích của tối ưu hóa lồi là nó cho phép chúng ta xử lý các ràng buộc một cách hiệu quả. Nó cho phép ta giải quyết các bài toán dưới dạng:

$$\begin{aligned} \mathop{\mathrm{cựctiểuhóa}}_{\mathbf{x}} & f(\mathbf{x}) \\ \text{theo} & c_i(\mathbf{x}) \leq 0 \text{vớimọi~} i \in {1, \ldots, N}. \end{aligned}$$

$f$ ở đây là mục tiêu và các hàm $c_i$ là các hàm số ràng buộc. Hãy xem nó xử lý thế nào trong trường hợp $c_1(\mathbf{x}) = |\mathbf{x}|_2 - 1$. Ở trường hợp này, các tham số $\mathbf{x}$ bị ràng buộc vào khối cầu đơn vị. Nếu ràng buộc thứ hai là $c_2(\mathbf{x}) = \mathbf{v}^\top \mathbf{x} + b$ thì điều này ứng với mọi $\mathbf{x}$ nằm trên nửa khoảng. Đáp ứng đồng thời hai ràng buộc này nghĩa là chọn ra một lát cắt của khối cầu làm tập hợp ràng buộc.

Hàm số Lagrange

Nhìn chung, giải quyết một bài toán tối ưu hóa bị ràng buộc là tương đối khó khăn. Có một cách giải quyết bắt nguồn từ vật lý dựa trên một trực giác khá đơn giản. Hãy tưởng tượng có một quả banh bên trong một chiếc hộp. Quả banh sẽ lăn đến nơi thấp nhất và trọng lực sẽ cân bằng với lực nâng của các cạnh hộp tác động lên quả banh. Tóm lại, gradient của hàm mục tiêu (ở đây là trọng lực) sẽ được bù lại bởi gradient của hàm ràng buộc (cần phải nằm trong chiếc hộp, bị các bức tưởng "đẩy lại"). Lưu ý rằng bất kỳ ràng buộc nào không kích hoạt (quả banh không đụng đến bức tường) thì sẽ không có bất kỳ một lực tác động nào lên quả banh.

Ta hãy bỏ qua phần diễn giải chứng minh của hàm số Lagrange $L$ (Xem sách của Boyd và Vandenberghe về vấn đề này :cite:Boyd.Vandenberghe.2004). Lý luận bên trên có thể được mô tả thông qua bài toán tối ưu hóa điểm yên ngựa:

$$L(\mathbf{x},\alpha) = f(\mathbf{x}) + \sum_i \alpha_i c_i(\mathbf{x}) \text{ với } \alpha_i \geq 0.$$

Các biến $\alpha_i$ ở đây được gọi là nhân tử Lagrange (Lagrange Multipliers), chúng đảm bảo rằng các ràng buộc sẽ được tuân thủ đàng hoàng. Chúng được chọn vừa đủ lớn để đảm bảo rằng $c_i(\mathbf{x}) \leq 0$ với mọi $i$. Ví dụ, với mọi $\mathbf{x}$ mà $c_i(\mathbf{x}) < 0$ một cách tự nhiên, chúng ta rốt cuộc sẽ chọn $\alpha_i = 0$. Hơn nữa, đây là bài toán tối ưu hóa điểm yên ngựa, nơi ta muốn cực đại hóa $L$ theo $\alpha$ và đồng thời cực tiểu hóa nó theo $\mathbf{x}$. Có rất nhiều tài liệu giải thích về cách đưa đến hàm $L(\mathbf{x}, \alpha)$. Đối với mục đích của chúng ta, sẽ là đủ khi biết rằng điểm yên ngựa của $L$ là nơi bài toán tối ưu hóa bị ràng buộc ban đầu được giải quyết một cách tối ưu.

Lượng phạt

Có một cách để thỏa mãn, ít nhất là theo xấp xỉ, các bài toán tối ưu hóa bị ràng buộc là phỏng theo hàm Lagrange $L$. Thay vì thỏa mãn $c_i(\mathbf{x}) \leq 0$, chúng ta chỉ cần thêm $\alpha_i c_i(\mathbf{x})$ vào hàm mục tiêu $f(x)$. Điều này sẽ đảm bảo rằng các ràng buộc không bị vi phạm quá mức.

Thực tế, chúng ta đã dùng thủ thuật này khá thường xuyên. Hãy xét đến suy giảm trọng số trong :numref:sec_weight_decay. Ở đó chúng ta thêm $\frac{\lambda}{2} |\mathbf{w}|^2$ vào hàm mục tiêu để đảm bảo rằng giá trị $\mathbf{w}$ không trở nên quá lớn. Dưới góc nhìn tối ưu hóa có ràng buộc, ta có thể thấy nó sẽ đảm bảo $|\mathbf{w}|^2 - r^2 \leq 0$ với giá trị bán kính $r$ nào đó. Điều chỉnh giá trị của $\lambda$ cho phép chúng ta thay đổi độ lớn của $\mathbf{w}$.

Nhìn chung, thêm các lượng phạt là một cách tốt để đảm bảo việc thỏa mãn ràng buộc xấp xỉ. Trong thực tế, hóa ra phương pháp này ổn định hơn rất nhiều so với trường hợp thỏa mãn chuẩn xác. Hơn nữa, với các bài toán không lồi, những tính chất khiến phương án tiếp cận chuẩn xác trở nên rất thu hút trong trường hợp lồi (ví dụ như tính tối ưu) không còn đảm bảo nữa.

Các phép chiếu

Một chiến lược khác để thỏa mãn các ràng buộc là các phép chiếu. Chúng ta cũng đã gặp chúng trước đây, ví dụ như khi bàn về phương pháp gọt gradient ở :numref:sec_rnn_scratch. Ở phần đó chúng ta đã đảm bảo rằng gradient có độ dài ràng buộc bởi $c$ thông qua

$$\mathbf{g} \leftarrow \mathbf{g} \cdot \mathrm{min}(1, c/|\mathbf{g}|).$$

Hóa ra đây là một phép chiếu của $g$ lên khối cầu có bán kính $c$. Tổng quát hơn, một phép chiếu lên một tập (lồi) $X$ được định nghĩa là

$$\mathrm{Proj}X(\mathbf{x}) = \mathop{\mathrm{argmin}}{\mathbf{x}' \in X} |\mathbf{x} - \mathbf{x}'|_2.$$

Do đó đây là điểm gần nhất trong $X$ tới $\mathbf{x}$. Điều này nghe có vẻ hơi trừu tượng. :numref:fig_projections sẽ giải thích nó một cách rõ ràng hơn. Ở đó ta có hai tập lồi, một hình tròn và một hình thoi. Các điểm nằm bên trong tập (màu vàng) giữ nguyên không đổi. Các điểm nằm bên ngoài tập (màu đen) được ánh xạ tới điểm gần nhất bên trong tập (màu đỏ). Trong khi với các khối cầu $\ell_2$ hướng của phép chiếu được giữ nguyên không đổi, điều này có thể không đúng trong trường hợp tổng quát, như có thể thấy trong trường hợp của hình thoi.

🏷️fig_projections

Một trong những ứng dụng của các phép chiếu lồi là để tính toán các vector trọng số thưa. Trong trường hợp này chúng ta chiếu $\mathbf{w}$ lên khối cầu $\ell_1$ (phiên bản tổng quát của hình thoi ở hình minh họa phía trên).

Tóm tắt

Trong bối cảnh học sâu, mục đích chính của các hàm lồi là để thúc đẩy sự phát triển các thuật toán tối ưu hóa và giúp ta hiểu chúng một cách chi tiết. Phần tiếp theo chúng ta sẽ thấy cách mà hạ gradient và hạ gradient ngẫu nhiên có thể được suy ra từ đó.

• Giao của các tập lồi là tập lồi. Hợp của các tập lồi không bắt buộc phải là tập lồi.
• Kỳ vọng của hàm lồi lớn hơn hàm lồi của kỳ vọng (Bất đẳng thức Jensen).
• Hàm khả vi hai lần là hàm lồi khi và chỉ khi đạo hàm bậc hai của nó chỉ có các trị riêng không âm ở mọi nơi.
• Các ràng buộc lồi có thể được thêm vào hàm Lagrange. Trong thực tế, ta chỉ việc thêm chúng cùng với một mức phạt vào hàm mục tiêu.
• Các phép chiếu ánh xạ đến các điểm trong tập (lồi) nằm gần nhất với điểm gốc.

Bài tập

1. Giả sử chúng ta muốn xác minh tính lồi của tập hợp bằng cách vẽ mọi đoạn thẳng giữa các điểm bên trong tập hợp và kiểm tra liệu các đoạn thẳng có nằm trong tập hợp đó hay không.
   • Hãy chứng mình rằng ta chỉ cần kiểm tra các điểm ở biên là đủ.
   • Hãy chứng minh rằng ta chỉ cần kiểm tra các đỉnh của tập hợp là đủ.
2. Ký hiệu khối cầu có bán kính $r$ sử dụng chuẩn $p$ là $B_p[r] := {\mathbf{x} | \mathbf{x} \in \mathbb{R}^d \text{ và } |\mathbf{x}|_p \leq r}$. Hãy chứng minh rằng $B_p[r]$ là lồi với mọi $p \geq 1$.
3. Cho các hàm lồi $f$ và $g$ sao cho $\mathrm{max}(f, g)$ cũng là hàm lồi. Hãy chứng minh rằng $\mathrm{min}(f, g)$ không lồi.
4. Hãy chứng minh rằng hàm softmax được chuẩn hóa là hàm lồi. Cụ thể hơn, chứng minh tính lồi của $f(x) = \log \sum_i \exp(x_i)$.
5. Hãy chứng minh rằng các không gian con tuyến tính là các tập lồi. Ví dụ, $X = {\mathbf{x} | \mathbf{W} \mathbf{x} = \mathbf{b}}$.
6. Hãy chứng minh rằng trong trường hợp của các không gian con tuyến tính với $\mathbf{b} = 0$, phép chiếu $\mathrm{Proj}_X$ có thể được viết dưới dạng $\mathbf{M} \mathbf{x}$ với một ma trận $\mathbf{M}$ nào đó.
7. Hãy chỉ ra rằng với các hàm số khả vi hai lần $f$, ta có thể viết $f(x + \epsilon) = f(x) + \epsilon f'(x) + \frac{1}{2} \epsilon^2 f''(x + \xi)$ với một giá trị $\xi \in [0, \epsilon]$ nào đó.
8. Cho vector $\mathbf{w} \in \mathbb{R}^d$ với $|\mathbf{w}|_1 > 1$, hãy tính phép chiếu lên khối cầu đơn vị $\ell_1$.
   • Như một bước trung gian, hãy viết ra mục tiêu có lượng phạt $|\mathbf{w} - \mathbf{w}'|_2^2 + \lambda |\mathbf{w}'|_1$ và tính ra đáp án với $\lambda > 0$.
   • Bạn có thể tìm ra giá trị 'chính xác' của $\lambda$ mà không phải đoán mò quá nhiều lần không?
9. Cho tập lồi $X$ và hai vector $\mathbf{x}$, $\mathbf{y}$, hãy chứng minh rằng các phép chiếu không bao giờ làm tăng khoảng cách, ví dụ, $|\mathbf{x} - \mathbf{y}| \geq |\mathrm{Proj}_X(\mathbf{x}) - \mathrm{Proj}_X(\mathbf{y})|$.

Thảo luận

• Tiếng Anh - MXNet
• Tiếng Anh - Pytorch
• Tiếng Việt

Những người thực hiện

Bản dịch trong trang này được thực hiện bởi:

• Đoàn Võ Duy Thanh
• Phạm Hồng Vinh
• Lê Khắc Hồng Phúc
• Nguyễn Văn Quang
• Nguyễn Lê Quang Nhật
• Phạm Minh Đức
• Võ Tấn Phát