Skip to main content

Lấy mẫu con

Đánh giá hàm mất mát với kỹ thuật lấy mẫu con​

1) Vấn đề

Như các bạn từng nghe tới thuật toán SGD khi đào tạo một mô hình học máy.

Bảng trên so sánh hai thuật toán đó là Gradient Descent và Stochastic Gradient Descent. Hai thuật toán này đều có mục tiêu tìm ra giá trị nhỏ nhất có thể của hàm mất mát.

Với thuật toán SGD ta nhận thấy, với bộ dữ liệu có 10610^6 phần tử thì trong mỗi vòng lặp, ta cũng cần phải tính giá trị hàm mất mát với số lượng tương đương 10610^6 lần.

Rõ ràng dễ dàng nhận thấy sẽ tốt hơn nếu có một cơ chế lặp ít hơn để cập nhật bộ tham số thay vì lặp qua toàn bộ.

2) Cách giải quyết

Kỹ thuật lấy mẫu con - Subsampling.

Chúng ta có thể dùng kỹ thuật lấy mẫu con để xấp xỉ tốt nhất việc lặp 10610^6 lần bên trên.

Giả sử ZZ là một biến ngẫu nhiên có giá trị ∂cost(θ,(x(i),y(i)))\partial{cost(\theta, (x^{(i)}, y^{(i)}))} có xác suất xảy ra đó là 1n\frac{1}{n}. Cho nên ta dễ nhận ra một điều:

E[Z]=1n∑i=1ncost(θ,(x(i),y(i)))=J(θ)E[Z] = \frac{1}{n}\sum_{i=1}^{n}cost(\theta, (x^{(i)}, y^{(i)})) = J(\theta)

Giả sử trong 10610^6 lần tính toán bên trên, ta lấy ra K\bold{K} lần ngẫu nhiên IID (độc lập và có cùng phân phối) Z1,Z2,⋯ZnZ_1, Z_2, \cdots Z_n giống ZZ bên trên thì trung bình những giá trị này sẽ có thể xấp xỉ J(θ)J(\theta). Tức là:

S(K)=1K∑1KZk≈J(θ)S(K) = \frac{1}{K}\sum_{1}^{K}Z_k \approx J(\theta)

Biểu thức bên trên có thể kết luật dựa theo luật số lớn (The law of large numbers) và định lý giới hạn trung tâm (Central limit theorem) thì trung bình mẫu lấy ra với số lượng đủ lớn K gần với kỳ vọng phân phối của ZZ.

Và câu hỏi đặt ra thì K cần lấy ít nhất bao nhiêu là đủ để có thể xấp xỉ giá trị hàm mất mát?

Theo bất đẳng thức Chebyshev’s ta chứng minh được như sau:

P(∣SK−E[Z∣⩾a)⩽1a24KP(| S_K - E[Z| \geqslant a) \leqslant \frac{1}{a^24K}

Biểu thức này cho ta biết có thể tìm ra cận trên của một ước lượng xác suất khả năng sai lệch giữa trung bình các mẫu với kỳ vọng biến ngẫu nhiên.

Ta ứng dụng công thức này như thế nào?

Ví dụ, nếu bạn muốn ước lượng giá trị mất mát sao cho xác suất đại lượng thể hiện độ lệch giữa trung bình các mẫu với giá trị mất mát thật nhỏ hơn 10% với giá trị lớn hơn 99%. Thì cần số lượng mẫu ước lượng KK là bao nhiêu?

Lời giải: Câu hỏi đề bài sẽ được quy về như sau:

P(∣S(K)−J(θ)∣⩽0.1)⩾0.99⇔P(∣S(K)−J(θ)∣⩾0.1)⩽0.01P(|S(K) - J(\theta)| \leqslant 0.1) \geqslant 0.99 \\ \Leftrightarrow P(|S(K) - J(\theta)| \geqslant 0.1) \leqslant 0.01

Để điều này xảy ra thì cận trên của P(∣S(K)−J(θ)∣⩾0.1)P(|S(K) - J(\theta)| \geqslant 0.1) phải nhỏ hơn 0.010.01 tức là:

1a24K⩽0.01⇔K⩾14×0.012=2500\frac{1}{a^24K} \leqslant 0.01 \\ \Leftrightarrow K \geqslant \frac{1}{4 \times 0.01^2} = 2500

Vậy cần ít nhất 2500 mẫu để có thể thực hiện được điều này.