ToanNV's Blog

ToanNV

Developer, living in Tokyo, get married.


The only person you should try to be better than is the person you were yesterday.

[Course][ML] Logistic Regression

Classification

Classification hay tiếng việt còn gọi là phân loại, phân lớp. Là bài toán thường gặp trong cuộc sống và được nghiên cứu nhiều trong ML. Một số ví dụ về việc phân loại mà chúng ta thường gặp trong cuộc sống như: phân loại email là spam hay không spam, phân loại một khối u là lành tính hay ác tính, phân loại xem một hành vi trên mạng xã hội có phải là lừa đảo hay không... các ví dụ trên là kết quả mà chúng ta thường nhìn thấy hàng ngày. Vậy thực tế thì chương trình máy tính làm việc như thế nào để đưa ra những kết quả đó.

Trong bài toán phân loại, chương trình máy tính sẽ phải đưa ra nhãn của một điểm dữ liệu, các nhãn này thường được định nghĩa từ trước. Ví dụ ta có thể gán nhãn cho các email không phải spam là 0, các email spam là 1. Hoặc u lành tính là 0, u ác tính là 1... Cũng giống như bài toán Linear regression, ta cũng phải xây dựng một hàm hθ(x)h_{\theta}(x) để mapping từ tập input XX và output yy.

Đi vào bài toán cụ thể: "Phân loại khối u là lành tính hay ác tính, dựa trên kích thước của khối u." Ở đây, ta có hai nhãn cần phải phân loại là: lành tính(0) và ác tính(1).

y{0,1}y \in \{0, 1\}

Như vậy, ta có thể biếu diễn trên hệ trục toạ độ như hình dưới đây.

logistic regression

Trục hoành biểu diễn kích thước của khối u, trục tung biểu diễn các lớp được phân loại. Trong trường hợp này có 2 nhãn là ác tính có giá trị 1, và u lành có giá trị là 0. Nếu ta áp dụng phương pháp linear regression vào bài toán này, tức là ta sẽ có hàm hypothesis có dạng hθ(x)=ΘTXh_{\theta}(x)=\Theta^{T}X. Vẽ đồ thì của hàm hθ(x)h_{\theta}(x) trên hệ trục toạ độ.

logistic regression

Với đồ thì như như thế này thì ta có thể dự đoán kết quả, nếu hθ(x)0.5h_{\theta}(x) \geq 0.5 thì y=1y = 1, nếu hθ(x)<0.5h_{\theta}(x) < 0.5 thì y=0y = 0.

logistic regression

Tuy nhiên, có một vài vấn đề với vấn đề này. Giả sử như kích thước của khối u có một điểm ngoại lệ như hình trên, khi đó việc dự đoán theo mô hình này sẽ bị sai. Hơn nữa, với việc phân loại, mà cụ thể là trường hợp binary classification(tức là đầu ra chỉ có hai nhãn 0 và 1) như này thì yêu cầu: 0hθ(x)10 \leq h_{\theta}(x) \leq 1. Với bài toán như này thì chúng ta có cách giải quyết với logistic regression

Logistic regression

Trong tên của thuật toán có từ regression, nhưng thực ra đây là thuật toán dùng để phần loại. Mô hình của bài toán này là hàm sigmoid(sigmoid function) hay còn gọi là logistic function.

hθ(x)=g(θTx)h_{\theta}(x) = g(\theta^{T}x)
z=θTxz = \theta^{T}x
g(z)=11+ezg(z) = \frac{1}{1 + e^{-z}}

Khi đó đồ thì hàm hθ(x)h_{\theta}(x) sẽ trở thành như sau:

logistic regression

hàm hθ(x)h_{\theta}(x) luôn nằm trong khoảng [0,1][0,1], nghĩa là hθ(x)h_{\theta}(x) luôn mang lại một xác suất để output là 1. Ví dụ: hθ(x)=0.7h_{\theta}(x) = 0.7 khi đó xác suất để điểm dữ liệu đó có nhãn 1 là 70%, và xác suất điểm dữ liệu đó có nhãn 0 là 30%.

KaTeX parse error: Expected 'EOF', got '−' at position 34: …y=1|x;\theta)=1−̲P(y=0|x;\theta)
P(y=1x;θ)+P(y=0x;θ)=1P(y=1|x;\theta) + P(y=0|x;\theta) = 1

Bởi vì, đầu ra là hai lớp riêng biệt có nhãn là 0 và 1, nên ta giả sử:

hθ(x)0.5y=1h_{\theta}(x) \geq 0.5 \rightarrow y = 1
hθ(x)<0.5y=0h_{\theta}(x) < 0.5 \rightarrow y = 0

