CS 229 - Học máy

Học có giám sát cheatsheet
Star

Bởi Afshine AmidiShervine Amidi


Dịch bởi Trần Tuấn Anh, Đàm Minh Tiến, Hung Nguyễn và Nguyễn Trí Minh

Giới thiệu về học có giám sát

Cho một tập hợp các điểm dữ liệu $\{x^{(1)}, ..., x^{(m)}\}$ tương ứng với đó là tập các đầu ra $\{y^{(1)}, ..., y^{(m)}\}$, chúng ta muốn xây dựng một bộ phân loại học được cách dự đoán $y$ từ $x$.

Loại dự đoán Các loại mô hình dự đoán được tổng kết trong bảng bên dưới:

Hồi quy Phân loại
Đầu ra Liên tục Lớp
Các ví dụ Hồi quy tuyến tính Hồi quy Logistic, SVM, Naive Bayes

Loại mô hình Các mô hình khác nhau được tổng kết trong bảng bên dưới:

Mô hình phân biệt Mô hình sinh
Mục tiêu Ước lượng trực tiếp $P(y|x)$ Ước lượng $P(x|y)$ để tiếp tục suy luận $P(y|x)$
Những gì học được Biên quyết định Phân bố xác suất của dữ liệu
Hình minh hoạ Discriminative model Generative model
Các ví dụ Hồi quy, SVMs GDA, Naive Bayes

Các kí hiệu và khái niệm tổng quát

Hypothesis Hypothesis được kí hiệu là $h_\theta$, là một mô hình mà chúng ta chọn. Với dữ liệu đầu vào cho trước $x^{(i)}$, mô hình dự đoán đầu ra là $h_\theta(x^{(i)})$.


Hàm mất mát Hàm mất mát là một hàm số dạng: $L:(z,y)\in\mathbb{R}\times Y\longmapsto L(z,y)\in\mathbb{R}$ lấy đầu vào là giá trị dự đoán được $z$ tương ứng với đầu ra thực tế là $y$, hàm có đầu ra là sự khác biệt giữa hai giá trị này. Các hàm mất mát phổ biến được tổng kết ở bảng dưới đây:

Least squared error Mất mát Logistic Mất mát Hinge Cross-entropy
$\displaystyle\frac{1}{2}(y-z)^2$ $\displaystyle\log(1+\exp(-yz))$ $\displaystyle\max(0,1-yz)$
$\displaystyle-\Big[y\log(z)+(1-y)\log(1-z)\Big]$
Least squared error Logistic loss Hinge loss Cross entropy
Hồi quy tuyến tính Hồi quy Logistic SVM Mạng neural

Hàm giá trị (Cost function) Cost function $J$ thường được sử dụng để đánh giá hiệu năng của mô hình và được định nghĩa với hàm mất mát $L$ như sau:

\[\boxed{J(\theta)=\sum_{i=1}^mL(h_\theta(x^{(i)}), y^{(i)})}\]

Gradient descent Bằng việc kí hiệu $\alpha\in\mathbb{R}$ là tốc độ học, việc cập nhật quy tắc/ luật cho gradient descent được mô tả với tốc độ học và cost function $J$ như sau:

\[\boxed{\theta\longleftarrow\theta-\alpha\nabla J(\theta)}\]

Gradient descent

Chú ý: Stochastic gradient descent (SGD) là việc cập nhật tham số dựa theo mỗi ví dụ huấn luyện, và batch gradient descent là dựa trên một lô (batch) các ví dụ huấn luyện.


Likelihood Likelihood của một mô hình $L(\theta)$ với tham số $\theta$ được sử dụng để tìm tham số tối ưu $\theta$ thông qua việc cực đại hoá likelihood. Trong thực tế, chúng ta sử dụng log-likelihood $\ell(\theta)=\log(L(\theta))$ đễ dễ dàng hơn trong việc tôi ưu hoá. Ta có:

\[\boxed{\theta^{\textrm{opt}}=\underset{\theta}{\textrm{arg max }}L(\theta)}\]

