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

Learn & Enjoy …

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

Posted by Trần Quốc Long 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\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:

  1. 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

  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):

Leo đồi theo hướng đạo hàm

Nhận xét:

  1. 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…).
  2. 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.
  3. 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).
  4. 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)\|.
  5. 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.
  6. 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 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ó:

  1. 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

  2. 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:

  1. Đặ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^{**}.
  2. 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.
  3. 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\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^*\displaystyle \delta>0 sao cho khi \displaystyle x_t\in U thì

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

\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:

  1. 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\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.
  2. 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\displaystyle \phi'(0)<0

Gửi phản hồi

Mời bạn điền thông tin vào ô dưới đây hoặc kích vào một biểu tượng để đăng nhập:

WordPress.com Logo

Bạn đang bình luận bằng tài khoản WordPress.com Log Out / Thay đổi )

Twitter picture

Bạn đang bình luận bằng tài khoản Twitter Log Out / Thay đổi )

Facebook photo

Bạn đang bình luận bằng tài khoản Facebook Log Out / Thay đổi )

Google+ photo

Bạn đang bình luận bằng tài khoản Google+ Log Out / Thay đổi )

Connecting to %s

 
%d bloggers like this: