Image Classification

Chào mừng bạn đến với các bài học Image classification, một trong những bài học thuộc mảng Computer Vision được mình viết trên blog cá nhân. Mong rằng qua những bài học trong series này, bạn sẽ nắm vững được một số kiến thức cơ bản trong việc phân loại hình ảnh sử dụng các phương pháp máy học, để từ đó có thể làm tiền đề cho những ứng dụng sau này của bản thân.
Bài 1 : Giới thiệu
Bài đầu tiên sẽ giới thiệu tổng quan về series image classification.
Bài 2 : Image classification
Bài này sẽ giới thiệu tổng quan về image classification
Bài 3 : Thuật toán Nearest Neighbor Classifier
Thuật toán phân lớp Người láng giềng gần nhất
Bài 4 : Cài đặt Nearest Neighbor Classifier với ngôn ngữ Python
Bài 5 : Thuật giải K-Nearest Neighbor
Bài 6 : Cài đặt K-Nearest Neighbor Classifier với ngôn ngữ Python
 Bắt đầu từ đây, các bài tiếp theo sẽ dính dáng khá nhiều tới toán học nhé mấy man. Nếu không hiểu công thức toán thì cứ kệ đi nhá :v Vì biết đâu đọc ví dụ lại hiểu. Đó cũng là cách mình đọc tài liệu ( vì mình không giỏi toán lắm).
Bài 7 : Score function
Bài 8 : Loss function
Bài 9: Optimization và Gradient Descent
Bài 10: Backpropagation
Bài 11: Giải thích quá trình máy học
Như vậy, chúng ta đã hiểu máy học là gì. Những phần tiếp theo, chúng ta sẽ tìm hiểu về model. Những model được đem vào mổ sẻ là ANN (mạng nơ ron nhân tạo) và CNN (mạng nơ ron tích chập).
Bài 12: Kiến trúc mạng neural nhân tạo
Bài 13: Cấu trúc của 1 neural
Bài 14: Tìm hiểu mạng CNN
 Okie, Vậy là chúng ta đã hoàn thành được bài CNN, cũng là bài cuối trong loạt series image classification của mình. Đây chỉ là kiến thức nền cơ bản để các bạn hiểu và nắm được các khái niệm của Classification và những mạng model dùng để giải quyết bài toán đó. Mong các bạn dựa vào đây có thể tự mình tìm hiểu và phát huy được bản thân trong lĩnh vực đầy thú vị này. Chào thân ái và quyết thắng.

Read More

Tìm hiểu về Convolutional Neural Network (CNN)

Chúng ta đã được tìm hiểu về mạng neural nhân tạo trong bài này. Nếu như đầu vào của chúng ta là 1 bức hình 30*30*3 pixel, thì lớp input của neural network sẽ là 30*30*3 neural. Số lượng neural này vẫn tạm chấp nhận được cho quá trình training vì chi phí tính toán cũng chưa phải là lớn lắm. Nhưng nếu đầu vào của chúng ta là bức hình 1000*1000*3, thì số lượng neural lúc này cực kì lớn và quá trình tính toán sẽ chậm đi rất nhiều, đồng thời mạng phức tạp sẽ dễ dẫn đến overfitting.
Mặt khác, với đối tượng đầu vào là bức hình, thì các pixel gần nhau hợp lại sẽ mang những thông tin hữu ích, nhưng neural network thì không khai thác được đặc điểm này. Do đó, có một mạng neural mới, được người ta nghiên cứu sáng tạo ra: đó là convolutional neural network (CNN). Vậy CNN khác với ANN như thế nào? Hiểu một cách nôm na thì CNN không đọc từng pixel riêng lẻ như ANN, mà nó sẽ đọc 1 loạt các pixel gần nhau để đưa vào tính toán. Nhưng để hiểu rõ hơn về cách hoạt động của CNN, chúng ta phải đi vào tìm hiểu từng thành phần cấu tạo nên mạng CNN mới rõ đc. Ở đây chúng ta sẽ tìm hiểu các khái niệm mới như Convolutional Layer, Pooling Layer.

Convolutional Layer:

Convolutional Layer là 1 lớp cực kì quan trọng trong CNN, nó đảm nhận hầu hết chức năng tính toán của mạng.

Để giải thích về Convolutional Layer, mình sẽ đi thẳng trực tiếp vào ví dụ để giải thích cho trực quan.
Đầu tiên là khái niệm filter map: thay vì kết nối với từng pixel của hình ảnh đầu vào như ANN, CNN có những tấm filter dùng để áp vào những vùng của bức hình. Các filter map này thực chất là một ma trận 3 chiều gồm các con số. Và điều bạn cần phải cực kì lưu ý là các con số này chính là các parameter cần phải học. Filter map có kích thước dài và rộng là hyperparameter ( hyperparameter là gì thì mình có nói trong bài này) , riêng chiều cao ( mình sẽ gọi là depth - chiều sâu ) của filter map sẽ bằng với depth của lớp trước.
Ví dụ nhìn vào hình ví dụ ở trên, chúng ta có 2 filter map màu hồng là W0 và W1. Mỗi filter map có kích thước 3*3*3. Kích thước dài * rộng ( 3*3 ) là hyperparameter, còn chiều sâu (Depth) sẽ bằng với depth của input volumn, tức là bằng 3.
Stride: như đã nói ở trên, filter map được dùng để trượt lên tấm hình đầu vào, vậy trượt ở đây có nghĩa là như thế nào? Rất đơn giản, chỉ cần dịch filter map theo pixel từ trái sang phải theo từng dòng. Mỗi lần dịch như thế sẽ dựa vào 1 giá trị gọi là stride.
Ví dụ, stride = 1, thì mỗi lần dịch filter map sẽ sang phải 1 pixel, khi hết cạnh biên phải thì xuống 1 dòng và dịch tiếp. Còn nếu stride = 2 thì mỗi lần dịch sẽ sang phải 2 pixel, khi hết cạnh thì xuống 2 dòng.  
Padding: người ta sẽ thêm những giá trị 0 bao quanh lớp input. Ví dụ như ở trên hình, lớp input của chúng ta ban đầu có kích thước 5*5*3, nhưng vì giá trị padding = 1, nên được bao thêm 1 lớp 0 bên ngoài. Từ đó, kích thước của lớp input = 7*7*3.
Feature map: feature map thực chất là kết quả sau khi lớp input được filter map quét qua hết. Với mỗi lần filter map áp lên input, sẽ có quá trình tính toán xảy ra. Vậy quá trình tính toán này là gì? Thực chất đó là quá trình nhân 2 ma trận.
Ví dụ như trên hình, khi lớp trên cùng của filter map W0 áp vào lớp trên cùng của input volum, ma trận filtermap w0 3*3 sẽ được nhân với ma trận 3*3 của input sau đó cộng thêm bias=1, và đưa ra kết quả = 2 ở feature map. Kích thước feature map được tính như nào? Mỗi lần 1 filter map trượt hết lên input volum sẽ cho ra 1 lớp của feature map. Vậy nên, depth của feature map sẽ bằng số lượng filter map.
Ví dụ như hình trên, depth của feature map = số lượng filter map = 2. Còn chiều dài và chiều rộng của feature map sẽ được tính bằng công thức: (W + 2P - F)/S +1 . Trong đó, W là kích thước input, P là padding, F là kích thước filter map, S là stride.
Ví dụ với hình, W = 5, P =1, F = 3, S =1 , ta tính được kích thước của feature map là 3.
Ta có thể thấy được, nếu với ANN thông thường, 1 bức hình 7*7*3 như trên sẽ cần có 7*7*3 = 147 parameters (nếu lớp thứ 2 chỉ có 1 neural), nhưng với CNN lại cần ít hơn số parameter từ filter map và số lượng parameter này có thể được chúng ta định lượng.

Pooling layer

Thường giữa các lớp Convolutional Layer với nhau người ta sẽ chèn vào 1 lớp Pooling layer để giảm bớt số lượng parameter lại nếu như đầu vào quá lớn. Có nhiều loại pooling layer, nhưng mình chỉ giới thiệu max pooling.

 

 Ví dụ ở trên, lớp max pooling có kích thước là 2*2, stride = 2. Với mỗi lần áp lên input, nó sẽ lấy giá trị lớn nhất trong khoảng filter đó và để nó vào output.

ReLU layer

Khái niệm về ReLU mình đã nói trong bài này rồi, các bạn quay lại để xem nhá. Thường thì sau khi feature map được tính ra, người ta sẽ xếp theo sau đó 1 lớp ReLU, lớp này sẽ áp dụng hàm ReLU lên tất cả các giá trị của feature map.

Fully Connected Layer

Để đưa ra được kết quả dự đoán thì lớp Neural network sẽ được thêm vào sau một mang CNN. Lớp neural này cũng chỉ là ANN bình thường thôi chứ ko khác gì cả. Vậy một mạng CNN thông thường sẽ có cấu trúc các lớp như thế nào? Sau đây là ví dụ:

INPUT -> [[CONV -> RELU]*N -> POOL?]*M -> [FC -> RELU]*K -> FC

Read More

Cấu trúc của 1 neural

