Explain Normal Equation matrix formula

I’m just learning the Machine Learning course of Andrew Ng on coursera , and at the Normal Equation lesson I encountered a matrix formula to compute regression coefficients \Theta without the explanation of how to come up with that.

There are some blogs on the Internet prove this formula in very detail and I just want to share an easy way to explain as well as to memorize the formula that is efficiently and handy.

So we have matrix X as the design matrix, and Y is the output vector of size (m+1). We want to find\Theta matrix so that:

$latex X \Theta = Y$

All we want to do is isolating \Theta in the left side (just like we always do to isolate x when solving a equation). And to do that, we want to “bring” what multiply by \Theta to the right side, and we can do that only when “what” is a square matrix (make sense right ?).

So now X is not a square matrix yet, we will multiply X by its transpose matrix, which is $latex X^{T}$. Now we have:

$latex X^{T}X\Theta = X^{T}Y$

Now X^{T}X is a square matrix, we can “bring” it to the right side:

\Theta = (X^{T}X)^{-1}X^{T}Y

And that’s it !

 

Advertisements

Sự khác nhau giữa Population và Sample

Lấy ví dụ: chiều cao trung bình ở nam giới, đây là một Population vì nó bao gồm tất cả những người đàn ông ở cả quá khứ (đã chết), hiện tại (đang sống) và tương lai (được sinh ra). Căn bản là chúng ta không thể tiến hành khảo sát trên toàn bộ Population vì không thể đo được chiều cao của tất cả đàn ông được (ví dụ như những người nam chưa được sinh ra). Thậm chí nếu có thể, thì cũng sẽ mất rất nhiều thời gian và tiên bạc. Ở ví dụ trên, chúng ta có một Population là “nam giới”, và thông số cần khảo sát là “chiều cao” của họ.

Thay vì vậy, chúng ta có thể tiến hành đo (thống kê) chiều cao của một tập con những nam giới – gọi là Sample (mẫu) – và từ đó suy luận kết quả của toàn bộ Population. Gọi là suy luận vì việc có những số liệu không ổn định và không chính xác là điều khó tránh khỏi trong việc có được kết quả của Population chỉ dựa trên một Sample của nó. Điều này là hiển nhiên vì số phần tử trong Sample ít hơn số phần tử trong Population, nên sẽ có mất mát thông tin.

Nói tóm lại:
Sample là một nhóm các thực thể tham gia vào việc khảo sát của bạn (có trong dữ liệu của bạn)
Population là một nhóm các thực thể lớn hơn, mà kết quả của nó sẽ được suy luận từ kết quả của Sample.

Có nhiều phương pháp để chọn một Sample và môn học nghiên cứu về nó được gọi là Sampling Theory (lý thuyết lấy mẫu). Một phương pháp hay được dùng là Simple Random Sampling (SRS). Trong SRS, mỗi phần tử của Population đều có xác suất được chọn vào một Sample như nhau (cho nên mới có từ Random). Có nhiều phương pháp lấy mẫu khác như Stratified Sampling, Cluster Sampling… mỗi cái đều có ưu và nhược riêng.

Cần lưu ý rằng Sample mà chúng ta lấy ra từ Population chỉ là một trong một tập lớn các Sample tiềm năng. Nếu 10 nhà nghiên cứu cùng khảo sát trên một Population, việc dùng các Sample khác nhau có thể sẽ thu được kết quả khác nhau. Quay trở lại ví dụ ban đầu, mỗi nhà nghiên cứu kết thúc với một chiều cao nam giới khác nhau, tức là việc thống kê chiều cao thay đổi theo từng Sample, sự phân phối này gọi là Sampling Distribution. Chúng ta có thể dùng phân phối này để hiểu về tính bất định trong ước đoán về thông số của Population.

Tham khảo và dịch từ: https://stats.stackexchange.com/questions/269/what-is-the-difference-between-a-population-and-a-sample

Classic problems

“Classic” ở đây với nghĩa là những bài có phát biểu ngắn gọn và có thể ứng dụng trong các bài toán lớn khác

Updated 6/4/2017

