Parameter Estimation techniques applied in Machine Learning

Bài này tóm tắt các kĩ thuật ước lượng tham số, vốn có nguồn gốc từ lí thuyết xác suất thống kê, đang được dùng rộng rãi trong Machine Learning. Bài này chỉ là ôn lại để chuẩn bị cho 1 series về Gaussian Process nên sẽ hơi sơ sài, không có ví dụ.

Trong thống kê, bài toán ước lượng tham số có thể tóm tắt như sau: Cho tập dữ liệu \left\{x_i\right\}_{i=1}^n, x_i \in \mathbf{R}^d, biết rằng tập dữ liệu này lấy mẫu từ phân phối f\left(x, \theta\right), với \theta là tham số.  Hãy ước lượng giá trị của tham số \theta.

Như vậy ta cần tập mẫu \left\{x_i\right\}_{i=1}^n, và biết trước dạng của hàm f\left(x, \theta\right).

1. Frequentist: Maximum Likelihood Estimation (MLE)

Theo trường phái frequentist, tham số \theta chỉ đơn giản là ẩn số (constant-valued but unknown), và MLE là một phương pháp thống kê để ước lượng ẩn số này.

Theo đó, hàm likelihood được định nghĩa là:

L\left(x_1, x_2, ..., x_n | \theta\right) = \prod_{i=1}^n f\left(x_i, \theta\right)

Ý tưởng là để \theta “phù hợp” với tập mẫu thì giá trị của L phải càng lớn càng tốt. Do đó bài toán ước lượng \theta chính là tìm \theta để L đạt cực đại:

\displaystyle \theta_{ML} = \arg\max_{\theta} \prod_{i=1}^n f\left(x_i, \theta\right)     (1)

Có nhiều cách để giải bài toán này. Nếu công thức của L là closed-form thì có thể giải rất đơn giản bằng cách tính đạo hàm và giải phương trình đạo hàm bằng 0.

Thông thường vì công thức của L là tích của nhiều đại lượng nhỏ, nên thay vì tìm cực đại của L, người ta tìm cực đại của log(L):

\displaystyle \log L = \sum_{i=1}^n\log f\left(x_i, \theta\right)

Và lời giải của MLE là nghiệm của phương trình:

\displaystyle \frac{\partial \log L}{\partial \theta} = \sum_{i=1}^n \left(\frac{1}{f\left(x_i, \theta\right)}\frac{\partial f\left(x_i, \theta\right)}{\partial \theta}\right) = 0

 Tuy nhiên trong thực tế, công thức (1) không closed-form thì bài toán được chuyển thành 1 bài toán optimization.

2. Bayesian estimators: MAP and EAP

Theo trường phái Bayesian, \theta không chỉ đơn giản là ẩn số, mà là một biến ngẫu nhiên, và ta không biết giá trị của nó. Vì là biến ngẫu nhiên nên ta sẽ đặt một phân phối prior p\left(\theta\right) để mô hình hoá “niềm tin” của ta về giá trị của \theta. Thật ra đây là cách “hiển nhiên” để biểu thị niềm tin rằng \theta là một biến ngẫu nhiên.

Vậy bây giờ ta có cả hàm likelihood L\left(x_1, x_2, ..., x_n | \theta\right) và xác suất prior p\left(\theta\right), một cách hiển nhiên ta sẽ dùng định lí Bayes để tính xác suất posterior:

\displaystyle \begin{array}{rl} p\left(\theta \vert x_1, x_2, ..., x_n\right) = & \frac{\displaystyle L\left(x_1, x_2, ..., x_n | \theta\right)p\left(\theta\right)}{\displaystyle \int L\left(x_1, x_2, ..., x_n | \theta'\right)p\left(\theta'\right)d\theta'} \\ & \frac{\displaystyle \left(\prod_{i=1}^n f\left(x_i, \theta\right)\right)p\left(\theta\right)}{\displaystyle \int \left(\prod_{i=1}^n f\left(x_i, \theta\right)p\left(\theta'\right)\right)d\theta'} \end{array}     (2)