Mỗi neural sẽ nhận vào các input. Các input này có thể là giá trị của tập dataset đưa vào (ví dụ như các điểm ảnh), hoặc input này cũng có thể là các giá trị output của layer trước đó. Mỗi input đi vào sẽ kèm với 1 giá trị Weight. Weight này có thể hiểu là 1 cái cầu nối giữa input và neural.
Lấy ví dụ như cái mạng nhện trong nhà bạn ấy, nhà bạn nào sạch quá ko có mạng nhện thì qua nhà hàng xóm xin coi cái mạng nhện như nào. Những cái weight này giống như mấy đường nối của mạng nhện, còn mấy cái điểm giao của mạng nhện cũng như là neural. Ok chưa?. (thực ra chả liên quan gì đâu :/ ).
Nói vòng vo nãy h, vậy cuối cùng neural là gì, có nhiệm vụ làm gì? Các bạn cứ hiểu neural là cái phòng để tính toán xử lí các dữ liệu dựa vào input và weight. Ở đây, nó sẽ làm phép tính tổng của các tích WiXi (Trong đó Wi là weight, và Xi là input). Nghe quen không? Nó y chang như cái hàm linear classifier trong bài function score đấy.

$F = Wx .$

Sau khi qua căn phòng tính toán. Giá trị sẽ được đi qua 1 hàm transfer function ( hay Activation function). Hàm này sẽ tiếp tục xử lý tùm lum tá lả để đưa ra 1 giá trị output. Vậy hàm activation function này là gì?

Activation function:

Thực ra activation function là một hàm toán học thôi, định nghĩa vậy là dễ hiểu nhất. Có rất nhiều loại Activation function nhé, sau đây mình sẽ giới thiệu qua một số hàm activation function chính, và mình cũng giới thiệu công thức thôi. Còn mấy vụ giải thích mặt toán học để xem xét nó xịn chỗ nào, nó cùi chỗ nào thì mình sẽ ko bàn tới nhé.  
Sigmoid: Hàm này có công thức:

$\sigma (x)= \frac{1}{1+e^{-x}}$

Giá trị x sau khi đi vào hàm này sẽ cho kết quả là 1 giá trị trong khoảng 0 – 1.

Tanh:

$tanh(x)=2\sigma (2x)-1$

Hàm này sẽ cho ra giá trị trong khoảng -1 đến 1

 

ReLU:

$f(x)=max(0,x)$

Hàm này lấy giá trị của x nếu x>0. Nếu x<0 0.

Ngoài ra còn có rất nhiều hàm activation function khác mà mình sẽ không kể đến. Mỗi hàm sẽ có ưu nhược điểm riêng, tùy theo bài toán giải quyết mà người ta sẽ lựa chọn cho phù hợp.

Read More

Kiến trúc mạng neural nhân tạo

Kiến trúc của một mạng neural

Mạng neural nhân tạo, Aritificial Neural network (viết tắt là ANN). Đây là mạng đang được nhắc đến siêu nhiều trong các bài quảng cáo về công nghệ AI, bạn chắc hẳn đã gặp đâu đó những câu từ như: “chúng được xây dựng dựa trên công nghệ AI, công nghệ này áp dụng một mạng nơ ron nhân tạo để học dữ liệu.. bla bla”. Vậy rút cuộc cái ANN là gì? Dưới đây là một mô hình tổng quan ANN.

Một ANN có 3 thành phần :
Input layer: là lớp đầu vào, như mô hình trên thì lớp đầu vào nhận 3 giá trị.
Hidden layer: lớp ẩn. Lớp này nhận giá trị từ lớp liền kề trước. Sau đó xử lí các thứ các thứ rồi truyền tiếp đi lớp sau (Xử lí gì thì chúng ta sẽ tìm hiểu sau, giờ cứ hiểu vậy đã). Một mạng ANN có thể có nhiều hidden layer.
Output layer: lớp đầu ra, là cái lớp xuất ra giá trị sau khi tính toán .

Các khái niệm cơ bản:

Neural: Mỗi cái cục tròn tròn trong hình là 1 neural. Cục này có nhiệm vụ xử lý nhân cộng các giá trị rồi đưa ra kết quả. Cục neural này sẽ được giới thiệu trong bài này.  
Cách đếm số lớp của ANN: Khi đếm số lớp của ANN, chúng ta không đếm lớp input. Ví dụ mạng bên trái là 2 lớp, mạng bên phải là 3 lớp.  
Số lượng neural của mạng: số lượng neural được tính bằng tổng số neural của hidden layer và output layer. Ví dụ mạng bên trái là 6 neurals, còn mạng bên phải là 9 neurals.  
Số lượng parameters của mạng: cái này thì tùy vào bạn có muốn gộp chung Weight và bias hay không. Số lượng bias bằng số lượng neural. Số lượng weights bằng số lượng gạch nối. Mình thì sẽ tính số lượng parameter bằng tổng số weight và bias. Ví dụ mạng bên trái là 20 parameters ( không tính bias) và bên phải là 32 parameters (không tính bias).  
Fully connected Layer: là loại layer mà tất cả các neural của layer trước liên kết với tất cả neural của layer kế nó. Ví dụ cả 2 mạng trên đều là fully connected Layer.

Read More

Giải thích quá trình máy học

Sau quá trình học được score function, loss function, optimization (gradient descent), backpropagation. Mình sẽ giải thích cho mọi người quá trình máy học dựa trên những khái niệm này.

 Đầu tiên, một bức ảnh sẽ được đưa vào model dự đoán của chúng ta. Model ở đây thực chất là tập hợp các Weight và bias. Khi model này nhận input là bức ảnh, nó sẽ tính toán dựa theo Score function và đưa ra được kết quả dự đoán. Kết quả dự đoán này sẽ được so sánh với kết quả thực để tính ra được độ lỗi theo loss function. Toàn bộ quá trình này là quá trình forward.
 Tiếp đến, quá trình backpropagation bắt đầu. Khởi động quá trình tính đạo hàm riêng điên loạn cho toàn bộ W và b trong model. Sau khi tính được đạo hàm riêng, gradient descent sẽ được áp vào để cập nhật các W và b. Và vòng lặp thứ nhất kết thúc.
Vòng lặp thứ 2 bắt đầu! Bức ảnh lại được đưa vào, model lại tiếp tục tính toán theo score function. Nhưng vì ở vòng lặp thứ nhất, các W và b đã được cập nhật theo gradient descent, do đó ở lần lặp này, loss function được tính ra sẽ thấp hơn loss function ở lần lặp trước. Điều này đánh dấu cho một sự kiện quan trọng của học máy: qua quá trình lặp, kết quả dự đoán đã chính xác hơn. Tiếp đến sẽ lại là quá trình backpropagation và cập nhật model. Quá trình này lặp cho đến khi nào loss đủ nhỏ mà người dùng ưng ý thì sẽ dừng hoặc sẽ dừng sau 1 số hữu hạn vòng lặp đã được lập trình.
Và đó, tất cả quá trình lặp forward và backpropagation đó, là quá trình máy học. Quá đơn giản đúng không nào!

Read More

Backpropagation

Phần backpropagation này rất nặng về toán đạo hàm nhé. Nên ai chưa có kiến thức đạo hàm riêng thì bắt buộc phải học trước đi nhé.

Ý nghĩa của đạo hàm riêng

Giả sử ta có hàm f = xy. Theo đạo hàm riêng thì ta có:

$\frac{\delta f}{\delta x}=y$ , $\frac{\delta f}{\delta y}=x$

Ví dụ với x= 4 và y =-3. Quá trình forward là quá trình tính toán theo biểu thức để ra kết quả. Tức forward ở đây là 4.-3 = -12. Lúc này, ta có đạo hàm riêng theo x = -3. Điều này có nghĩa là, nếu ta tăng giá trị của x 1 khoảng h nào đó, thì toàn bộ hàm f sẽ giảm một khoảng là -3h. Tương tự với đạo hàm riêng theo y = 4. Điều này có nghĩa, nếu ta tăng giá trị y 1 khoảng h nào đó, thì toàn bộ giá trị của f sẽ tăng 1 khoảng 4h. Như vậy, có thể hiểu:

Đạo hàm riêng của 1 biến chỉ ra được sự ảnh hướng của biến đó tới sự biến động của toàn bộ hàm số.

Các ví dụ

Giả sử ta có biểu thức: f(x,y,z)=(x+y)z. Giả sử x = -2, y = 5, z = -4. Ta có thể vẽ biểu thức như sau:

Còn quá trình backpropagation là quá trình tính đạo hàm của từng thành phần bằng cách tính ngược từ kết quả lên. Có thể thấy: q = x+ y có đạo hàm riêng là -4. Do đó, ta có thể nói rằng: nếu x hay y tăng thì q sẽ tăng, và f sẽ giảm 1 khoảng 4 lần giá trị tăng.  
Ví dụ tiếp theo cho hàm sigmoid Giả sử ta có hàm sau (gọi là hàm sigmoid):

$f(x,y)=\frac{1}{1+e^{-(w_{0}x_{0}+w_{1}x_{1}+w_{2})}}$

Ta có thể biểu diễn nó ra được như hình sau:

