Tối ưu không ràng buộc (3) – Xuống đồi theo hướng đạo hàm (gradient descent) « CS Study Fun

Tháng Tư 2008
T2	T3	T4	T5	T6	T7	CN
« Tháng 3		Tháng 7 »
	1	2	3	4	5	6
7	8	9	10	11	12	13
14	15	16	17	18	19	20
21	22	23	24	25	26	27
28	29	30

Tối ưu không ràng buộc (3) – Xuống đồi theo hướng đạo hàm (gradient descent)

Đăng bởi tqlong on Tháng Tư 23, 2008

Trong bài này, ta xem xét một phương pháp tối ưu hóa hay được sử dụng nhất, đó là phương pháp xuống đồi theo hướng véctơ đạo hàm (gradient descent). Đúng như tên gọi của nó, tại mỗi bước lặp, hướng được lựa chọn để giảm giá trị hàm mục tiêu là $\displaystyle -\nabla f(x)$ . Như vậy, nghiệm hiện tại được cập nhật tại bước thứ $\displaystyle t$ bằng luật sau:

$\displaystyle x_{t+1} = x_t - \gamma_t \nabla f(x_t)$

Các phương pháp xuống đồi khác nhau ở việc chọn bước nhảy $\displaystyle \gamma_t$ . Cụ thể, ta sẽ tìm hiểu 2 phương pháp:

Sử dụng bước nhảy Armijo (Armijo Gradient Descent – ArD): Cho $\displaystyle 0<\epsilon < 1,\nu>1$ tìm $\displaystyle \gamma_t$ sao cho:
$\displaystyle f(x_t-\gamma_t \nabla f(x_t)) \leq f(x_t)-\epsilon \gamma_t \|\nabla f(x_t)\|^2$
$\displaystyle f(x_t-\nu\gamma_t \nabla f(x_t)) > f(x_t)-\epsilon \nu\gamma_t \|\nabla f(x_t)\|^2$
Sử dụng bước nhảy tốt nhất có thể được bằng tìm kiếm chính xác (Steepest Descent – StD): tìm $\displaystyle \gamma_t$ sao cho:
$\displaystyle \gamma_t=\arg\min_{\gamma>0}f(x_t-\gamma \nabla f(x_t))$ .

Ví dụ: Hình sau (nguồn Wikipedia) là quá trình cực đại hóa hàm số theo hướng đạo hàm (thuật toán StD):

Nhận xét:

Trên thực tế, ít khi ta sử dụng phương pháp tìm kiếm chính xác (trừ trường hợp $\displaystyle \phi(\gamma)=f(x-\gamma\nabla f(x))$ là hàm có dạng đơn giản như hàm tuyến tính, hàm bậc 2, dạng nón ngửa, v.v…).
Trong cài đặt, nhiều khi người ta sử dụng bước nhảy cố định, $\displaystyle \gamma_t = \mathrm{const},\forall t$ để giảm khối lượng tính toán. Tuy nhiên, các thuật toán xuống đồi với bước nhảy cố định không có đảm bảo hội tụ đến các điểm KKT.
Các phương pháp sử dụng đạo hàm không làm thay đổi nghiệm hiện tại khi $\displaystyle \nabla f(x_t)=0$ . Như vậy, các phương pháp sử dụng đạo hàm cho ta các nghiệm thỏa mãn điều kiện cần Karush-Kuhn-Turker (lưu ý là điều kiện KKT chỉ là điều kiện đủ khi hàm mục tiêu là hàm lồi).
Cũng vì vậy, một thước đo sai số hay được sử dụng trong các phương pháp dùng đạo hàm là $\displaystyle \epsilon(t)=\|\nabla f(x_t)\|$ .
Phương pháp tối ưu sử dụng đạo hàm được ứng dụng rất rộng rãi. Khi áp dụng phương pháp này, cần tính toán được đạo hàm $\displaystyle \nabla f(x)$ . Lưu ý là số chiều $\displaystyle n$ có thể rất lớn hoặc cấu trúc của $\displaystyle f(x)$ rất phức tạp nên việc tính toán đạo hàm không phải lúc nào cũng dễ dàng. Một ví dụ là mạng nơron (neural networks) trong trí tuệ nhân tạo. Trước khi có thuật toán lan truyền ngược sai số (error back-propagation) (năm 1986), do không thể tính toán đạo hàm của hàm sai số một cách hiệu quả, người ta đã cho rằng mạng nơron là tuy là mô hình học máy mạnh (có thể xấp xỉ bất cứ hàm “trơn” nào) nhưng lại không thể huấn luyện được.
Qua hình trên, ta thấy thuật toán StD luôn cho quỹ đạo dích dắc với
$\displaystyle \nabla f(x_t)^T\nabla f(x_{t+1}) = 0$