Cho một sample mới x, ta có thể tính xác suất sample đó thuộc vào tập huấn luyện bằng công thức xác suất điều kiện:

\displaystyle p\left(x \vert x_1, x_2, ..., x_n\right) = \int f\left(x, \theta\right)p\left(\theta \vert x_1, x_2, ..., x_n\right)d\theta   (3)

Dựa vào (2) và (3) có một số thứ thú vị mà ta có thể làm:

Thứ nhất, để ước lượng giá trị của \theta, ta có thể dùng kì vọng của (2):

\displaystyle \theta_{EAP} = E \left[\theta \vert x_1, x_2, ..., x_n\right] = \int \theta p\left(\theta \vert x_1, x_2, ..., x_n\right)d\theta

Đây gọi là Expected a Posteriori (EAP) estimation. Tuy nhiên tính tích phân trên toàn miền giá trị của \theta khá là bất khả thi trong thực tế. Người ta thường dùng Maximum A Postoeriori, như sau.

Thứ hai, thay vì ước lượng EAP, ta có thể ước lượng điểm bằng MAP:

\displaystyle \theta_{MAP} = \arg \max_{\theta} p\left(\theta \vert x_1, x_2, ..., x_n\right)

Vì mẫu số trong (2) không phụ thuộc vào \theta, nên công thức trên có thể viết lại thành:

\displaystyle \theta_{MAP} = \arg \max_{\theta} \prod_{i=1}^n f\left(x_i, \theta\right) p\left(\theta\right)    (4)

Để ý rằng công thức (4) giống hệt (1), chỉ thêm phần xác suất prior của \theta. Trên thực tế nếu p\left(\theta\right) là phân phối uniform thì MAP chính là MLE.

Thứ ba, (3) là công thức của một phân phối xác suất đầy đủ cho mọi sample. Như vậy ta hoàn toàn có thể tính được expected values của phân phối này:

\displaystyle E\left[x \vert x_1, x_2, ..., x_n\right] = \int x p\left(x \vert x_1, x_2, ..., x_n\right) dx    (5)

Tuỳ vào ngữ cảnh bài toán cụ thể, đây gọi là “fully Bayesian inference”, vì ta tính tích phân qua tất cả các giá trị của \theta.

Thông thường người ta hay chọn \theta ~ N\left(0, \tau^2I\right), khi đó MAP thường ít overfitting hơn MLE, vì nói chung giá trị của \theta chọn bằng MAP sẽ có norm nhỏ hơn so với giá trị \theta chọn bằng MLE.

 3. Applied in Machine Learning: discriminative models

Rất nhiều mô hình Machine Learning là discriminative. Những mô hình này (logistic regression, neural networks…) mô hình hoá xác suất có điều kiện p\left(y\vert x\right), thay vì p\left(x, y\right). Khi đó lí thuyết đề cập trong bài này đều có thể áp dụng, nhưng thay vì viết f\left(x, \theta\right), ta viết p\left(y | x; \theta\right). Như vậy các công thức (1), (4), (5) trở thành:

\displaystyle \theta_{ML} = \arg\max_{\theta} \prod_{i=1}^n f\left(y_i \vert x_i; \theta\right)   (6)

\displaystyle \theta_{MAP} = \arg \max_{\theta} \prod_{i=1}^n f\left(y_i \vert x_i, \theta\right) p\left(\theta\right)   (7)

\displaystyle E\left[y \vert x, x_1, x_2, ..., x_n\right] = \int y p\left(y \vert x, x_1, x_2, ..., x_n\right) dy   (8)

Lưu ý là trong (7) ta viết p\left(y_i \vert x_i, \theta\right) vì trong cách tiếp cận Bayesian, \theta cũng là một biến ngẫu nhiên.

Các công thức (6), (7) sẽ còn được gặp lại trong các bài sau về Gaussian Process.

Advertisements

2 comments

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s