Quá trình tính toán forward cực kì đơn giản, bạn có thể tự tính ra được như trong hình. Mình sẽ giải thích quá trình backpropagation cho trường hợp này:
Giả sử cho kết quả output có đạo hàm = 1 cho dễ tính. Ta backward 1 bước về phép tính 1/x. Đạo hàm riêng của 1/x = -1/x^2 . Do đó ta có kết quả đạo hàm riêng tại đây là : (-1/1.37^2)*1 = -0.53. Tiếp đến ta backward 1 bước về phép tính x +1 . Đạo hàm theo x = 1. Do đó kết quả đạo hàm riêng tại đây = 1*-0.53 = -0.53. Tiếp tục backward lại 1 bước về phép tính :e^x . Ta có đạo hàm theo x của e^x = e^x. Do đó, đạo hàm riêng của x tại đây = e^-1*-0.53 = -0.2. Cứ thế, ta tính ngược cho đến input. Quá trình này chính là quá trình backpropagation.

Backpropagation và gradient descent

Quay lại với hàm score function, ta có $f(x_{i},W)=Wx_{i}$, loss function(SVM loss) $L_{i}=\sum_{j\neq y_{i}}max(0,s_{j}-s_{y_{i}}+\Delta )$. Giả sử W là tập hợp của 1 trăm triệu weight từ W1 đến W100 triệu. Và qua quá trình backpropagation của hàm L, ta có đạo hàm riêng của $\frac{\delta L}{\delta W_{69}}=-4$. Điều này có ý nghĩa là: Nếu W69 tăng 1 khoảng h, thì L sẽ giảm 1 khoảng -4h. Đúng chưa nào? Mục tiêu chúng ta đặt ra từ đầu là làm cho L giảm (loss càng thấp thì dự đoán càng chính xác).
Tiếp tục ôn bài gradient descent nè: để L giảm thì ta xài gradient descent với công thức $W_{t+1} = W_{t}-\alpha f'(W_{t})$. Với $\alpha > 0$. Áp vào cho W69, ta có : $W'_{69} = W_{69} - \alpha(-4)$. Tức là W69 sẽ tăng sau vòng lặp này, đồng nghĩa là L sẽ giảm sau vòng lặp này.
 Và bây giờ, hiệu ứng quá rõ ràng: nhờ backpropagation tính ra đạo hàm riêng cho W, mà ở bước lặp tiếp theo, W sẽ thay đổi dựa vào gradient descent. Và sự thay đổi này làm L ở vòng lặp tiếp theo giảm. Tức là sự dự đoán ở vòng lặp tiếp theo sẽ chính xác hơn!

Read More

L2 Regularization

Trong máy học, vấn đề nhức nhối bao nhiêu con người ưu tú của nhân loại là Overfitting, do đó, có rất nhiều người đêm quên ăn, ngày ăn bù để suy nghĩ làm sao để hạn chế được Overfitting. Và một ý tưởng chợt lóe ra, ý tưởng này có thể mường tượng được như sau: bạn có một model với tập hợp các parameters, parameters càng nhiều thì model càng phức tạp. Đúng chưa? mà model càng phức tạp thì overfitting càng dễ gặp. Vậy để giảm overfitting, ta cần giảm độ phức tạp model, để giảm độ phức tạp model, ta giảm số lượng parameters. Mà để giảm số lượng parameters thì ta làm sao? Ta phải cho các parameters có giá trị càng gần 0 càng tốt. Vì sao? Vì nếu càng gần 0, thì sức ảnh hưởng của parameters càng ít và gần như tiêu biến. Và đó, là cách giảm parameters.
Ý tưởng đã có, vậy làm thế nào để giảm được giá trị của W mà độ chính xác của model vẫn ngon lành. Đây là lúc L2 Regularization có tác dụng. Ví dụ với hàm Linear Classifier, ta có hàm tổng quan là :

$f(x_{i},W)=Wx_{i}$

Giả sử ta có input x = [1,1,1,1], ta có 2 W lần lượt là W1 = [1,0,0,0] và W2 = [0.25,0.25,0.25,0.25]. Cả 2 đều cho ra cùng kết quả là 1. Và vì chung kết quả từ score function nên loss function SVM cũng tính ra chung 1 kết quả theo công thức:

$L_{i}=\sum_{j\neq y_{i}}max(0,s_{j}-s_{y_{i}}+\Delta )$

Nhưng các bạn thấy, rõ ràng ở W2, các giá trị gần 0 hơn, do đó sẽ giảm được overfitting. Vậy nên người ta đã nghĩ ra cách kết hợp hàm L2 Norm có công thức như sau:

$R(W)=\sum_{k}\sum_{l}W_{k,l}^{2}$

Nhìn công thức hầm hố vậy thôi, thực ra chỉ là tổng bình phương các giá trị của W. Kết hợp với SVM loss ta có:

$L_{i}=\sum_{j\neq y_{i}}max(0,s_{j}-s_{y_{i}}+\Delta )+\lambda \sum_{k}\sum_{l}W_{k,l}^{2}$

Ta có R(W1)=1, R(W2)=0.25. Vậy nên, L2 < L1. Do đó, với hàm loss này, ta sẽ chọn L2, chính là chọn W2. Và đó, đó chính là cách L2 Regularization được áp dụng để hạn chế overfitting. Với việc lập trình, mình thấy người ta hay dùng thuật ngữ Weight decay, và weight decay cũng chính là L2 Regularization.

Read More

Optimization và Gradient Descent

Chúng ta đã tìm hiểu về score function và loss function. Giả sử score function có công thức $f(x_{i},W)=Wx_{i}$, và loss function (SVM loss) có công thức: $L_{i}=\sum_{j\neq y_{i}}max(0,s_{j}-s_{y_{i}}+\Delta )$
Mục tiêu của chúng ta là phải làm sao cho giá trị loss càng thấp càng tốt ( tức là dự đoán càng chính xác càng tốt). Trong công thức trên, $x_{i}$ và $y_{i}$ là cố định (đầu vào - đầu ra), và chỉ có W là có thể thay đổi trong mô hình. Vậy để giảm loss thì chỉ có cách đánh vào W mà thôi. Và Optimization chính là thứ giúp ta điều chỉnh được các giá trị của W để làm giảm được giá trị của loss.
 Nói suông là thế, vậy Optimization làm cách nào để điều chỉnh W giúp làm giảm loss? Sau đây là hướng tiếp cận để làm điều đó.  
Đầu tiên: Hướng tiếp cận đơn giản nhất cho Optimization là random.
Ý tưởng cực kì đơn giản. Để biết được tập W nào có loss thấp, thì ta sẽ random các tập W và tính loss dựa trên tập W đó. Sau đó ta sẽ lấy W có kết quả loss thấp nhất và dung nó để dự đoán.  
Hướng tiếp cận thứ 2 là random hướng. Ý tưởng cái này cũng đơn giản chả kém. Tưởng tượng quá trình đi tìm W là bạn đang lầm lũi bước đi trong một cái sân golf rộng lớn và uốn lượn để tìm nơi có vị trí thấp nhất.

Hướng tiếp cận thứ nhất có thể hiểu là bạn được random liên tục các vị trí trong sân golf đó. Nhưng với hướng tiếp cận thứ 2, sau khi bạn được random vị trí đầu tiên, bạn sẽ chọn đó làm vị trí gốc để tiếp tục bước đi chứ không random tiếp nữa.
Giả sử bạn lần đầu bạn được thả rơi ngay trúng sườn đồi cỏ trong sân golf, bước tiếp đến bạn sẽ random một hướng để bước. Nếu bước tiếp theo bạn có vị trí cao hơn bước hiện tại (loss cao hơn) thì bạn sẽ bỏ qua và lại random hướng. Còn nếu bước tiếp theo bạn đi có vị trí thấp hơn bước hiện tại (loss thấp hơn) thì bạn sẽ đi. Quá trình này lặp đi lặp lại đến khi nào bạn ưng ý thì thôi.  
Hướng tiếp cận thứ 3 là dựa vào độ dốc
Ý tưởng hướng tiếp cận này là chúng ta dựa vào độ dốc nơi chúng ta đang đứng, sau đó sẽ đi theo hướng có độ dốc đi xuống. Ý tưởng trực quan thì là thế, nhưng về mặt toán học để hiểu được nó, bạn phải quay về các bài học về đạo hàm. Bài này của trang machinelearningcoban giải thích rất hay và dễ hiểu về đạo hàm trên phương diện toán học. Về cơ bản, chúng ta có thể hiểu trên một cái sân gofl lớn có rất nhiều địa hình nhấp nhô uốn lượn, và do đó có rất nhiều điểm thấp trũng . Những điểm này gọi là local minimum. Trong tất cả những local minimum này, điểm có giá trị thấp nhất gọi là global minimum. Việc tìm W để Loss function có giá trị nhỏ nhất cũng như là việc tìm điểm global minimum này vậy.
Nhưng trong thực tế, rất tiếc phải nói rằng việc này rất khó có thể thực hiện được, do vậy người ta chủ yếu chỉ tìm được local minimum mà người ta ưng ý thôi.
Quay lại với toán học, với hàm f(t), tại một điểm ti bất kì, nếu ta đi theo hướng ngược với hướng của đạo hàm f'(ti) thì sẽ đạt được vị trí có giá trị thấp hơn f(ti). Đây cũng chính là cách mà người ta áp dụng vào việc tìm W cho loss nhỏ.

