Nhãn

This is default featured slide 1 title

Go to Blogger edit html and find these sentences.Now replace these sentences with your own descriptions.This theme is Bloggerized by Lasantha Bandara - Premiumbloggertemplates.com.

This is default featured slide 2 title

Go to Blogger edit html and find these sentences.Now replace these sentences with your own descriptions.This theme is Bloggerized by Lasantha Bandara - Premiumbloggertemplates.com.

This is default featured slide 3 title

Go to Blogger edit html and find these sentences.Now replace these sentences with your own descriptions.This theme is Bloggerized by Lasantha Bandara - Premiumbloggertemplates.com.

This is default featured slide 4 title

Go to Blogger edit html and find these sentences.Now replace these sentences with your own descriptions.This theme is Bloggerized by Lasantha Bandara - Premiumbloggertemplates.com.

This is default featured slide 5 title

Go to Blogger edit html and find these sentences.Now replace these sentences with your own descriptions.This theme is Bloggerized by Lasantha Bandara - Premiumbloggertemplates.com.

Thứ Tư, 12 tháng 10, 2016

Submodular Function (Phần 1)

By  tháng 10 12, 2016  No comments
Xin phép được đăng lại bài của cô Thái Trà My để mọi người tham khảo ak!
Submodular function được định nghĩa như sau:
Định nghĩa 1: Cho một set function f trên mọi tập con của tập E. Hàm f được gọi là submodular function khi với bất kỳ hai tập con A, B \subseteq E, ta có:
f(A) + f(B) \ge f(A \cup B) + f(A \cap B)
Ví dụ: f(A) = |A| là một submodular function.
Định nghĩa trên còn tương đương với định lý sau:
Định lý 1: Xét một set function f. Nếu f là submodular function thì với mọi A \subseteq B \subseteq E và x \in E \setminus B, ta có:
f(A \cup {x}) - f(A) \ge f(B \cup {x}) - f(B)
Định lý 1 ngụ ý rằng thêm một phần tử vào tập A sẽ có lợi hơn thêm nó vào mộ tập lớn hơnA. Nghĩa là, càng sớm càng tốt.
Tại sao chúng ta lại quan tâm đến submodular function? Bởi chúng đóng một vai trò rất quan trọng trong toán tối ưu và thuật toán xấp xỉ (approximation algorithms)
Có rất nhiều phương pháp trong thuật toán xấp xỉ, từ thuật toán tổ hợp (combinatorics) tới quy hoạch tuyến tính (linear programming) và semi-definite programming. Trong đó, thuật toán tham lam (greedy algorithms) là một trong những thuật toán phổ biến nhất và tính ứng dụng rất cao bởi độ đơn giản của nó cùng với độ phức tạp thấp về thời gian.
Tuy nhiên, phân tích tỉ lệ xấp xỉ (approximation ratio) của thuật toán tham lam vô cùng tricky và thú vị. Nếu hàm tham lam (greedy function) của một thuật toán tham lam là submodular function thì việc phân tích tỉ lệ xấp xỉ trở nên đơn giản hơn nhiều. Chúng ta hãy xét một vài ví dụ sau đây.
Set Cover: Cho trước một tập vũ trụ U có n phần tử và một họ \mathcal{C} tập con của U. Tìm họ con nhỏ nhất \mathcal{C}' \subseteq \mathcal{C} phủ tất cả các phần tử của U.
Define f(\mathcal{C}') = |\bigcup_{S \in \mathcal{C}'}S| (i.e. tổng số phần tử trong \mathcal{C}'). Xét thuật toán tham lam sau:
Algorithm 1:
\mathcal{C}' \leftarrow \emptyset
while |U| > f(\mathcal{C}') do
\hspace{10pt} choose S \in \mathcal{C} to maximize f(\mathcal{C}' \cup S)
\hspace{10pt} \mathcal{C}' \leftarrow \mathcal{C}' \cup S
return \mathcal{C}'
Trong Algorithm 1, cho mỗi iteration, chúng ta chọn một tập con sao cho phủ được nhiều phần tử chưa được phủ tại thời điểm đó. Chúng ta sẽ chứng minh rằng Algorithm 1 có tỉ lệ xấp xỉ là (1 + \ln n) với n = |U|. (Chú ý rằng với bài toán minimization, thì tỉ lệ xấp xỉ \rho được định nghĩa như sau: \rho = opt/sol trong đó opt là giá trị tối ưu và sol là giá trị lời giải.)
Trước tiên, chúng ta chứng minh hai bổ đề sau:
Bổ đề 1: Hàm f là submodular function và monotone increasing.
Chứng minh: Bài tâp.
\Box
Bổ đề 2: Giả sử  S_1, S_2, \dots, S_k được chọn bởi Algorithm 1. Ký hiệu \mathcal{C}_i = \{ S_1, S_2, \dots, S_i\} và opt là giá trị tối ưu (optimal value), ta có:
f(\mathcal{C}_{i+1}) \ge f(\mathcal{C}_i) + (n - f(\mathcal{C}_i))/opt
Chứng minh: Ký hiệu \Delta_Xf(A) = f(A \cup X) - f(A). Gọi \mathcal{C}^* = \{X_1, X_2, \dots, X_{opt}\} là lời giải tối ưu (optimal solution). Và ký hiệu \mathcal{C}_j^* = \{X_1, X_2, \dots, X_j\}. Tại mỗi iteration i, theo Algorithm 1, ta có:
\Delta_{S_{i+1}} f(\mathcal{C}_i) \ge \Delta_{X_{j+1}} f(\mathcal{C}_i) \forall j, 0 \le j \le opt - 1
Suy ra,
\Delta_{S_{i+1}}f(\mathcal{C}_i) \ge (\sum_{0 \le j \le opt -1} \Delta_{X{j+1}} f(\mathcal{C}_i))/opt
\ge (\sum_{0 \le j \le opt -1} \Delta_{X{j+1}} f(\mathcal{C}_i \cup \mathcal{C}_j^*))/opt (theo Bổ đề 1)
Do đó, ta có:
\Delta_{S_{i+1}}f(\mathcal{C}_i) \ge (f(\mathcal{C}_i \cup \mathcal{C}^*) - f(\mathcal{C}_i))/opt = (n - f(\mathcal{C}_i))/opt
\Box
Từ bổ đề 2, chúng ta dễ dàng chứng minh Định lý sau:
Định lý 2: Algorithm 1 có tỉ lệ xấp xỉ là (1 + \ln n)
Chứng minh: Theo Bổ đề 2, ta có:
n - f(\mathcal{C}_{i+1})  \le (n - f(\mathcal{C}_i))(1 -1/opt) \le (n - f(\mathcal{C}_{i-1}))(1 -1/opt)^2
\le \dots \le n(1-1/opt)^{i+1}
Chọn i là số nguyên dương lớn nhất thỏa mãn: opt \le n - f(\mathcal{C}_i).  Ta có:
k - i \le opt, nên opt \le n(1 - 1/opt)^i \le n e^{-i/opt} (vì 1 + x \le e^x)
Do đó, i \le opt \ln(n/opt). Suy ra k \le opt + 1 \le opt(1 + \ln(n/opt))
\Box
Bây giờ, giả sử mỗi tập con của U có một khối lượng và ta muốn tìm họ con với khối lượng nhỏ nhất.  Ta cần phải làm gì?
Weighted Set Cover: Cho trước một tập vũ trụ U có n phần tử , một họ \mathcal{C} tập con của U với weight function w: \mathcal{C} \rightarrow \mathbb{Q}^+. Tìm họ con có khối lượng nhỏ nhất \mathcal{C}' \subseteq \mathcal{C}phủ tất cả các phần tử của U.
Sử dụng hàm f ở trên, thay đổi Algorithm 1 một tí, ta có:
Algorithm 2:
\mathcal{C}' \leftarrow \emptyset
while |U| > f(\mathcal{C}') do
\hspace{10pt} choose S \in \mathcal{C} to maximize \Delta_S f(\mathcal{C}')/w(S)
\hspace{10pt} \mathcal{C}' \leftarrow \mathcal{C}' \cup S
return \mathcal{C}'
Định lý 3: Algorithm 2 có tỉ lệ xấp xỉ là (1 + \ln n)
Chứng minh: Bài tập.
\Box
Tổng quát hóa, ta có:
Bài toán tổng quát : Xét một hàm monotone increasing và submodular function f trên tất cả tập con của tập E và một cost function c: E \rightarrow \mathbb{Q}^+. Định nghĩa \Omega(f) = \{A \ | \ \forall x \in E, \Delta_{\{x\}}f(A) = 0\}. Xét bài toán sau:
minimize c(A) = \sum_{x \in A} c(x) sao cho A \in \Omega(f)
Lời giải: Để giải bài toán tổng quát trên, ta có thuật toán tham lam như sau:
Algorithm 3:
A \leftarrow \emptyset
while  tồn tại x \in E sao cho \Delta_{\{x\}} f(A) > 0 do
\hspace{10pt} choose x \in E to maximize \Delta_{\{x\}} f(A)/c(x)
\hspace{10pt} A \leftarrow A \cup \{x\}
return A
Định lý 4: Nếu f(\emptyset) = 0, f là hàm số dương (integer function), monotone increasing, submodular function, và c(x) \ge 0, \forall x \in E, Algorithm 3 sẽ có tỉ lệ xấp xỉ là (1 + \ln \gamma) với \gamma = \max_{x \in E} f(\{x\}).
Chứng minh: Giả sử x_1, x_2, \dots, x_k là các phần tử được Algorithm 3 chọn theo thứ tự như vậy. Ký
hiệu A_i = \{x_1, \dots, x_i\} và r_i = \Delta_{x_i}f(A_{i - 1}).
Gọi A^* = \{y_1, \dots, y_h\} là lời giải tối ưu. Với mỗi y_e \in A^*, đặt z_{ei} = \Delta_{ye}f(A_{i-1}). Cho đơn giản, ký hiệu c_i = c(x_i) và w(e) = \sum_{i=1}^{k-1}(z_{ei} - z_{e, i+1})\frac{c_i}{r_i} + z_{ek}\frac{c_k}{r_k} = \frac{c_1}{r_1}z_{e1} + \sum_{i=2}^k(\frac{c_i}{r_i}-\frac{c_{i - 1}}{r_{i -1}})z_{ei}
Trước tiên, ta chứng minh hai mệnh đề sau:
Mệnh đề 1: c(A) \le \sum_{y_e \in A^*}w(e)
Để chứng minh Mệnh đề 1, ta có:
c(A) = \sum_{i=1}^k \frac{r_i}{r_i}c_i = \sum_{i=1}^{k-1}\frac{c_i}{r_i}(\sum_{j=1}^k r_j - \sum_{j=i+1}^{k}r_j) + \frac{c_k}{r_k}\sum_{j=k}^k r_j
= \frac{c_1}{r_1} \sum_{j=1}^k r_j + \sum_{i=2}^k (\frac{c_i}{r_i} - \frac{c_{i-1}}{r_{i-1}}) \sum_{j=i}^k r_j
Hơn nữa, hàm f là submodular và monotone increasing, ta có:
r_1/c_1 \ge r_2/c_2 \ge \dots \ge r_k/c_k
Vì vậy, để chứng minh Mệnh đề 1, chúng ta chỉ cần chứng minh
\sum_{j=1}^k r_j \le \sum_{y_e \in \mathcal{C}^*} z_{ei} \ \forall i = 1, \dots, k là xong.
Ta có,
\sum_{j=i}^k r_j = f(A) - f(A_{i-1}) = f(A^*) - f(A_{i-1})
= f(A^* \cup A_{i-1}) - f(A_{i-1}) = \Delta_{A^*}f(A_{i-1})
\le \sum_{y_e \in A^*} \Delta_{y_e}f(A_{i-1}) = \sum_{y_e in A^*} z_{ei}
Vậy là chúng ta đã chứng minh xong Mệnh đề 1.
Mệnh đề 2: \forall y_e \in A^*, ta có:
w(e) \le c(y_e) \sum_{i=1}^\gamma \frac{1}{i}
Chứng minh Mệnh đề 2 khá đơn giản. Chú ý rằng \frac{c_i}{r_i} \le \frac{e(y_e)}{z_{ei}} (theo Algorithm 3} và z_{ei} \ge z_{e, i+1} (f là monotone increasing và submodular)
Vì vậy, chúng ta dễ dàng có:
w(e) = \sum_{i=1}^{k-1}(z_{ei} - z_{e,i+1}) \frac{c_i}{r_i} + z_{ek}\frac{c_k}{r_k}
\le \sum_{i=1}^{k-1}(z_{ei} - z_{e,i+1}) \frac{c(y_e)}{z_{ei}} + z_{ek}\frac{c(y_e)}{z_{ek}} \le c(y_e) \sum_{i=1}^{z_{e1}} \frac{1}{i}
Có được bước cuối cùng vì z_{ei} là số nguyên. Chú ý rằng z_{e1} \le \gamma \ \forall y_e \in A^*. Nên từ hai mệnh đề, ta chứng minh xong định lý 4.
\Box
Ghi chú: Nếu f(\emptyset) \neq 0, chúng ta đặt g(A) = f(A) - f(\emptyset). Lúc đó, g là hàm nguyên, monotone increasing, submodular, và g(\emptyset) = 0. Suy ra, \gamma = \max_{x \in E} f(\{x\} - f(\emptyset)).
Vậy cho mỗi bài minimization, nếu ta tìm được hảm f thỏa mãn các điều kiện trên thì ta có một thuật toán xấp xỉ với tỉ lệ 1 + \ln \gamma).
Bài tập:
Bài tập 1: Chứng minh Định lý 1.
Bài tập 2: Chứng minh Bổ đề 1.
Bài tập 3: Trong chứng minh Bổ đề 2, tại bước gần cuối, ta dựa theo Bổ đề 1. Tại sao ta cần f là monotone increasing. Nếu f chỉ là submodular function thì chuyện gì xảy ra?
Bài tập 4: Chứng minh Định lý 3.
Bài tập 5: Nếu f không là hàm số nguyên, thì Định lý 4 sẽ thay đổi như thế nào?
Nguồn: https://thaitramy.wordpress.com/2010/01/11/submodular-function/
Read More