tức là đạo hàm tại các nghiệm kế tiếp nhau vuông góc với nhau. Tại sao như vậy? Lý do đơn giản như sau, nếu

$\displaystyle \nabla f(x_t)^T\nabla f(x_{t+1}) \neq 0$

thì theo định lý về hướng làm giảm hàm mục tiêu, $\displaystyle \nabla f(x_t)$ hoặc $\displaystyle -\nabla f(x_t)$ là hướng làm giảm hàm mục tiêu tại $\displaystyle x_{t+1}$ , mâu thuẫn với cách chọn $\displaystyle \gamma_t$ trong thuật toán StD:

$\displaystyle \gamma_t=\arg\min_{\gamma>0}f(x_t-\gamma \nabla f(x_t))$ $\displaystyle x_{t+1}=x_t-\gamma_t \nabla f(x_t)$

Định lý (tính hội tụ của phương pháp sử dụng đạo hàm): Giả sử $\displaystyle \{x_t\}_{t=0}^\infty$ là quỹ đạo của thuật toán ArD (hoặc StD) và hàm $\displaystyle f(x)$ khả vi liên tục và bị chặn dưới, ta có:

Nếu dãy $\displaystyle \{x_t\}_{t=0}^\infty$ bị chặn thì tại các điểm giới hạn $\displaystyle x^*$ của dãy này ta có
$\displaystyle \nabla f(x^*)=0$
Nếu $\displaystyle x_0$ là nghiệm ban đầu và tập $\displaystyle \{x:f(x)\leq f(x_0)\}$ bị chặn thì tại các điểm giới hạn $\displaystyle x^*$ của quỹ đạo ta có
$\displaystyle \nabla f(x^*)=0$

Nhận xét:

Đặt $\displaystyle X^{**}=\{x:\nabla f(x)=0\}$ . Định lý trên chứng tỏ, nếu $\displaystyle x^*$ là điểm giới hạn của $\displaystyle \{x_t\}_{t=1}^\infty$ thì $\displaystyle x\in X^{**}$ .
Do quỹ đạo bị chặn nên luôn tồn tại ít nhất một điểm giới hạn.
Mệnh đề (2) là hệ quả của mệnh đề (1) vì quỹ đạo $\displaystyle \{x_t\}_{t=0}^\infty$ nằm trong tập $\displaystyle \{x:f(x)\leq f(x_0)\}$ do tại các bước, thuật toán ArD hay StD đều làm giảm giá trị hàm mục tiêu nên $\displaystyle f(x_t)<f(x_0),\forall t$ .

Chứng minh: Chứng minh của định lý trên sử dụng bổ đề sau

Bổ đề: Nếu $\displaystyle \nabla f(x)\neq 0$ thì tồn tại lân cận $\displaystyle U$ của $\displaystyle x$ và $\displaystyle \delta>0$ sao cho nếu $\displaystyle x_t\in U$ thì với thuật toán ArD (hoặc StD) ta có

$\displaystyle f(x_{t+1}) \leq f(x_t) - \delta$

trong đó $\displaystyle \delta>0$ không phụ thuộc $\displaystyle x_t$ mà chỉ phụ thuộc vào $\displaystyle x$ . Nghĩa là nếu $\displaystyle x_t\in U$ , sau mỗi bước lặp của thuật toán ArD, hàm mục tiêu giảm ít nhất là $\displaystyle \delta$ .

Chứng minh định lý: Giả sử điểm giới hạn $\displaystyle x^*$ của quỹ đạo có

$\displaystyle \nabla f(x^*)\neq 0$