Gradient Descent

Gradient là dốc, descent là đi xuống. Gradient descent là đi xuống dốc, tức là đi ngược với dấu đạo hàm. Giả sử ta đang ở vị trí W, và ở bước tiếp theo ta bước đi với khoảng cách $\alpha$, ta bước theo hướng ngược đạo hàm của f(w) thì ta có vị trí đứng tiếp theo là:

$W_{t+1} = W_{t}-\alpha f'(W_{t})$

Đây là công thức gradient descent , và được lặp rất nhiều trong quá trình học của máy học.

Phân loại Gradient Descent

Dựa vào số lượng của đầu vào cho mỗi lần lặp, người ta chia gradient descent làm 3 loại:  
Batch Gradient Descent (BGD) Với BGD, thì ở mỗi lần lặp, người ta sẽ sử dụng toàn bộ tập dataset để làm input cho mô hình. Có thể các bạn sẽ thắc mắc rằng, tại sao không thấy bất kì biến nào biểu thị cho dataset input trong công thức gradient descent. Nhưng thực ra, f’(Wt) thực chất là đạo hàm của score function: $f(x_{i},W)=Wx_{i}$. Và x ở đây chính là đầu vào của dataset. Như vậy, bạn có thể hiểu BGD tức là khi x = toàn bộ training set. Nhược điểm của phương pháp này là nó sẽ làm cho quá trình tính toán rất lâu và tốn tài nguyên.
 Stochastic Gradient Descent (SGD) Ở loại này, thì mỗi lần lặp, người ta chỉ sử dụng 1 đầu vào X duy nhất. Để dễ hiểu, giả sử bạn có 1 tập dữ liệu training set với 100 tấm hình, BGD là bạn sử dụng 100 tấm đó cho mỗi lần lặp. Còn SGD là bạn chỉ sử dụng 1 tấm cho mỗi 1 lần lặp.
Mini-batch gradient descent Phương pháp này thì mỗi lần lặp, bạn sẽ chọn ra ngẫu nhiên 1 tập gồm n phần tử từ tập training set. N sẽ lớn hơn 1 và nhỏ hơn tổng số phần tử của training set. Ví dụ bạn có 100 tấm hình trong training set, n có thể là 5, 10 hay 20. Nếu n = 1 thì sẽ là SGD, còn nếu n = 100 thì sẽ là BDG.

Read More

Loss Function

Trong bài Score Function, khi nhìn vào công thức của linear classifier: $f(x_{i},W,b)=Wx_{i}+b$ ta có thể thấy được rằng: $x_{i}$ là đại lượng không thể thay đổi được (vì nó là bức hình chúng ta đưa vào). Nhưng ta có thể thay đổi được các parameters (W và b). Từ đó có ý tưởng, chúng ta sẽ thay đổi các parameters, sao cho với bức ảnh vào, hàm f sẽ cho ra được kết quả dự đoán đúng với các nhãn dán. Ví dụ với kết quả dự đoán trong bài Score Function:

Có thể thấy rằng, kết quả đúng (cat) có giá trị thấp hơn so với kết quả sai (Dog, ship). Do đó, nảy sinh một ý tưởng rằng: ta sẽ xây dựng một hàm L nào đó có khả năng đánh giá được độ chính xác của hàm f. Giả sử nếu kết quả của hàm f sai càng nhiều, thì giá trị của hàm L càng cao. Nếu hàm f dự đoán càng đúng, thì hàm L càng thấp. Và hàm L này, người ta gọi nó là Loss function (hàm độ lỗi). 

Loss function (hàm độ lỗi) là hàm có giá trị cao khi kết quả dự đoán của f tệ, và có giá trị thấp khi kết quả dự đoán của f chính xác.

Loss function thì có rất nhiều hàm định nghĩa. Nhưng dưới đây là 2 loại mình sẽ giới thiệu trong bài này:

Multiclass Support Vector Machine loss (SVM)

SVM là hàm được xây dựng sao cho các giá trị của các nhãn đúng phải lớn hơn giá trị của các nhãn sai 1 khoảng Δ nào đó. Giả sử với bức hình thứ i, chúng ta có tập pixels $x_{i}$ và nhãn dán $y_{i}$. Score function sẽ nhận giá trị $x_{i}$ và tính toán thông qua hàm $f(x_{i}, W)$ . Giả sử ta quy ước rằng giá trị của nhãn thứ j sau khi được tính toán ra là $s_{j}=f(x_{i},W)_{j}$, thì lúc này hàm SVM cho bức hình thứ I được tính bằng:

$L_{i}=\sum_{j\neq y_{i}}max(0,s_{j}-s_{y_{i}}+\Delta )$

Ví dụ dễ hiểu nhất là: chúng ta có 3 giá trị tương ứng với 3 nhãn dán , sau khi được tính toán bởi hàm f là: s=[13,−7,11]. Và nhãn đúng là nhãn đầu tiên (yi=0) . Giả sử Δ = 10. Svm loss sẽ được tính bằng: Li=max(0,−7−13+10)+max(0,11−13+10)

Ở vế đầu, giá trị là 0, vì max (0,-10) = 0. Ở vế sau, max(0,8) = 8. Vậy nên, tổng loss Li = 0+8 =8. Giá trị này có ý nghĩa độ lỗi của hàm f là 8. Và cũng đúng với tiêu chí của định nghĩa loss function: nếu kết quả f càng tệ thì L có giá trị càng cao. Nói tóm lại là, svm loss sẽ bỏ qua cho giá trị của các nhãn sai bé hơn giá trị nhãn đúng 1 khoảng Δ. Còn nếu không, nó sẽ cộng giá trị sai này vào hàm loss.

Softmax classifier

Bên cạnh SVM loss, một hàm khác được sử dụng phổ biến ko kém là Softmax. Hàm softmax được tính theo công thức:

$L_{i} = -log(\frac{e^{f_{yi}}}{\sum _{j}e^{f_{j}}})$

Nhìn thì có vẻ kinh khủng thật. Nhưng mà đi vào ví dụ thì rất dễ hiểu.

Kết quả sau khi được tính từ score function, sẽ được đưa vào hàm $e^{f_{j}}$. Sau đó mỗi giá trị sẽ được tính thành giá trị xác suất. Và cuối cùng, giá trị loss = -log(giá trị của nhãn đúng). Vậy là xong, tổng kết bài này là bạn hiểu được loss function là gì. Hai hàm svm và softmax là gì. Vậy thôi.

Read More

Score Function

Score function là gì? Đơn giản mà hiểu:

Score function là một hàm có khả năng chuyển từng pixel trên 1 bức ảnh thành các điểm tin cậy (confidence score) tương ứng với mỗi nhãn dán.

Đọc khái niệm thì có vẻ khó hiểu. Nhưng cứ đi vào ví dụ thì mọi chuyện sẽ dễ dàng hơn. Giả sử ta có 1 tập training set gồm i bức hình $x_{i}\epsilon R^{D}$, mỗi bức hình có nhãn dán tương ứng là $y_{i}$. Trong đó i ∈ 1..N và $y_{i}$ ∈ 1..K . Tức là, chúng ta có 1 tập N bức hình (D chiều) và K nhãn dán phân loại. Ví dụ dễ hiểu: với tập CIFAR-10 ta có N = 50000 , D = 32*32*3 = 3072 điểm ảnh, K =10 nhãn dán. Vậy score function lúc này là 1 hàm sexcos khả năng chuyển các điểm ảnh $R^{D}$ về thành các điểm tương ứng với nhãn dán $R^{K}$ $f:R^{D}$↦$R^{K}$

Linear Classifier (Hàm tuyến tính)

Linear classifier là hàm cơ bản nhất (theo mình nghĩ), nó được viết như sau:

$f(x_{i},W,b)=Wx_{i}+b$

Với công thức trên, giả sử ta duỗi thẳng các pixels của 1 bức hình thành 1 vector duy nhất [D*1]. Ma trận W sẽ có kích thước là [K*D], vector b có kích thước là [K*1]. W và b này là các parameters của hàm. Ví dụ trong cifar-10, $x_{i}$ chứa tất cả pixels của bức hình thứ I, được duỗi thẳng ra thành 1 vector [3072*1] , W = [10*3072], b = [10*1]. Vậy với hàm trên, đầu vào sẽ là 3072 con số, và đầu ra sẽ là 10 con số. Nhìn lại định nghĩa của Score function dùm mình: Score function nhận đầu vào là 1 bức hình (thực chất là $x_{i}$ ), đầu ra là confidence score tương ứng với nhãn dán ( hàm $f(x_{i},W,b)=Wx_{i}+b$ cho đầu ra là một vector 10 con số với trường hợp là tập Cifar-10). Cũng nhắc luôn, W là weights, b là bias. Nhưng mình thường gọi chung hết W và b là parameters.

Ví dụ cho linear classifier