Giải thuật Newton Giải thuật Newton là một phương thức số tìm $\theta$ thoả mãn điều kiện $\ell'(\theta)=0$. Quy tắc cập nhật của nó là như sau:

\[\boxed{\theta\leftarrow\theta-\frac{\ell'(\theta)}{\ell''(\theta)}}\]

Chú ý: Tổng quát hoá đa chiều, còn được biết đến như là phương thức Newton-Raphson, có quy tắc cập nhật như sau:

\[\theta\leftarrow\theta-\left(\nabla_\theta^2\ell(\theta)\right)^{-1}\nabla_\theta\ell(\theta)\]

Các mô hình tuyến tính

Hồi quy tuyến tính

Chúng ta giả sử ở đây rằng $y|x;\theta\sim\mathcal{N}(\mu,\sigma^2)$

Phương trình chuẩn Bằng việc kí hiệu $X$ là ma trận thiết kế, giá trị của $\theta$ làm cực tiểu hoá cost function là một phương pháp dạng đóng như sau:

\[\boxed{\theta=(X^TX)^{-1}X^Ty}\]

Giải thuật LMS Bằng việc kí hiệu $\alpha$ là tốc độ học, quy tắc cập nhật của giải thuật Least Mean Squares (LMS) cho tập huấn luyện của $m$ điểm dữ liệu, còn được biết như là quy tắc học Widrow-Hoff, là như sau:

\[\boxed{\forall j,\quad \theta_j \leftarrow \theta_j+\alpha\sum_{i=1}^m\left[y^{(i)}-h_\theta(x^{(i)})\right]x_j^{(i)}}\]

Chú ý: Luật cập nhật là một trường hợp đặc biệt của gradient ascent.


LWR Hồi quy trọng số cục bộ, còn được biết với cái tên LWR, là biến thể của hồi quy tuyến tính, nó sẽ đánh trọng số cho mỗi ví dụ huấn luyện trong cost function của nó bởi $w^{(i)}(x)$, được định nghĩa với tham số $\tau\in\mathbb{R}$ như sau:

\[\boxed{w^{(i)}(x)=\exp\left(-\frac{(x^{(i)}-x)^2}{2\tau^2}\right)}\]

Phân loại và logistic hồi quy

Hàm Sigmoid Hàm sigmoid $g$, còn được biết đến như là hàm logistic, được định nghĩa như sau:

\[\forall z\in\mathbb{R},\quad\boxed{g(z)=\frac{1}{1+e^{-z}}\in]0,1[}\]

Hồi quy logistic Chúng ta giả sử ở đây rằng $y|x;\theta\sim\textrm{Bernoulli}(\phi)$. Ta có công thức như sau:

\[\boxed{\phi=p(y=1|x;\theta)=\frac{1}{1+\exp(-\theta^Tx)}=g(\theta^Tx)}\]

Chú ý: không có giải pháp dạng đóng cho trường hợp của hồi quy logistic.


Hồi quy Softmax Hồi quy softmax, còn được gọi là hồi quy logistic đa lớp, được sử dụng để tổng quát hoá hồi quy logistic khi có nhiều hơn 2 lớp đầu ra. Theo quy ước, chúng ta thiết lập $\theta_K=0$, làm cho tham số Bernoulii $\phi_i$ của mỗi lớp $i$ bằng với:

\[\boxed{\displaystyle\phi_i=\frac{\exp(\theta_i^Tx)}{\displaystyle\sum_{j=1}^K\exp(\theta_j^Tx)}}\]

Mô hình tuyến tính tổng quát

Họ số mũ Một lớp của phân phối được cho rằng thuộc về họ số mũ nếu nó có thể được viết dưới dạng một thuật ngữ của tham số tự nhiên, cũng được gọi là tham số kinh điển (canonical parameter) hoặc hàm kết nối, $\eta$, một số liệu thống kê đầy đủ $T(y)$ và hàm phân vùng log (log-partition function) $a(\eta)$ sẽ có dạng như sau:

\[\boxed{p(y;\eta)=b(y)\exp(\eta T(y)-a(\eta))}\]

Chú ý: chúng ta thường có $T(y)=y$. Đồng thời, $\exp(-a(\eta))$ có thể được xem như là tham số chuẩn hoá sẽ đảm bảo rằng tổng các xác suất là một.

Ở đây là các phân phối mũ phổ biến nhất được tổng kết ở bảng bên dưới:

Phân phối $\eta$ $T(y)$ $a(\eta)$ $b(y)$
Bernoulli $\log\left(\frac{\phi}{1-\phi}\right)$ $y$ $\log(1+\exp(\eta))$ $1$
Gaussian $\mu$ $y$ $\frac{\eta^2}{2}$ $\frac{1}{\sqrt{2\pi}}\exp\left(-\frac{y^2}{2}\right)$
Poisson $\log(\lambda)$ $y$ $e^{\eta}$ $\displaystyle\frac{1}{y!}$
Geometric $\log(1-\phi)$ $y$ $\log\left(\frac{e^\eta}{1-e^\eta}\right)$ $1$

Giả thuyết GLMs Mô hình tuyến tính tổng quát (GLM) với mục đích là dự đoán một biến ngẫu nhiên $y$ như là hàm cho biến $x\in\mathbb{R}^{n+1}$ và dựa trên 3 giả thuyết sau:

$(1)\quad\boxed{y|x;\theta\sim\textrm{ExpFamily}(\eta)}$
$(2)\quad\boxed{h_\theta(x)=E[y|x;\theta]}$
$(3)\quad\boxed{\eta=\theta^Tx}$

Chú ý: Bình phương nhỏ nhất thông thường và hồi quy logistic đều là các trường hợp đặc biệt của các mô hình tuyến tính tổng quát.


Máy vector hỗ trợ

Mục tiêu của máy vector hỗ trợ là tìm ra dòng tối đa hoá khoảng cách nhỏ nhất tới dòng.

Optimal margin classifier Optimal margin classifier $h$ là như sau:

\[\boxed{h(x)=\textrm{sign}(w^Tx-b)}\]

với $(w, b)\in\mathbb{R}^n\times\mathbb{R}$ là giải pháp cho vấn đề tối ưu hoá sau đây:

\[\boxed{\min\frac{1}{2}||w||^2}\quad\quad\textrm{như là: }\quad \boxed{y^{(i)}(w^Tx^{(i)}-b)\geqslant1}\]
SVM

Chú ý: đường thẳng có phương trình là $\boxed{w^Tx-b=0}$.


Mất mát Hinge Mất mát Hinge được sử dụng trong thiết lập của SVMs và nó được định nghĩa như sau:

\[\boxed{L(z,y)=[1-yz]_+=\max(0,1-yz)}\]

Kernel (nhân) Cho trước feature mapping $\phi$, chúng ta định nghĩa kernel $K$ như sau:

\[\boxed{K(x,z)=\phi(x)^T\phi(z)}\]

Trong thực tế, kernel $K$ được định nghĩa bởi $K(x,z)=\exp\left(-\frac{||x-z||^2}{2\sigma^2}\right)$ được gọi là Gaussian kernal và thường được sử dụng.

SVM kernel

Chú ý: chúng ta nói rằng chúng ta sử dụng "kernel trick" để tính toán cost function sử dụng kernel bởi vì chúng ta thực sự không cần biết đến ánh xạ tường minh $\phi$, nó thường khá phức tạp. Thay vào đó, chỉ cần biết giá trị $K(x,z)$.


Lagrangian Chúng ta định nghĩa Lagrangian $\mathcal{L}(w,b)$ như sau:

\[\boxed{\mathcal{L}(w,b)=f(w)+\sum_{i=1}^l\beta_ih_i(w)}\]

Chú ý: hệ số $\beta_i$ được gọi là bội số Lagrange.


Generative Learning

Một mô hình sinh đầu tiên cố gắng học cách dữ liệu được sinh ra thông qua việc ước lượng P(x|y), sau đó chúng ta có thể sử dụng $P(x|y)$ để ước lượng $P(y|x)$ bằng cách sử dụng luật Bayes.

Gaussian Discriminant Analysis

Thiết lập Gaussian Discriminant Analysis giả sử rằng $y$ và $x|y=0$ và $x|y=1$ là như sau:

$(1)\quad\boxed{y\sim\textrm{Bernoulli}(\phi)}$
$(2)\quad\boxed{x|y=0\sim\mathcal{N}(\mu_0,\Sigma)}$
$(3)\quad\boxed{x|y=1\sim\mathcal{N}(\mu_1,\Sigma)}$

Sự ước lượng Bảng sau đây tổng kết các ước lượng mà chúng ta tìm thấy khi tối đa hoá likelihood:

$\widehat{\phi}$ $\widehat{\mu_j}\quad{\small(j=0,1)}$ $\widehat{\Sigma}$
$\displaystyle\frac{1}{m}\sum_{i=1}^m1_{\{y^{(i)}=1\}}$ $\displaystyle\frac{\sum_{i=1}^m1_{\{y^{(i)}=j\}}x^{(i)}}{\sum_{i=1}^m1_{\{y^{(i)}=j\}}}$ $\displaystyle\frac{1}{m}\sum_{i=1}^m(x^{(i)}-\mu_{y^{(i)}})(x^{(i)}-\mu_{y^{(i)}})^T$

Naive Bayes

Giả thiết Mô hình Naive Bayes giả sử rằng các features của các điểm dữ liệu đều độc lập với nhau:

\[\boxed{P(x|y)=P(x_1,x_2,...|y)=P(x_1|y)P(x_2|y)...=\prod_{i=1}^nP(x_i|y)}\]

Giải pháp Tối đa hoá log-likelihood đưa ra những lời giải sau đây, với $k\in\{0,1\},l\in[\![1,L]\!]$ $k\in\{0,1\},l\in[\![1,L]\!]$

\[\boxed{P(y=k)=\frac{1}{m}\times\#\{j|y^{(j)}=k\}}\quad\textrm{ and }\quad\boxed{P(x_i=l|y=k)=\frac{\#\{j|y^{(j)}=k\textrm{ và }x_i^{(j)}=l\}}{\#\{j|y^{(j)}=k\}}}\]

Chú ý: Naive Bayes được sử dụng rộng rãi cho bài toán phân loại văn bản và phát hiện spam.


Các phương thức Tree-based và ensemble

Các phương thức này có thể được sử dụng cho cả bài toán hồi quy lẫn bài toán phân loại.

CART Cây phân loại và hồi quy (CART), thường được biết đến là cây quyết định, có thể được biểu diễn dưới dạng cây nhị phân. Chúng có các ưu điểm có thể được diễn giải một cách dễ dàng.


Rừng ngẫu nhiên Là một kĩ thuật dựa trên cây (tree-based), sử dụng số lượng lớn các cây quyết định để lựa chọn ngẫu nhiên các tập thuộc tính. Ngược lại với một cây quyết định đơn, kĩ thuật này khá khó diễn giải nhưng do có hiệu năng tốt nên đã trở thành một giải thuật khá phổ biến hiện nay.

Chú ý: rừng ngẫu nhiên là một loại giải thuật ensemble.


Boosting Ý tưởng của các phương thức boosting là kết hợp các phương pháp học yếu hơn để tạo nên phương pháp học mạnh hơn. Những phương thức chính được tổng kết ở bảng dưới đây:

Adaptive boosting Gradient boosting
• Các trọng số có giá trị lớn được đặt vào các phần lỗi để cải thiện ở bước boosting tiếp theo • Các phương pháp học yếu huấn luyện trên các phần lỗi còn lại

Các cách tiếp cận phi-tham số khác

$k$-nearest neighbors Giải thuật $k$-nearest neighbors, thường được biết đến là $k$-NN, là cách tiếp cận phi-tham số, ở phương pháp này phân lớp của một điểm dữ liệu được định nghĩa bởi $k$ điểm dữ liệu gần nó nhất trong tập huấn luyện. Phương pháp này có thể được sử dụng trong quá trình thiết lập cho bài toán phân loại cũng như bài toán hồi quy.

Chú ý: Tham số $k$ cao hơn, độ chệch (bias) cao hơn, tham số $k$ thấp hơn, phương sai cao hơn.

k nearest neighbors

Lý thuyết học

Union bound Cho $k$ sự kiện là $A_1, ..., A_k$. Ta có:

\[\boxed{P(A_1\cup ...\cup A_k)\leqslant P(A_1)+...+P(A_k)}\]
Union bound

Bất đẳng thức Hoeffding Cho $Z_1, .., Z_m$ là $m$ biến iid được đưa ra từ phân phối Bernoulli của tham số $\phi$. Cho $\widehat{\phi}$ là trung bình mẫu của chúng và $\gamma>0$ cố định. Ta có:

\[\boxed{P(|\phi-\widehat{\phi}|>\gamma)\leqslant2\exp(-2\gamma^2m)}\]

Chú ý: bất đẳng thức này còn được biết đến như là ràng buộc Chernoff.


Lỗi huấn luyện (Training error) Cho trước classifier $h$, ta định nghĩa training error $\widehat{\epsilon}(h)$, còn được biết đến là empirical risk hoặc empirical error, như sau:

\[\boxed{\widehat{\epsilon}(h)=\frac{1}{m}\sum_{i=1}^m1_{\{h(x^{(i)})\neq y^{(i)}\}}}\]

Probably Approximately Correct (PAC) PAC là một framework với nhiều kết quả về lí thuyết học đã được chứng minh, và có tập hợp các giả thiết như sau:
- tập huấn luyện và test có cùng phân phối
- các ví dụ huấn luyện được tạo ra độc lập


Shattering (Chia nhỏ) Cho một tập hợp $S=\{x^{(1)},...,x^{(d)}\}$, và một tập hợp các classifiers $\mathcal{H}$, ta nói rằng $\mathcal{H}$ chia nhỏ $S$ nếu với bất kì tập các nhãn $\{y^{(1)}, ..., y^{(d)}\}$ nào, ta có:

\[\boxed{\exists h\in\mathcal{H}, \quad \forall i\in[\![1,d]\!],\quad h(x^{(i)})=y^{(i)}}\]

Định lí giới hạn trên Cho $\mathcal{H}$ là một finite hypothesis class mà $|\mathcal{H}|=k$ với $\delta$, kích cỡ $m$ là cố định. Khi đó, với xác suất nhỏ nhất là $1-\delta$, ta có:

\[\boxed{\epsilon(\widehat{h})\leqslant\left(\min_{h\in\mathcal{H}}\epsilon(h)\right)+2\sqrt{\frac{1}{2m}\log\left(\frac{2k}{\delta}\right)}}\]

VC dimension Vapnik-Chervonenkis (VC) dimension của class infinite hypothesis $\mathcal{H}$ cho trước, kí hiệu là $\textrm{VC}(\mathcal{H})$ là kích thước của tập lớn nhất được chia nhỏ bởi $\mathcal{H}$.

Chú ý: VC dimension của ${\small\mathcal{H}=\{\textrm{tập hợp các linear classifiers trong 2 chiều}\}}$ là 3.

VC dimension

Định lí (Vapnik) Cho $\mathcal{H}$ với $\textrm{VC}(\mathcal{H})=d$ và $m$ là số lượng các ví dụ huấn luyện. Với xác suất nhỏ nhất là $1-\delta$, ta có:

\[\boxed{\epsilon(\widehat{h})\leqslant \left(\min_{h\in\mathcal{H}}\epsilon(h)\right) + O\left(\sqrt{\frac{d}{m}\log\left(\frac{m}{d}\right)+\frac{1}{m}\log\left(\frac{1}{\delta}\right)}\right)}\]