Theo bổ đề trên, tồn tại lân cận $\displaystyle U$ của $\displaystyle x^*$ và $\displaystyle \delta>0$ sao cho khi $\displaystyle x_t\in U$ thì

$\displaystyle f(x_{t+1}) \leq f(x_t) - \delta$

Vì $\displaystyle x^*$ là điểm giới hạn của dãy $\displaystyle \{x_t\}_{t=0}^\infty$ , số bước lặp có $\displaystyle x_t\in U$ là vô hạn (tức là số lần giảm hàm mục tiêu ít nhất $\displaystyle \delta$ là vô hạn), suy ra

$\displaystyle f(x_t)\rightarrow -\infty$ khi $\displaystyle t\rightarrow \infty$

hay hàm $\displaystyle f(x)$ không bị chặn dưới, mâu thuẫn. Vậy $\displaystyle \nabla f(x^*)= 0$ .

Chứng minh bổ đề: Ta chỉ cần chứng minh với thuật toán ArD (tham số $\displaystyle 0<\epsilon<1,\nu>1$ ) vì tại mỗi bước lặp, nếu xuất phát ở cùng một điểm $\displaystyle x_t$ , thuật toán StD luôn giảm hàm mục tiêu nhiều hơn thuật toán ArD.

Xét $\displaystyle p,P>0$ sao cho $\displaystyle p<\|\nabla f(x)\|<P$ , do hàm $\displaystyle f(x)$ khả vi liên tục nên tồn tại bán kính $\displaystyle R>0$ sao cho

$\displaystyle \forall y\in \mathrm{Ball}(x,R): p\leq\|\nabla f(y)\|\leq P$

Đặt $\displaystyle \zeta=\frac{(1-\epsilon)p^2}{P}>0$ , do hàm $\displaystyle f(x)$ khả vi liên tục nên tồn tại bán kính $\displaystyle 0<r<R$ sao cho

$\displaystyle \forall y,z\in \mathrm{Ball}(x,r): \|\nabla f(y)-\nabla f(z)\|\leq \zeta$

Đặt $\displaystyle U=\mathrm{Ball}(x,\frac{r}{2})$

Ta sẽ chứng minh bước nhảy Armijo $\displaystyle \gamma_t$ tại mỗi điểm $\displaystyle x_t\in U$ nhỏ nhất là bằng

$\displaystyle \gamma^*=\frac{r}{2\nu P}\leq \gamma_t$

Thật vậy, giả sử ngược lại, $\displaystyle \gamma_t < \gamma^*$ và đặt

$\displaystyle \phi(\gamma)=f(x_t-\gamma\nabla f(x_t))$

Ta có

$\displaystyle \phi'(\gamma)=-\nabla f(x_t-\gamma\nabla f(x_t))^T\nabla f(x_t)$

$\displaystyle \phi'(0)=-\|\nabla f(x_t)\|^2\leq -p^2$

Do $\displaystyle \gamma_t < \gamma^*$ nên

$\displaystyle \|\nu\gamma_t\nabla f(x_t)\|\leq \nu\gamma^* P=\frac{r}{2}$

Vì thế, do $\displaystyle x_t\in U=\mathrm{Ball}(x,\frac{r}{2})$ nên đoạn thẳng $\displaystyle [x_t, x_t-\nu\gamma_t\nabla f(x_t)] \subset \mathrm{Ball}(x,r)$ . Suy ra

$\displaystyle \phi(\nu\gamma_t) -\phi(0) = \phi'(\gamma)\nu\gamma_t$

trong đó $\displaystyle \gamma\in[0,\nu\gamma_t]$ , ta có

$\displaystyle \phi'(\gamma)-\phi'(0)=(\nabla f(x_t)-\nabla f(x_t-\gamma\nabla f(x_t)))^T\nabla f(x)$

Suy ra

$\displaystyle \phi'(\gamma)-\phi'(0)\leq \|\nabla f(x_t-\gamma\nabla f(x_t))-\nabla f(x_t)\| \|\nabla f(x)\|$ $\displaystyle \leq \zeta P=(1-\epsilon) p^2$

Vậy