Ví dụ như ở bức hình trên, giả sử bức tranh đầu vào chỉ có kích thước 2*2 pixel, ta sẽ duỗi thẳng bức hình này ra thành vector $x_{i}$=4*1. Lúc này, D = 4. Giả sử trong trường hợp này số nhãn phân loại chỉ là 3 nhãn (cat, dog,ship) thì K = 3. Như vậy W lúc này sẽ là ma trận K*D = 3*4, b là vector K*1 tức là b = 3*1. Bây giờ, để tính ra được kết quả như hình trên, yêu cầu bạn phải biết được cách nhân và cộng ma trận. Cái này sẽ liên quan đến toán đại số tuyến tính. Và cũng có 1 lưu ý luôn cho mọi người đỡ phải bỡ cmn ngỡ về sau đó là: Deep learning nói chung và series Image classification nói riêng sẽ liên quan đến toán cực kì nhiều, nên hãy chuẩn bị tinh thần trước những công thức và tính toán hack não. Sau quá trình tính toán, kết quả đầu ra sẽ là 3 giá trị tương ứng với 3 nhãn. Vì dog có giá trị cao nhất nên được chọn. Và bạn cũng thấy được đây là kết quả sai, vì cat mới là nhãn đúng. Nhưng không sao, đây chỉ là ví dụ cho bạn hiểu được khái niệm linear classifier là gì thôi.

Ghép chung W và b trong toán học

Theo như công thức linear classifier ở trên, chúng ta đã tách biệt W và b. Nhưng thông thường khi lập trình và tính toán, người ta có thể gộp chung 2 phần tử trên thành 1 ma trận chung.

$f(x_{i},W)=Wx_{i}$

Việc gộp này thực hiện như thế nào, bạn nhìn vào hình sau sẽ rõ:

b sẽ được thêm vào sau ma trận W, lúc này ma trận W = K*D+1. Còn $x_{i}$ sẽ được thêm 1 giá trị 1 vào vector để có kích thước: $x_{i}$=D+1 Ok, vậy là xong. Qua bài này chúng ta đã hiểu được khái niệm cơ bản nhất của score Function. Đầu vào là ảnh, đầu ra là dãy số tương ứng với nhãn dán.

Read More

Cross Validation

Bài này sẽ giới thiệu một khái niệm trong lĩnh vực máy học đó là Cross Validation, một phương pháp siêu phổ biến để hạn chế Overfittings trong huấn luyện mạng. Vậy Cross Validation là gì?
Chúng ta phải quay lại bài toán training model trong máy học. Như bạn đã biết, thường với một bộ dataset chúng ta sẽ có 3 tập: training set, validation set và testing set, trong đó training set dùng để huấn luyện, validation set dùng để test trong quá trình huấn luyện và testing set dùng để test cho model cuối cùng. Nhưng nếu dataset của bạn không có validation set thì sao? Bạn sẽ lấy gì để test trong quá trình huấn luyện? Chúng ta chắc chắn không được dùng testing set để kiểm thử trong huấn luyện, bởi điều này sẽ dẫn tới overfitting trên tập test. Chúng ta cũng không được dùng tập train để kiểm thử nốt, vì nó sẽ dẫn tới overfitting trên tập train. Vậy chỉ còn 1 cách, bạn sẽ lấy 1 phần của tập train ra làm tập validation. Đây cũng là 1 ý kiến hay! Nhưng, nếu tập train của bạn quá ít, việc lấy ra 1 phần của tập sẽ làm nó ít hơn và dẫn đến thiếu dữ liệu train. Điều này cũng dẫn tới overfitting. Vậy thì phải làm sao???? Đây chính là lúc bạn dùng tới Cross Validation.
Cross Validation là phương pháp chia nhỏ tập training ra thành N phần. Với mỗi lần train, mô hình sẽ sử dụng N-1 phần để train, sau đó test dựa trên 1 phần còn lại. Điều này sẽ giúp cho mô hình hạn chế gặp phải overfitting và giúp bạn tìm ra được những Hyper parameter tốt hơn. Để dễ hiểu, ta đi tới ví dụ sau. Với bộ dữ liệu CIFAR-10, bạn không hề có tập Validation.
Với phương pháp Cross Validation, bạn có thể chia nhỏ tập train ra thành 5 phần. Tổng số ảnh của tập train là 50000 ảnh => mỗi phần nhỏ sẽ có 10000 ảnh.

Với mỗi lần train đầu, bạn lấy 4 fold đầu tiên để train. Sau đó để test, bạn sử dụng fold 5 để test. Qua lần train thứ 2, bạn lấy từ fold 2 đến fold 5 để train, rồi lại lấy fold 1 để test. Và đó, chính là Cross Validation. Có thể những lý thuyết ở trên sẽ chẳng giúp bạn hiểu được vai trò của Cross Validation, thế nên chúng ta hãy thử áp dụng nó vào bài toán image classification với tập CIFAR-10 bằng thuật toán K-Nearest Neighbor.
Với thuật toán này, vấn đề đặt ra là bạn phải chọn tham số K sao cho tốt nhất bằng cách thử nghiệm. Giả sử ta chọn K = 1. Đầu tiên ta sẽ lấy fold 5 để test với tập train là từ fold 1 đến fold 4. Và kết quả cho ra được là a1% độ chính xác. Lần thứ 2 ta sẽ lấy fold 4 để test, và dùng các fold còn lại để train. Kết quả lần này cho ra a2% độ chính xác. Ta thực hiện lần lượt với 5 fold, sẽ cho ra 5 kết quả từ a1 đến a5.

Như vậy, với K=1, ta có kết quả bằng : (a1+a2+a3+a4+a5)/5. Tiếp tục thử nghiệm với các K khác, và ta tìm ra được K có kết quả tốt nhất. Từ đó có thể lấy K tốt nhất để test trên tập test mà không sợ Overfitting.

Read More

Cài đặt K-Nearest Neigbor với Python

Hi mọi người, hôm nay mình sẽ cài đặt thử thuật giải KNN với Python. Cũng như ở bài trước, chúng ta đã thử cài đặt NN với Python, mặc dù thuật toán cùi bắp nhưng vẫn có kết quả dự đoán khá ngon (38.6%). Lần này, để áp dụng KNN giải bài toán classification trên CIFAR-10 xem như thế nào. Để tìm hyperparameter K trong thuật toán này, mình sẽ xài chiến lược Cross Validation để tìm. Nhưng vì mình lười chạy thử vì đòi hỏi tài nguyên + thời gian + những suy tư trăn trở, mình mạn phép được lấy kết quả từ CS231n. Theo đó, K=7 là tối ưu dựa trên Cross Validation. Ok, vậy đã có K=7. Quá đơn giản mà không tốn nhiều công sức, chúng ta sẽ bước vào code. Sử dụng code của bài trước, ta đổi lại hàm tìm phần tử gần nhất.

def predict(self, X):   
    Ypred = np.zeros(num_test, dtype = self.ytr.dtype)    
    for i in xrange(num_test):
      print i     
      distances = np.sum(np.abs(self.Xtr - X[i,:]), axis = 1)
      k=7
      min_indexes = np.argpartition(distances, k)[:k] # vị trí k ảnh gần nhất
      yget = self.ytr[min_indexes] # yget chứa nhãn của k ảnh gần nhất
      c = Counter(yget).most_common(1) # lấy ra nhãn xuất hiện nhiều nhất trong yget
      Ypred[i] = c[0][0] # gán giá trị nhãn đó cho kết quả
    return Ypred

Lưu ý là, để chạy được hàm Counter, các bạn phải thêm thư viện vào bằng dòng code sau đây:

from collections import Counter

Sau khi để máy chạy một hồi, kết quả bạn thu được sẽ là: 37,65%. What the fuck????? Có gì đó sai sai ở đây, KNN dự đoán thua NN??? Đó là cảm giác của mình sau khi chạy xong code ở trên. Sau một hồi xem xét, thì hóa ra lỗi là ở đoạn code sau:

c = Counter(yget).most_common(1)
Ypred[i] = c[0][0]

Oái ăm là vầy, nếu như tất cả các nhãn trong yget xuất hiện phổ biến ngang nhau, thì đoạn code trên sẽ trả về nhãn có giá trị nhỏ nhất.

Như các bạn thấy, bức hình gần nhất có nhãn là "2". Nhưng đoạn code trên lại trả về nhãn "1", có thể vì nó sort hay sao đó để tìm mình cũng ko rõ, dẫn đến sai kết quả. Vì lí do này, mình có bổ sung thêm 1 số dòng code để giải.

def predict(self, X,k):
    num_test = X.shape[0]
    Ypred = np.zeros(num_test, dtype = self.ytr.dtype)
    for i in xrange(num_test):
      print i
      distances = np.sum(np.abs(self.Xtr - X[i,:]), axis = 1)      
      min_indexes = np.argpartition(distances, k)[:k] 
      yget = self.ytr[min_indexes]
      c = Counter(yget).most_common(k)
      result = c[0][0]
      if c[0][1]==1:
        k = 1
        min_indexes = np.argpartition(distances, k)[:k]
        yget = self.ytr[min_indexes]
        c = Counter(yget).most_common(k)
        result = c[0][0]
      else:
        i = 0
        while i<len(c)-1 and c[i][1]==c[i+1][1]:
          i = i+1
        if i!=0:            
          result = c[0][0]
          k2 = 1
          ind2 = np.argpartition(distances, k2)[:k2]
          yget2 = self.ytr[ind2]
          c2 = Counter(yget2).most_common(1)
          for y in range(0,i):
            if c[i][0]==c2[0][0]:
              result = c[i][0]
      Ypred[i] = result 
    return Ypred