Lưu ý: 
+ Substring / Subarray là dãy con liên tục 
+ Subsequence là dãy con có thể không liên tục

Dãy số

– Tìm Subsequence dài nhất của dãy số (LIS – Longest Increasing Subsequence) O(NlogN): code mẫu

String

– So khớp chuỗi KMP O(N+M): code mẫu , bài tập

– Tìm Subsequence chung dài nhất của 2 xâu/dãy (LCS – Longest Common Subsequence ) O(N*M) : bài tập

– Tìm số bước biến đổi (delete, add, replace) ít nhất để biến xâu này thành xâu kia (String Alignment, Edit Distance) O(N*M)  : bài tập

Palindrome

– Tìm Palindrome Subsequence dài nhất trong một xâu O(N*N): bài tập

– Thêm vào cuối xâu S ít kí tự nhất để được xâu Palindrome O(N): bài tập

– Thêm vào xâu S ít kí tự nhất để được xâu Palindrome O(N*N): bài tập

– Biến đổi xâu S (delete, insert, replace) ít thao tác nhất để được xâu Palindrome O(N*N) : bài tập

– Đếm số Palindrome Subsequence trong xâu S O(N*N): bài tập

Suffix Array

– Tìm Substring dài nhất xuất hiện ít nhất 2 lần trong 1 xâu O(Nlog^2N): bài tập

– Tìm Substring chung dài nhất của 2 xâu (LCS – Longest Common Substring) O(Nlog^2N): bài tập

– Tìm Substring chung dài nhất của M xâu trong N xâu cho trước (M <= N)

Graph

– Kiểm tra xem một đồ thị  liên thông vô hướng có phải là một Clique hay không: E = V*(V-1)/2: bài tập

– Tìm thứ tự topo của một đồ thị có hướng không chu trình (DAG)

– Tìm tất cả thứ tự topo của một đồ thị có hướng không chu trình (DAG)

[NTUCoder] Capxach – Cặp xách

Đề bài: http://laptrinh.ntu.edu.vn/Problem/Details/5568

Lời giải:
+ Thực ra bài này không khó nhưng mình vẫn mắc phải cái lỗi sơ đẳng nên cứ note lại vậy
+ Quy hoạch động f[x] là số cách chọn để có được khối lượng x, khởi tạo f[0] = 1, implement với 2 vòng for đơn giản
+ Chú ý:
=> Nếu dể vòng for khối lượng ở ngoài, vòng for cặp xách ở trong sẽ cho kết quả sai do bị trùng cách chọn cặp xách
=> Cách viết đúng phải là vòng for cặp xách ở ngoài, for khối lượng ở trong => như vậy việc xây dựng f[x] tại thời điểm cặp xách thứ i sẽ chỉ phụ thuộc vào cặp xách j <= i => không bị trùng cách chọn

Writing some Embedded System stuffs

All the devices and systems you’re seeing in this picture are the meaningful results of an industry that mark a milestone in turning technology world to a whole new level – Embedded Systems

On one hand, this science has a huge potential in leading human to a convenient lifestyle by integrating the operating system and source code into many devices, so that it can be manipulated with more functions than before. For example over the past few years, we were observing the release of Smart Watch & Google Glass, that slightly change the way we normally use them, now you can send email, listen to music and even measure your heartbeat with only one single watch !

On the other hand, Embedded Systems has also an enormous influence to various sectors from daily life like having a robot to do your housework; to relief operations, counter terrorism operations, for example a soldier can command an auto-driving car to save people from dangerous places.

The word “Embedded” somehow denote the relationship between software and hardware, and the question is how to achieve a high performance in such machines that has very limited space for the software-part. And it’s time Assembly comes to place to adapt all those criteria. This language allows programs to be compiled and executed more quickly due to its low-level property.

When it comes to processors in Embedded System, there are very many kind of them on market like MIPS, x86, PIC, 8051 … but I would like to focus on ARM processor. ARM occupies the superiority over others processors and is preferred because of its saving energy feature. It is also the core of the processor architecture of many renowned devices ..

Next we are going to find out the structure of ARM as well as how it operates, plz welcome…