Chương 1 Một số phương pháp hướng giảm đa mục tiêu kinh điển Chương này tập trung phân tích chủ yếu hai thuật toán tối ưu đa mục tiêu kinh điển, đó là thuật toán hướng giảm dốc nhất và thuật toán Newton đa mục tiêu.1 Điều kiện cần cấp một Xét bài toán MOP sau đây: minn F (x) x∈R Trong đó, ta giả sử F ∶ Rn → Rm là một hàm véc tơ khả vi liên tục. Ta nói x là một điểm dừng Pareto đối với hàm véc tơ F nếu thỏa mãn điều kiện sau đây: ∀d ∈ Rn , ta có JF (x)d ≮ 0.,m Tương đương với điều kiện, nếu bao lồi của ∇fi (x) chứa điểm gốc, tức là, m ∃λ ∈ Δ sao cho ∑ λi ∇fi (xk ) = 0. , m} m i=1 là tập m− đơn hình. Lưu ý, khi F là hàm lồi trong không gian Rm thì x ∈ P ⇔ x là điểm dừng Pareto cấp 1 1.2 Tìm kiếm theo đường Với x bất kỳ không phải điểm dừng, tồn tại d ∈ Rn sao cho ∇fi (x)⊺ d < 0, ∀i = 1,.
Hơn nữa, ta có fi (x + td) − fi (x) lim = ∇fi (x)⊺ d < 0, ∀i t→0 t tức là, ∃t0 sao cho F (x + td) < F (x) đúng với mọi t ∈ (0, t0 ].3 Thuật toán hướng giảm dốc nhất đa mục tiêu(MSDM) Hướng giảm dốc nhất được tính theo công thức sau: 1 d(x) = argmin max ∇fi (x)⊺ d + ∣∣d∣∣2. Bài toán đối ngẫu của nó là d∈Rn i=1,. , m} là tập m− đơn hình. i=1 Lưu ý, khi m = 1, ta tìm được d(x) = −∇f1 (x).
4) x là điểm dừng khi và chỉ khi bao lồi của ∇fi (x) chứa điểm gốc, tức là, m ∃λ ∈ Δm sao cho ∑ λi ∇fi (xk ) = 0. i=1 Ta xét bài toán sau đây: 1 minn max ∇fi (x)⊺ d + ∥d∥2 .,m 2 8 Bài toán tương đương: 1 min β + ∥d∥2 β,d 2 v. Đây là bài toán cực tiểu hàm toàn phương với ràng buộc tuyến tính, có biến (β, d) ∈ Rn+1. Bài toán đối ngẫu có biến λ ∈ Rm.
Lưu ý m ≪ n, nên việc giải bài toán đối ngẫu hiệu quả hơn việc giải trực tiếp bài toán gốc. Thuật toán 1 MSDM 1: Chọn σ ∈ (0, 1) và x0 ∈ Rn. do 3: Tính dk bằng cách giải bài toán con có ràng buộc lồi 1 min β + ∣∣d∣∣2 β,d 2 v. 4: Nếu θ(xk ) = 0 thì dừng.
5: Chọn cỡ bước αk là lớn nhất trong α ∈ {1/2j ∶ j ∈ N} sao cho F (xk + αdk ) ≤ F (xk ) + σαJF (xk )dk. 6: Cập nhật xk+1 = xk + αk dk 7: end for 1.4 Sự hội tụ và độ phức tạp của thuật toán MSDM Định lý 1.3 (Các gradient liên tục Lipschitz) Gọi {xk } là một dãy được sinh ra bởi thuật toán MSDM. Mọi điểm tụ của dãy, nếu có, là một điểm dừng Pareto.4 (F không lồi trên Rm ) Giả sử có ít nhất một trong các hàm fi , i = 1,. , m, bị chặn dưới, dãy {xk } được sinh ra bởi thuật toán MSDM thỏa mãn √ min ∣∣di ∣∣ ≤ O(1/ k).
0≤i≤k−1 9 Tương tự, độ đo tính không dừng θ(xk ) của điểm xk thỏa mãn √ ∣θ(xk )∣ ≤ O(1/ k). Giả sử dãy {xk } hội tụ đến điểm x∗ tương ứng với các trọng số λ∗. Khi đó ta có hai phát biểu sau đây: 1) F là lồi chặt trên Rm : • Tốc độ tuyến tính theo số bước lặp: ∣∣xk − x∗ ∣∣ ≤ O(ck ), c ∈ (0, 1). • Tốc độ tuyến tính theo gap tối ưu sử dụng hàm tổng có trọng số: m m ∑ λi fi (xk ) − ∑ λ∗i fi (x∗ ) ≤ O(ck ).
∗ i=1 i=1 2) F là lồi trên Rm : • O(1/k) tốc độ hội tụ dưới tuyến tính cho gap tối ưu được định nghĩa bởi một dạng yếu hơn của hàm tổng có trọng số m m ∗ ∑ λ̄i fi (xk ) − ∑ λ̄k−1 k−1 i fi (x ) ≤ O(1/k).5 Thuật toán Newton đa mục tiêu Giả sử F là lồi chặt trên Rm và khả vi liên tục hai lần.,m 2 Ở đây, ta tính gần đúng fi (x + s) − fi (x) dựa trên mô hình xấp xỉ bậc hai cục bộ. Bài toán con có thể được đưa về bài toán ràng buộc bậc hai lồi: min t v.5 (Hướng Newton, [5]) m −1 m s(x) = − [∑ λ(x)i ∇ fi (x)] ∑ λ(x)i ∇fi (x) 2 i=1 i=1 trong đó λ(x) là hệ số Lagrange tương ứng với bài toán (1. Thuật toán Newton đa mục tiêu được mô tả chi tiết trong thuật toán 2. 11 Thuật toán 2 MNM 1: Chọn σ ∈ (0, 1) và x0 ∈ Rn.
do 3: Tính sk bằng cách giải bài toán con có ràng buộc lồi min t v. , m (t, s) ∈ R × Rn 4: Nếu tk = 0 thì dừng. 5: Chọn cỡ bước αk là lớn nhất trong α ∈ {1/2j ∶ j ∈ N} sao cho F (xk + αsk ) ≤ F (xk ) + σαJF (xk )sk. 6: Cập nhật xk+1 = xk + αk sk 7: end for 1.6 Tốc độ hội tụ của thuật toán Newton đa mục tiêu Định lý 1.7 (Tốc độ hội tụ bậc hai cục bộ [5]) Giả sử các ma trận Hesse ∇2 fi , ∀i là xác định dương đều và liên tục Lipschitz.
Gọi x0 là điểm đủ gần với một điểm dừng Pareto x∗. Dãy {xk } được sinh ra bởi thuật toán (2) MNM thỏa mãn 1. {xk } hội tụ đến điểm x∗ với tốc độ q−bậc hai. ∣∣s(xk )∣∣ hội tụ đến 0 với tốc độ r−trên tuyến tính.
12 Chương 2 Phương pháp hướng giảm chống lại xung đột cho học đa mục tiêu 2.1 Bài toán học đa mục tiêu Bài toán học đa mục tiêu (MOL) được định nghĩa như sau: ⊺ minw (w) = min{(1 (w),. , p (w)) ∣ w ∈ Rn }, (MOL) trong đó i (w) = Ex (i (w, x)) với i ∈ [p], và x là điểm dữ liệu trong tập dữ liệu. Ở đây ta ký hiệu [p] = {1, 2,. Mục đích của ta là tìm ra các điểm mà tại đó ta không thể cải thiện đồng thời tất cả các hàm mục tiêu.
Điều này dẫn đến khái niệm tối ưu Pareto. Xét hai điểm w, w′ ∈ Rn. Ta nói rằng điểm w trội so với điểm w′ nếu i (w) ≤ i (w′ ) với mọi i ∈ [p] và (w) ≠ (w′ ).2 (Tối ưu Pareto) Nếu một điểm w′ ∈ Rn không bị trội bởi điểm bất kỳ điểm w ∈ Rn nào, ta nói điểm w′ tối ưu Pareto. Tập các điểm tối ưu Pareto được gọi là tập Pareto.
Tập các giá trị hàm chi phí (w∗ ) đối với tất cả các điểm tối ưu Pareto w∗ được gọi là mặt Pareto. Điểm w được gọi là điểm dừng Pareto nếu tồn tại λ ∈ Λ sao cho ∑pi=1 λi ∇i (w) = 0. Tương tự như trường hợp một mục tiêu, điều kiện dừng Pareto là điều kiện cần cho tối ưu Pareto.2 Xung đột gradient Ta có thể giải bài toán MOL bằng cách tối ưu hàm mục tiêu có trọng số sau đây: p ∗ w = arg min ∑ λi i (w).1) w i Các trọng số λi được gán trước hoặc được tính toán trong suốt quá trình tối ưu. Phương pháp phổ biến nhất là gán cho mỗi mục tiêu các trọng số bằng nhau, khi đó ta có hàm chi phí trung bình được định nghĩa bởi 0 (w) = 1 p p ∑i=1 i (w).
Mặc dù vậy, việc tối ưu đa mục tiêu rất phức tạp và xung đột gradient là nguyên nhân phổ biến dẫn đến điều này. Ký hiệu gi = ∇i (w) là gradient của hàm chi phí i (w) theo tham số w đối với mục tiêu i. Để điều chỉnh w một lượng nhỏ theo hướng âm của gi , ta sử dụng công thức: w ← w − αgi , trong đó α là cỡ bước hay tỉ lệ học được chọn đủ nhỏ. Ảnh hưởng của sự thay đổi nhỏ này đến mục tiêu j được định lượng bởi: Δj = j (w − αgi ) − j (w) = −α⟨gi , gj ⟩ + O(α).2) Ta có được phương trình thứ hai bằng cách sử dụng xấp xỉ Taylor bậc nhất.
Tương tự, khi tham số mô hình w được cập nhật theo hướng ngược với gradient của mục tiêu j (cụ thể là −gj ) bởi một cỡ bước tương đối nhỏ α, thì sự ảnh hưởng đến mục tiêu i được đo bởi công thức: Δi = −α⟨gi , gj ⟩ + O(α). 14 Điều đáng chú ý là nếu ⟨gi , gj ⟩ < 0, thì cập nhật cho mục tiêu i có ảnh hưởng tiêu cực đến mục tiêu j vì nó làm tăng giá trị hàm chi phí của mục tiêu j và ngược lại. Định nghĩa xung đột gradient được sử dụng trong luận văn này dựa trên công trình nghiên cứu [21]. Định nghĩa này được trình bày như sau.4 (Xung đột gradient) Sự xảy ra xung đột gradient giữa gi và gj (i ≠ j) được định nghĩa bởi điều kiện cos φij < 0, trong đó φij là góc giữa hai gradient.
Như được mô tả trong công trình nghiên cứu [21], xung đột gradient có thể gây ra khó khăn lớn cho việc tối ưu hàm mục tiêu có trọng số được định nghĩa trong công thức (2. Khi triển khai thuật toán hướng giảm gradient sử dụng gradient trung bình, được biểu diễn bởi 1 p g0 = ∇0 (w) = ∑ gi , p i=1 thì hiệu năng của từng mục tiêu có thể bị ảnh hưởng tiêu cực, đặc biệt là khi có sự khác biệt đáng kể về mặt độ lớn gữa các gradient.3 Một số nghiên cứu liên quan Một số phương pháp đã được phát triển để tìm ra hướng gradient tốt hơn. Trong hình này, véc tơ cập nhật g (màu đỏ) là tổng hợp của hai gradient thành phần g1 và g2. Mỗi gradient thành phần tương ứng với mỗi mục tiêu.
MGDA [15] cực tiểu hóa chuẩn của tổng có trọng số của các gradient của các tác vụ để tìm ra trọng số của hàm chi phí đa tác vụ, trong khi GradNorm [2] điều chỉnh động độ lớn của gradient để học các trọng số của các tác vụ. PCGrad [21] giảm tác động của xung đột gradient bằng cách chiếu mỗi gradient lên mặt phẳng pháp tuyến của một gradient khác, sau đó tính trung bình của các gradient được chiếu lên này để cập nhật gradient. 15 g2 g2 g2 g2 g1 g1 g1 g1 GD MGDA PCGrad CAGrad & AdaCAGrad maxg mini gi⊺ g g = (g1⊥2 + g2⊥1 ) /2 maxg mini gi⊺ g g = (g1 + g2 ) /2 g⊺ g v.k ∥g ∥ ≤ 1 trong đó gi⊥j = gi − ∥igj ∥j gj v.