Nhìn thì có vẻ rối, nhưng cơ bản đoạn code trên giải quyết những trường hợp sau:

Và sau khi dành thời gian để chạy thử code, kết quả ra là 38,26%. Vẫn thấp hơn NN các bạn ạ :'( Cuộc đời đúng là không biết lúc nào mới được giải thoát. Sau bao lần cài đặt và chạy thử, kết cục vẫn là một con số cùi bắp. Nhưng lý do tại sao KNN lại thấp hơn NN, mình nghĩ có 3 khả năng xảy ra ở đây: Khả năng 1: Quá trình chạy Cross Validation của CS231n đã sai. Khả năng này thì xác xuất xảy ra là 0.001%. Vì đây là bài giảng của Stanford, khó mà sai được. Khả năng 2: Code của mình sai :'( Khả năng này cũng khó xảy ra lắm. chắc tầm 20%. Khả năng 3: K=7 không tối ưu bằng K=1 trên tập test. Đây cũng là điều dễ hiểu, vì Cross Validation được thử nghiệm trên tập train chia nhỏ. Nên việc thử nghiệm trên tập test ko giống cũng có thể xảy ra. Khả năng này tầm 30-40%. Ok, mặc dù quá trình cài đặt và chạy thử không ra gì. Nhưng chúng ta ít nhất cũng đã thực hiện hóa được thuật toán KNN trên CIFAR-10. Một thành tích đáng được nhà nước và các đoàn thể tặng huân chưa. Một lần nữa, xin được vỗ tay cho thành công ngày hôm nay. Code bài này mình cũng đã up lên đây, bạn có thể lên để tải về chạy thử.

Read More

K-Nearest Neighbor

Khi đọc về thuật toán Nearest Neighbor, ai nói thuật toán đó là vớ vẩn thì bước ra đây! Mấy người đúng rồi đấy =)) Đúng là NN rất vớ vẩn, với một người không giỏi toán như mình, khi nhìn nhận NN qua xác xuất thống kê đã thấy không ổn rồi. Chẳng ai lại đoán nhãn của 1 đối tượng dựa vào duy nhất 1 đối tượng gần nó nhất. Việc này cũng như tính toán tỉ lệ úp ngửa khi thảy đồng xu, chả ai lại thảy 1 lần duy nhất là đưa ra tỉ lệ cả. Và vì lí do cùi mía này, người ta có 1 thuật toán khác gọi là: K-Nearest Neighbor (KNN) để loại bỏ đi cái sự vớ vẩn của NN. Ý tưởng của KNN thực sự rất đơn giản, thay vì dự đoán nhãn của 1 đối tượng dựa vào 1 đối tượng gần nó nhất, người ta sẽ dựa vào K đối tượng gần nó nhất. Điều này ít nhất là giúp mình thấy có chút ngon lành theo mặt xác suất thống kê ( mặc dù mình dốt toán).

K-Nearest Neighbor Classifier là phương pháp mà bạn dự đoán nhãn của 1 đối tượng dựa vào nhãn của K đối tượng gần nó nhất.

Từ định nghĩa trên, có thể dễ dàng nhận thấy: với K = 1 thì KNN thực chất là NN. Với hình dưới đây, nếu như ta dùng NN để dự đoán X, thì chắc chắn sai. Nếu đúng ra, điểm X nên nhận giá trị màu xanh, nhưng vì nó gần với điểm đỏ nên theo NN nó là màu đỏ.

 

Những điểm đỏ nằm lẫn trong các điểm xanh, người ta gọi nó là dữ liệu nhiễu. Và hầu như các bộ dataset đều có dữ liệu nhiễu, đó là lí do mà NN đạt hiệu quả thấp. Nhưng nếu ta dùng KNN cho trường hợp này với K = 5, thì kết quả sẽ có 4 đối tượng màu xanh và 1 đối tượng màu đỏ. Theo số đông, thì nhãn của X sẽ là màu xanh.

Thấy thế nào, thuật toán này ngon lành nhỉ? Nhưng không đâu bạn à, vấn đề đặt ra ở đây là: K bao nhiêu là tốt nhất. Nếu muốn tối ưu, thì ta còn phải chọn độ đo nào (Mahattan hay Euclidean). Và những tham số cần phải chọn như này, người ta gọi là Hyperparameter (tiếng việt là siêu tham số). Và để chọn siêu tham số như nào, thì chỉ còn có cách là thử nghiệm. Các phương pháp thử nghiệm thì có rất nhiều, và bạn có thể đọc phương pháp Cross Validation để có thể thử code KNN và chạy thử.

Read More

Cài đặt thuật giải Nearest Neighbor với Python

Bài này sẽ giúp các bạn chạy thử thuật giải Nearest Neighbor bằng ngôn ngữ Python. Dataset được sử dụng trong bài này là CIFAR-10, một bộ dữ liệu khá nổi tiếng cho bài toán nhận dạng hình ảnh. Nói sơ qua về dataset này, CIFAR-10 chứa 60000 bức ảnh màu có kích thước 32*32, tổng số nhãn dán là 10 nhãn. Bộ dataset được chia làm 2 phần: training set (50000 ảnh) và testing set (10000 ảnh). Những bạn nào chưa nắm được các khái niệm như training set hay testing set thì xin mời quay về đây để đọc. Để tải bộ dataset này cho ví dụ ngày hôm nay, bạn vào đây.

Trước hết, bạn phải năm được Nearest Neighbor Classifier là gì đã nhá. Và code của bài này mình cũng đã upload lên đây. Bạn có thể tải về để chạy thử. Ok, bây chừ chúng ta sẽ bắt tay vào code. Đầu tiên chúng ta sẽ import các thư viện cần thiết vào:

import numpy as np
from cs231n.data_utils import load_CIFAR10

Lưu ý cho là, hàm load_CIFAR10 là hàm dùng để load dataset CIFAR10 vào python. Hàm này được cung cấp bởi cs231n, giúp các bạn dễ dàng hơn trong quá trình lập trình. Bước tiếp đến là chúng ta sẽ load dataset vào:

Xtr, Ytr, Xte, Yte = load_CIFAR10(link to dataset folder)

Như chúng ta đã biết, máy tính hiểu một bức hình màu thực chất là 3 ma trận RGB. Với trường hợp dataset này, mỗi bức hình màu sẽ là 1 ma trận: 32*32*3. Để dễ dàng cho việc tính khoảng cách, ta sẽ chuyển ma trận trên về thành ma trận 1 chiều với 3072 phần tử.

Xtr_rows = Xtr.reshape(Xtr.shape[0], 32 * 32 * 3) # Xtr_rows becomes 50000 x 3072
Xte_rows = Xte.reshape(Xte.shape[0], 32 * 32 * 3) # Xte_rows becomes 10000 x 3072

Bây giờ ta sẽ bắt đầu code hàm NearestNeighbor:

class NearestNeighbor(object):
  def __init__(self):
    pass

  def train(self, X, y):
    """ X, Y là input và output của tập train. Trong đó, X có kích thước 50000*3072, Y là mảng 1 chiều có kích thước 50000 """
    self.Xtr = X
    self.ytr = y

  def predict(self, X):
    """ X là input của tập test. Trong đó, X có kích thước 10000*3072 """
    num_test = X.shape[0]
    # khoi tạo tập kết quả dự đoán
    Ypred = np.zeros(num_test, dtype = self.ytr.dtype)

    # lặp qua tất cả những bức ảnh trong tập test
    for i in xrange(num_test):
      print i # hiển thị vòng lặp đang thực hiện
      # tính khoảng cách của bức ảnh hiện tại so với tất cả những bức ảnh trong tập train
      distances = np.sum(np.abs(self.Xtr - X[i,:]), axis = 1)
      # tìm vị trí của bức ảnh trong tập train gần với bức ảnh test nhất
      min_index = np.argmin(distances) 
      # lấy giá trị output tương ứng gán vào tập kết quả dự đoán
      Ypred[i] = self.ytr[min_index] 
    return Ypred

num_test là kích thước của tập test, trong trường hợp này là 10000. Nhìn vào dòng code ta có thể thấy, quá trình tính toán khoảng cách đã được numpy hỗ trợ rất tốt, ta có thể dễ dàng code chỉ trong 1 dòng. Và cũng nhắc thêm, khoảng cách trong đoạn code trên là khoảng cách Mahattan nhá. Việc tiếp theo ta cần làm là gọi tất cả các hàm ta đã code ra cho nó chạy thôi.

nn = NearestNeighbor()
nn.train(Xtr_rows, Ytr)
Yte_predict = nn.predict(Xte_rows)

Cuối cùng là tính toán tỉ lệ chính xác của thuật toán Nearest Neighbor classifier trên tập dataset này.

print 'accuracy: %f' % ( np.mean(Yte_predict == Yte) )

Nếu như chạy đúng, kết quả chính xác đưa ra sẽ là : 38,6%. OK, thấy được con số này, ai nói Nearest Neighbor là thuật toán vớ vẩn thì bước ra đây. Rõ ràng kết quả này quá cao nếu so với việc bạn cho máy tính random. Tỉ lệ đoán trúng dựa vào random chỉ là 10% (vì ta có đến 10 nhãn trong tập dataset này). Nếu bạn muốn cài đặt NN với độ đo Euclidean thì hãy thay dòng code này vào để tính khoảng cách:

distances = np.sqrt(np.sum(np.square(self.Xtr - X[i,:]), axis = 1))

Kết quả dự đoán với độ đo Euclidean là 35.4%, thấp hơn độ đo Mahattan. Vậy đấy, thế là bạn đã cài đặt thành công thuật toán Nearest Neighbor Classifier trên ngôn ngữ Python. Xin cung hỉ cung hỉ vì bạn vừa làm được cái điều mà ai học lập trình cũng làm đc -_-. Qua quá trình chạy trên, chắc hẳn bạn cũng thấy quá trình lặp để đưa kết quả dự đoán rất chậm. Cũng đúng thôi, vì mỗi lần đưa ra được kết quả, máy tính phải tính khoảng cách giữa 1 bức ảnh tới 50000 bức ảnh, đây cũng chính là nhược điểm rất lớn của thuật toán này.

Read More

Nearest Neighbor Classifier

Khái niệm

Thuật toán đầu tiên mà chúng ta học là Nearest Neighbor Classifier. Tiếng việt được gọi là người láng giềng gần nhất, nhưng đôi khi cũng được gọi là người hàng xóm kế bên… Riêng mình, mình thích gọi là “NN”. Vậy NN là gì? Đơn giản mà hiểu:

Nearest Neighbor Classifier là phương pháp mà bạn dự đoán nhãn của 1 đối tượng dựa vào nhãn của đối tượng gần nó nhất.

Hơi khó hiểu phải không. Lấy ví dụ như này cho đơn giản nà. Trong một lớp có 3 thằng tên : Nam, Man, Men. Bây giờ có 1 thằng A bước vào lớp, cô giáo đố bạn tên thằng đó là gì? Khó quá phải ko? Bạn đang tính nói: “em ko biết”. Thế là cô giáo nhanh miệng đưa ra gợi ý: “Tên thằng này giống với tên của 1 trong 3 thằng còn lại”. Và bây giờ đáp án có vẻ dễ dàng hơn rồi. Bạn có thể dùng thuật toán NN để đoán bằng cách: Thằng A nó đứng gần thằng nào nhất thì tên thằng A sẽ là tên thằng đó. Và bạn thấy thằng A đứng gần thằng Nam nhất => thằng A tên Nam. Đấy, đấy chính là “người láng giềng gần nhất”. Thuật toán nghe có vẻ thiệt xàm xí đúng ko? Thực ra không phải đâu, với những bức ảnh giống nhau thì khoảng cách (Distance) được tính ra giữa 2 bức ảnh đó sẽ có giá trị thấp. Điều này dẫn tới việc áp dụng NN trong hình ảnh đạt hiệu quả rất tốt.

Cách tính khoảng cách

Như đã được hiểu ở trên, thuật toán NN là thuật toán dự đoán nhãn của một đối tượng dựa vào nhãn của đối tượng gần nó nhất. Vậy làm sao để biết 2 đối tượng gần nhau hay xa nhau. Tất nhiên, chúng ta có những độ đo riêng để đo khoảng cách của 2 đối tượng. Nhưng trong bài này, mình chỉ giới thiệu về 2 độ đo cơ bản: Manhattan, Euclidean

Manhattan Distance

Đầu tiên và đơn giản nhất là độ đo khoảng cách Manhattan. Cho 2 điểm A(x1,y1) và B(x2,y2) trong cùng một mặt phẳng. Khoảng cách Manhattan được tính bằng: Manhattan : D = |x2-x1|+|y2-y1| Tương tự với các điểm trong không gian xyz: A(x1,y1,z1) và B(x2,y2,z2) thì D = |x2-x1| + |y2-y1| + |z2-z1|. Để áp dụng manhattan cho việc tính khoảng cách giữa 2 bức hình, ta có thể tưởng tượng như sau. Với 2 bức hình đầu vào có kích thước 4*4 pixel. Khoảng cách giữa 2 bức hình là tổng khoảng cách giữa các pixel tương ứng giữa 2 bức hình. Công thức tổng quát có thể viết tương ứng như sau: d1(I1,I2)=∑p|Ip2−Ip1| Trong đó: Ip1 và Ip2 lần lượt là các điểm ảnh trên bức hình 1 và bức hình 2.

Euclidean Distance

Với 2 điểm A(x1,y1) và B(x2,y2) trong cùng một mặt phẳng. Khoảng cách Euclidean được tính bằng: Eucliean : D = √(x2 - x1)² + (y2-y1)² Tương tự với các điểm trong không gian xyz: A(x1,y1,z1) và B(x2,y2,z2) thì D = √(x2 - x1)² + (y2-y1)²+ (z2-z1)². Công thức tổng quát cho khoảng cách giữa 2 bức hình dựa trên độ đo euclidean được biểu diễn như sau: d1(I1,I2)= ∑p√(Ip2 - Ip1)² .

Read More

Giới Thiệu Series Image Classification

Hé lồ mọi người, chào mừng mọi người đến với series bài học về image classification. Loạt bài này sẽ tập trung khai thác những kĩ thuật liên quan đến nhận dạng hình ảnh, một trong những bài toán của thị giác máy tính. Toàn bộ series được viết dựa trên khóa học CS231n… đây là một khóa học cực kì hay mà mình đã từng đọc và thiết nghĩ nó sẽ rất hữu ích nếu mọi người theo dõi và thực hành khóa học này. Để học theo tài liệu của CS231, bạn có thể xem thêm tại đây. Bên cạnh việc khai thác những khung nội dung từ cs231n, mình cũng sử dụng các tài liệu khác để làm rõ hơn những thuật ngữ, khái niệm, thuật toán và kĩ thuật được đưa ra trong toàn bộ series. Mong rằng, qua toàn bộ series này, mọi người có thể hiểu và nắm bắt được một số kĩ thuật cơ bản trong image classification để có thể ứng dụng vào các công trình sau này của bản thân. Chúc mọi người học vui. Peace!

Read More

Overfitting là gì

Dẫm chân vào lĩnh vực máy học, ai cũng phải đạp qua 1 khái niệm gọi là: OverFitting (tiếng việt là : "khít quá!!!"). Vậy Overfitting là gì? Tại sao lúc nào khái niệm này cũng xuất hiện và ám ảnh người học đến thế? Bài này sẽ giúp bạn có cái nhìn tổng quát về vấn đề này. Chúng ta cùng xem xét 2 tập dữ liệu dưới đây:

 

Tập training set

Tập testing set

Nhiệm vụ của bạn bây giờ là xây dựng 1 mô hình để gán màu cho tập testing set. Thông thường, với các phương pháp máy học, mô hình sẽ được xây dựng dựa trên sự sai số khi dự đoán trên tập train. Mô hình sẽ được cập nhật với tiêu chí sao cho độ lỗi khi dự đoán càng ngày càng nhỏ dần, điều này đồng nghĩa với mô hình dự đoán càng ngày càng chính xác. Giả sử sau 1 ngày học, máy tính đưa ra được 1 đường phân chia màu cho tập training set như sau.

Bạn có thể thấy, mô hình này vẫn chưa dự đoán đúng được hết. Vẫn còn một số điểm được phân loại sai. Vậy nên, bạn quyết định cho máy học thêm 1 ngày nữa. Và kết quả thật bất ngờ, bạn có 1 đường phân chia không sai một mili nào.

Thật tự hào đúng không? độ lỗi của mô hình máy học bây giờ đã là 0% trên tập training set. Một mô hình tuyệt vời, gán màu không sai 1 điểm nào. Và bạn nghĩ chắc chắn mô hình này cũng sẽ cho kết quả thật tuyệt vời trên tập testing set. Nhưng, đời không như là mơ ( và cũng vì lí do đó nên đời hay giết chết mộng mơ). Mô hình đỉnh cao của bạn chỉ đạt 30% độ chính xác trên tập testing set. :'( Nhưng ngạc nhiên hơn, mô hình đầu tiên mà bạn có (mô hình có độ lỗi sau 1 ngày máy học) , lại cho ra kết quả gán màu chính xác 100% trên tập testing set. Thật không thể tin nổi. Tại sao lại như vây, chuyện gì đang xảy ra. Và đây là thời khắc bạn nhận ra, bạn đã dẫm phải một khái niệm có tên là Overfitting.

Overfitting là hiện tượng mô hình dự đoán quá khớp với tập training set, dẫn đến dự đoán không hiệu quả đối với tập testing set.

Ok, đó là khái niệm khái quát nhất mà khi đọc vào bạn chả hiểu gì. Vậy thì hãy xem lại 2 mô hình trên một lần nữa. Với mô hình thứ 1, mặc dù độ chính xác trên tập training set không quá tối ưu, nhưng lại đạt 100% chính xác trên tập test.

Với mô hình thứ 2, đạt tối ưu 100% trên training set và chỉ đạt 30% trên testing set.

 