$\displaystyle \phi(\nu\gamma_t) -\phi(0) \leq \nu\gamma_t (\phi'(0) + (1-\epsilon)p^2)$

Hơn nữa, do $\displaystyle \gamma_t$ là bước nhảy Armijo (bước nhảy tốt nhất) nên

$\displaystyle \phi(\nu\gamma_t)-\phi(0)>\epsilon\nu\gamma_t\phi'(0)$

Tức là

$\displaystyle \nu\gamma_t (\phi'(0) + (1-\epsilon)p^2) > \epsilon\nu\gamma_t\phi'(0)$

$\displaystyle (1-\epsilon)\nu\gamma_t p^2 > -(1-\epsilon)\nu\gamma_t \phi'(0)\geq (1-\epsilon)\nu\gamma_t p^2$

Suy ra mâu thuẫn, vậy $\displaystyle \gamma_t\geq \gamma^*$ . Ngoài ra. $\displaystyle \gamma_t$ là bước nhảy thích hợp nên

$\displaystyle \phi(\gamma_t)\leq \phi(0) + \epsilon\gamma_t\phi'(0)\leq \phi(0)-\epsilon\gamma^*p^2$

Vậy, chọn $\displaystyle \delta = \epsilon\gamma^*p^2$ ta có điều phải chứng minh.

Nhận xét:

Kỹ thuật chứng minh định lý trên là kỹ thuật chung để chứng minh quỹ đạo của thuật toán tối ưu có các điểm giới hạn thỏa mãn $\displaystyle \nabla f(x^*)=0$ . Điểm mấu chốt là phải chứng minh được khi $\displaystyle \nabla f(x)\neq 0$ thì sẽ có một lân cận $\displaystyle U$ của $\displaystyle x$ và $\displaystyle \delta>0$ sao cho thuật toán tối ưu xuất phát từ một điểm $\displaystyle x_t\in U$ thì sẽ giảm giá trị hàm mục tiêu ít nhất là $\displaystyle \delta$ .
Cách chứng minh bổ đề trên khá rắc rối, điểm mấu chốt là ta giữ nguyên $\displaystyle p,P$ rồi điều chỉnh $\displaystyle \zeta$ (và kèm theo đó là $\displaystyle r$ ) để dẫn đến mâu thuẫn. Mâu thuẫn chắc chắn phải xảy ra vì
$\displaystyle \epsilon\nu\gamma_t\phi'(0)<\phi(\nu\gamma_t)-\phi(0)\leq \nu\gamma_t(\phi'(0)+\zeta P)$

trong khi đó $\displaystyle \epsilon\nu\gamma_t\phi'(0) \geq \nu\gamma_t\phi'(0)$ do $\displaystyle 0<\epsilon<1$ và $\displaystyle \phi'(0)<0$

Bài viết này được đăng vào Tháng Tư 23, 2008 lúc 6:57 chiều và tập tin được lưu ở Quy hoạch phi tuyến. Tagged: armijo, gradient descent, steepest descent, tìm kiếm chính xác, xuống đồi. Bạn có thể theo dõi các phản hồi của bài viết này thông qua RSS 2.0 dòng thông tin. Bạn có thể Để lại lời nhắn, hoặc trackback từ trang của bạn.

Để lại hồi âm

« Tối ưu không ràng buộc (2) – Tìm kiếm trên đường thẳng (line search)

Tối ưu không ràng buộc (4) – Tốc độ hội tụ của phương pháp đạo hàm »

	Khuyen Nguyen trong bài Phân lớp bằng siêu phẳng (1) …
	tqlong trong bài Phân lớp bằng siêu phẳng (1) …
	Khuyen Nguyen trong bài Phân lớp bằng siêu phẳng (1) …
	tqlong trong bài Bất đẳng thức xác suất (1) …
	H.T.D. trong bài Bất đẳng thức xác suất (1) …

CS Study Fun – Khoa học máy tính

Learn & Enjoy …

Phân loại

Lưu trữ

Thống kê

Bài gần đây

Lời bình gần đây

Trang

Blogroll

Quản trị

Lịch

Theo dõi

Blog D.Q. Huy

Các phương pháp điểm trong

Xem nhiều nhất

Từ khóa

Tối ưu không ràng buộc (3) – Xuống đồi theo hướng đạo hàm (gradient descent)

Để lại hồi âm