Theo như hàm sigmoid ở trên:

  • Khi z=0z = 0 thì e0=1e^{0} = 1 và khi đó hθ(x)=g(z)=0.5h_{\theta}(x) = g(z) = 0.5
  • Khi zz \rightarrow \infty thì e0e^{-\infty} \rightarrow 0 và khi đó hθ(x)=g(z)=1h_{\theta}(x) = g(z) = 1
  • Khi zz \rightarrow -\infty thì ee^{\infty} \rightarrow \infty và khi đó hθ(x)=g(z)=0h_{\theta}(x) = g(z) = 0

g(z)0.5\Rightarrow g(z) \geq 0.5 khi z>0z > 0, và g(z)<0.5g(z) < 0.5 khi z<0z < 0. Nghĩa là, hθ(x)=g(θTx)0.5h_{\theta}(x) = g(\theta^{T}x) \geq 0.5 khi θTx0\theta^{T}x \geq 0, và hθ(x)=g(θTx)<0.5h_{\theta}(x) = g(\theta^{T}x) < 0.5 khi θTx<0\theta^{T}x < 0

Từ đó ta có thể rút ra kết luận:

θTx0y=1\theta^{T}x \geq 0 \Rightarrow y = 1
θTx<0y=0\theta^{T}x < 0 \Rightarrow y = 0

\Rightarrow đường tạo bởi θTx\theta^{T}x sẽ chia thành hai vùng có y=0y = 0y=1y = 1. Đường này người ta gọi là decision boundary. Ví dụ:

θ=[510]\theta = \begin{bmatrix}5 \\ -1 \\ 0 \end{bmatrix}

y=1\Rightarrow y = 1 nếu 5+(1)x1+0x205x10x155 + (-1)x_{1} + 0x_{}2 \geq 0 \Leftrightarrow 5 - x_{1} \geq 0 \Leftrightarrow x_{1} \leq 5

Trong trường hợp này, đường decision boundary là đường thẳng x1=5x_{1} = 5 và tất cả mọi điểm nằm bên trái đường thằng này đều có nhãn là y=1y = 1, và mọi điểm nằm bên phải đường thằng này đều có nhãn là y=0y = 0.

Dĩ nhiên là ΘTX\Theta^{T}X không nhất thiết phải là hàm tuyến tính, nó có thể là hàm số biểu diễn đường tròn hoặc một hình nào đó tuỳ thuộc vào tập dữ liệu đầu vào.

Cost Function

Trong bài toán logistic regression, chúng ta không thể sử dụng hàm mất mát của linear regression được, vì nó không phải là một hàm lồi, mà là một hàm có nhiều cung với nhiều điểm local optimum. Hàm mất mát của logistic regression có dạng sau:

J(θ)=1mi=1mCost(hθ(x(i)),y(i))J(\theta) = \frac{1}{m}\sum\limits_{i=1}^mCost(h_{\theta}(x^{(i)}), y^{(i)})
Cost(hθ(x),y)=log(hθ(x))ne^ˊuy=1Cost(h_{\theta}(x), y) = -\log(h_{\theta}(x))\; nếu \; y = 1
Cost(hθ(x),y)=log(1hθ(x))ne^ˊuy=0Cost(h_{\theta}(x), y) = -\log(1 - h_{\theta}(x))\; nếu \; y = 0

Khi y=1y = 1 thì hàm J(θ)J(\theta) sẽ được biểu diễn như hình dưới đây.

logistic regression

Khi y=0y = 0 thì hàm J(θ)J(\theta) sẽ được biểu diễn như hình dưới đây.

logistic regression

Ta có thể dễ dàng nhận ra:

  • Nếu y=0y = 0, cost function bằng 0 nếu hypothesis function = 0, và tiến đến dương vô cùng nếu hypothesis function tiến đến 1.
  • Nếu y=1y = 1, cost function bằng 0 nếu hypothesis function = 1, và tiến đến dương vô cùng nếu hypothesis function tiến đến 0.
Cost(hθ(x),y)=0khihθ(x)=yCost(h_{\theta}(x), y) = 0 \; khi \; h_{\theta}(x) = y
Cost(hθ(x),y)khiy=0vaˋhθ(x)1Cost(h_{\theta}(x), y) \rightarrow \infty \; khi \; y = 0 \; và \; h_{\theta}(x) \rightarrow 1
Cost(hθ(x),y)khiy=1vaˋhθ(x)0Cost(h_{\theta}(x), y) \rightarrow \infty \; khi \; y = 1 \; và \; h_{\theta}(x) \rightarrow 0

Gradient Descent

Ta có thể gộp hai điều kiện của hàm cost function lại thành như sau:

Cost(hθ(x),y)=ylog(hθ(x))(1y)log(1hθ(x))Cost(h_{\theta}(x), y) = -y\log(h_{\theta}(x)) - (1 - y)\log(1 - h_{\theta}(x))

Thật vậy, do yy chỉ có 2 giá trị là 0 và 1. Nếu y=0y = 0, thì ylog(hθ(x))=0-y\log(h_{\theta}(x)) = 0, còn nếu y=1y = 1, thì (1y)log(1hθ(x))=0(1 - y)\log(1 - h_{\theta}(x)) = 0, vì vậy mà nó không ảnh hưởng gì đến kêt qủa của hàm Cost(hθ(x),y)Cost(h_{\theta}(x), y)