Bạn đã hiểu ra rồi chứ? Vì đường phân chia quá khớp với tập train, nên khi đưa một tập khác vào để dự đoán (tập test) thì kết quả sẽ sai lệch nhiều. Và đây chính là overfitting. Vì vậy, khi bạn đưa ra 1 mô hình dự đoán với sai số 0% trên tập train, đừng tự hào vỗ ngực vội! Vì có thể một mô hình với độ sai lệch 20% trên tập train lại cho ra kết quả dự đoán trên tập test cao hơn bạn đấy!

Read More

Training set, Testing set, Validation set

Trong máy học, có một khái niệm mà tất cả chúng ta hầu như phải bắt gặp ít nhất là chục lần, đó là dataset. Dataset là tập dữ liệu mà chúng ta làm việc cùng, chính là tập dữ liệu mà chúng ta áp dụng các thuật toán AI, các mô hình máy học để thử nghiệm và đánh giá. Và thông thường, tập dataset này có kích thước rất lớn, và người ta chia nó ra làm các tập nhỏ hơn.

Training set

Đầu tiên là tập training set. Đây thường là một tập dữ liệu có kích thước lớn, được dùng để training trong quá trình huấn luyện máy học. Nôm na dễ hiểu là, đây chính là tập dữ liệu máy dùng để học và rút trích được những đặc điểm quan trọng để ghi nhớ lại. Tập training set sẽ gồm 2 phần: - Input: sẽ là những dữ liệu đầu vào. Ví dụ với bài toán nhận dạng hình ảnh chẳng hạn: input sẽ là những bức hình. - Output: sẽ là những kết quả tương ứng với tập input. Ví dụ là những nhãn dán. Nếu input là ảnh con mèo, thì output sẽ là "con mèo". Tóm cái đuôi lại:

Training set là tập các cặp input và output dùng để huấn luyện trong quá trình máy học.

Testing set

Đúng với cái tên của nó, testing set là tập dữ liệu dùng để test sau khi máy đã học xong. Một mô hình máy học sau khi được huấn luyện, sẽ cần phải được kiểm chứng xem nó có đạt hiểu quả ko. Cũng giống như con người, sau mỗi khóa học bạn phải có một bài kiểm tra cuối kì để lấy kết quả. Ai điểm cao thì có thưởng, ai điểm thấp thì nhịn chơi game... Mô hình máy học cũng vậy, sau mỗi quá trình huấn luyện gian khổ, các mô hình này sẽ được kiểm chứng độ chính xác, nếu đáp ứng được yêu cầu thì ok, không thì quăng. Và để kiểm nghiệm được độ chính xác của mô hình này, người ta dùng tập Testing set. Khác với Training set, Testing set chỉ gồm các giá trị input mà không có các giá trị output. Máy tính sẽ nhận những giá trị input này, và xử lý các giá trị, sau đó đưa ra output tương ứng cho giá trị input. Ví dụ, bạn đưa cho máy tính 1 lá bài hình con mèo : đây chính là giá trị input. Máy tính sẽ xử lý các chi tiết trên lá bài này và in ra màn hình: "con mèo" : Đây chính là output. Tóm cái váy lại:

Testing set là tập các giá trị input và được dùng để kiểm thử độ chính xác của những mô hình máy học sau khi được huấn luyện.

Validation set

Để hiểu được rõ Validation set. Bạn cần phải hiểu được 1 vấn đề trong huấn luyện mô hình máy học đó là Overfitting. Validation test cũng giống như tập training set, nó cũng bao gồm các cặp giá trị input và ouput tương ứng. Nhưng nó lại khác training set ở chỗ, nó được sử dụng để kiểm thử độ chính xác của mô hình máy học trong quá trình huấn luyện. Vậy nó khác gì với tập Testing? Cũng rất dễ nhận thấy đó là: Testing được dùng để kiểm thử sau quá trình huấn luyện, còn validation set được sử dụng để kiểm thử trong quá trình huấn luyện. Vậy tại sao người ta lại không dùng Training set để kiểm thử luôn, mà lại phải có tập validation để kiểm thử. Câu hỏi này để trả lời được, xin mời thí chủ hãy quay về Overfitting để đọc. Hiểu nôm na là vầy: hãy xem quá trình học máy là quá trình một học sinh đi học toán ở trường. Những bài tập được làm ở trường là training set. Trong quá trình học ở trường, giáo viên sẽ đưa ra những bài kiểm tra 15', để xem học sinh này yếu chỗ nào, mạnh chỗ nào để sửa chữa cách dạy. Và tất nhiên, để tránh việc học vẹt, những bài kiểm tra 15' này phải khác với những bài tập đã được làm (đây chính là Validation). Cuối kì, học sinh này được tham gia kì thi cuối kì để xét xem có được lên lớp ko hay ở lại. Bài kiểm tra cuối kì này, chính xác là Testing set. Tóm cái quần lại

Validation set là tập các giá trị input đi kèm với giá trị output và được dùng để kiểm thử độc chính xác của mô hình máy học trong quá trình huấn luyện.

Read More

Phân lớp hình ảnh

Định nghĩa image classification

Đầu tiên, Classification ở đây là gì? Hiểu 1 cách đơn giản, classification là bạn sẽ gán nhãn cho 1 đối tượng. Ví dụ cho dễ hiểu nhá: bạn có 1 bộ bài chứa hình ảnh của những con vật. Bạn rút ra 1 lá bài có hình con mèo, classification là bạn phải viết chữ “mèo” lên lá bài đó. Tức là bạn đang phân loại cho từng lá bài với những cái tên tương ứng. Nghe quá là đơn giản luôn. Nhưng đó là với con người! Còn với máy tính, làm sao để máy có thể nhìn và hiểu con bài đó mà gán cho nó cái nhãn “mèo”, đây là một vấn đề cực lớn chứ ko phải dễ ăn.

Bây giờ vào định nghĩa sâu hơn cho bài toán classification: classification là gán nhãn. Vậy mấy cái nhãn này lấy từ đâu ra? Thực ra, đối với mỗi bài toán classification, chúng ta cần phải xác định trước tập hữu hạn các nhãn dán có thể có. Ví dụ như với bộ bài vừa rồi, tập nhãn dán của chúng ta là hữu hạn tên các con vật. Và kết quả của classification phải là 1 nhãn trong tập những nhãn dán đã có đó. Vậy thôi, ko có gì quá cao siêu và xa vời cả. ( thực ra đào sâu vào khái niệm thì nó cao siêu và xa vời thật, nhưng những kẻ tay mơ như mình và số ít các bạn đang đọc thì nhiêu trên là quá đủ ).

Cuối cùng, image classification là gì? Rất đơn giản, là classification trên tập các dữ liệu dạng ảnh.

Thách thức của bài toán classification

Với con người, để gán nhãn cho 1 đối tượng, thì những đứa nhóc tầm 5-6 tuổi có thể thực hiện dễ quá rồi. Lí do là con người trong suốt quá trình phát triển đã tự học hỏi và trau dồi đươc kiến thức. Còn máy tính lại khác, đưa vào 1 bức hình và ra lệnh cho nó dán nhãn cho bức hình thì ko hề dễ. Tới với ví dụ dán nhãn con mèo. Chúng ta có một mô hình classification trên máy tính, với tập nhãn dán được định nghĩa là: {mèo, chó , trâu, heo} . Bây giờ ta đưa vào 1 bức hình con mèo có kích thước 248*400 px, máy tính sẽ hiểu nó là 1 ma trận số 3*248*400, tức là 297,600 con số.

 

Giải thích cho ma trận số này một chút nếu bạn nào chưa hiểu. Bức ảnh 248*400px thực chất là 1 ma trận 2 chiều 248*400 điểm ảnh. Mỗi điểm ảnh thực chất là sự kết hợp của 3 giá trị RGB (mã màu red green blue).

Do đó, bức ảnh dưới con mắt của máy tính là 1 ma trận số 3*248*400. Và qua 297,600 con số này, máy tính sẽ tính toán thông qua mô hình classification và đưa ra được kết quả đại loại nhu sau: 82% mèo, 15% chó, 2% trâu và 1% heo. Và kết quả này có nghĩa là nhãn dán của bức hình trên rất có thể là “con mèo” . Vậy đấy, đó là quá trình nhận dạng hình ảnh của máy tính. Vậy thì bài toán này có thách thức gì? Tất nhiên là một đống thứ kể ko hết, cơ mà hầu hết liên quan tới sự đa dạng của tập hình ảnh: như là hướng chiếu khác nhau, độ phân giải khác nhau, màu sắc đa dạng, background phức tạp khiến khó xác định được chủ thể, sư đa dạng của đối tượng (như mèo ta, mèo tây, mèo lé, mèo què),…….

Vậy làm sao để giải quyết được bài toán kinh cmn khủng này?

Bạn còn nhớ những thuật toán đỉnh cao được học trước đây chứ? Interchange sort, buble sort.. rồi mấy thuật toán đẳng cấp như quick sort. Nhưng, cái đó khó có thể áp dụng được vào lĩnh vực này. Ở những bài toán này, phương thức tiếp cận đó là: “Máy học”. Vậy máy học là gì thì bạn có thể về đây để xem lại. Nôm na là: bạn có 1 tập dữ liệu ban đầu bao gồm input và output tương ứng với input đó, máy sẽ học như một con người, sau đó bạn chỉ cần đưa 1 cái input vào là máy nó trả lời cho bạn output ngon lành.

Read More