Hàm mất mát có thể được viết đầy đủ như sau:

J(θ)=1mi=1m[y(i)log(hθ(x(i)))(1y(i))log(1hθ(x(i)))]J(\theta) = \frac{1}{m}\sum\limits_{i=1}^m[-y^{(i)}\log(h_{\theta}(x^{(i)})) - (1 - y^{(i)})\log(1 - h_{\theta}(x^{(i)}))]

Có thể biểu diễn bằng vector như sau:

J(θ)=1m(yTlog(h)(1y)Tlog(1h))J(\theta) = \frac{1}{m}\cdot(-y^{T}\log(h)-(1-y)^{T}\log(1-h))

Đến đây chúng ta cần phải tối ưu hàm J(θ)J(\theta), và có một tin tốt là ta có thể sử dụng phương pháp Gradient Descent. Đạo hàm của hàm J(θ)J(\theta) tại một điểm dữ liệu được tính như sau:

θjJ(θ)=Jθhhzzθj\frac{\partial}{\partial\theta_{j}}J(\theta) = \frac{\partial J_{\theta}}{\partial h} \frac{\partial h}{\partial z} \frac{\partial z}{\partial \theta_{j}}

Với z=θTxz = \theta^{T}xh=hθ(x)h = h_{\theta}(x).

Đạo hàm của hàm Jθh\frac{\partial J_{\theta}}{\partial h}:

Jθh=yh+1y1h\frac{\partial J_{\theta}}{\partial h} = \frac{-y}{h} + \frac{1 - y}{1 - h}
Jθh=yhh(1h)\frac{\partial J_{\theta}}{\partial h} = -\frac{y - h}{h(1 - h)}

Đạo hàm của hàm hz\frac{\partial h}{\partial z}:

hz=hθ(x)(1hθ(x))\frac{\partial h}{\partial z} = h_{\theta}(x)(1 - h_{\theta}(x))
hz=h(1h)\frac{\partial h}{\partial z} = h(1 - h)

Đạo hàm của hàm zθj\frac{\partial z}{\partial \theta_{j}}:

zθj=xj\frac{\partial z}{\partial \theta_{j}} = x_{j}

\Rightarrow gộp các biểu thức trên lại ta được:

θjJ(θ)=yhh(1h)h(1h)xj\frac{\partial}{\partial\theta_{j}}J(\theta) = -\frac{y - h}{h(1 - h)}h(1 - h)x_{j}
θjJ(θ)=(hy)xj\frac{\partial}{\partial\theta_{j}}J(\theta) = (h - y)x_{j}
θjJ(θ)=(hθ(x)y)xj\frac{\partial}{\partial\theta_{j}}J(\theta) = (h_{\theta}(x) - y)x_{j}

Vậy khi đó đạo hàm của J(θ)J(\theta) trên toàn bộ tập dữ liệu sẽ là:

θjJ(θ)=1mi=1m(hθ(x(i))y(i))xj(i)\frac{\partial}{\partial\theta_{j}}J(\theta) = \frac{1}{m}\sum\limits_{i = 1}^{m}(h_{\theta}(x^{(i)}) - y^{(i)})x_{j}^{(i)}

Với hθ(X)=11+eΘTXh_{\theta}(X) = \frac{1}{1 + e^{-\Theta^TX}}

Vậy theo phương pháp Gradient descent, tham số sau mỗi vòng lặp được cập nhật theo công thức sau:

θj:=θjα1mi=1m(hθ(x(i))y(i))xj(i)\theta_{j} := \theta_j - \alpha\cdot\frac{1}{m}\sum\limits_{i = 1}^{m}(h_{\theta}(x^{(i)}) - y^{(i)})x_{j}^{(i)}

Với α\alpha là learning rate.

Multiclass Classification: One-vs-all

Trên đây là cách xử lý với binary classification, vậy với bài toán cần phân loại nn nhãn khác nhau thì ta phải xử lý chúng như thế nào? Khi đó chúng ta sẽ chia bài toán ra thành n+1n + 1 bài toán phân lớp binary classification, và trong mỗi bài toán ta sẽ tính được xác xuất yy thuộc nhãn nào.

y{0,1,,n}y \in \{0, 1, \dots, n\}
hθ(0)(x)=P(y=0x;θ)h_{\theta}^{(0)}(x) = P(y=0|x;\theta)
hθ(1)(x)=P(y=1x;θ)h_{\theta}^{(1)}(x) = P(y=1|x;\theta)
\dots
hθ(n)(x)=P(y=nx;θ)h_{\theta}^{(n)}(x) = P(y=n|x;\theta)
prediction=maxihθ(i)(x)\Rightarrow prediction = \max\limits_{i}h_{\theta}^{(i)}(x)

\Rightarrow Để phân loại n nhãn thì chúng ta cần train n lần