Posted in Khác

Linear Regression – Hồi quy tuyến tính

  1.  Linear Regression

Trong thống kê , chúng ta sử dụng hai cái tên khác nhau cho nhiệm vụ nối một số input features thành một số giá trị output : chúng ta sử dụng từ Regression khi output là giá trị thực , và Classification khi output là một trong tập rời rạc các classes . Linear Regression là một trong những kĩ thuật cơ bản và quan trọng để dự đoán giá trị cho một attribute(y) .

Ý tưởng của Linear Regression là chúng ta sẽ được cho một tập các observations , mỗi observations sẽ được liên kết tới một vài features , chúng ta sẽ muốn dự đoán giá trị thực cho mỗi observations . Một ví dụ nổi tiếng về dự đoán giá nhà (Levitt and Dubner (2005)) chỉ ra rằng những từ được sử dụng trong những quảng cáo bất động sản có thể là một dự đoán tốt xem một ngôi nhà sẽ được bán với giá cao hơn hay ít hơn so với giá chào bán của nó . Họ chỉ ra rằng , ví dụ , một ngôi nhà  được quảng cáo bất động sản có những từ như fantastic , cute , hoặc charming , thường có xu hướng bán với giá thấp hơn , trong khi những ngôi nhà có quảng cáo có những từ như maple granite thường bán với giá cao hơn . Giả thuyết của họ là các môi giới sử dụng các từ tích cực mơ hồ như fantastic để che giấu những sự thiếu hụt những định lượng tích cực trong ngôi nhà .

Một vài dữ liệu chúng ta tự tạo ra :

Số các tính từ mơ hồ Giá bán được cao hơn giá mời chào
4 0
3 $1000
2 $1500
2 $6000
1 $14000
0 $18000

 

Hình dưới mô tả các điểm dữ liệu trong dữ liệu tự tạo của chúng ta , với số các tính từ mơ hồ trong trục x , và giá trong trục y . Chúng ta sẽ vẽ được một regression line , mà có thể phù hợp tốt nhất với dữ liệu chúng ta quan sát được .

1

Với Linear regression một biến như ví dụ trên , chúng ta có thể tìm một phương trình có dạng

price = w0 + w1 * Num_Adjectives

Khi có nhiều hơn một feature , được gọi là multiple linear regression . Ví dụ , giá một ngôi nhà có thể phụ thuộc vào rất nhiều các yếu tố như số ngồi nhà chưa bán trong thị trường , tỷ lệ thế chấp trung bình . Chúng ta có thể coi những yếu tố này là một biến , độ quan trọng các yếu tố sẽ là weight của nó

price = w0 + w1 * Num_Adjectives + w2 * Mortgage_Rate + w3* Num_Unsold_Houses

Trong xử lý ngôn ngữ tự nhiên , chúng ta thường gọi các yếu tố dự đoán như số tính từ mơ hồ là các feature . Chúng ta sẽ biểu diễn mỗi observation( mỗi một ngôi nhà để bán) bằng một vector của những features này . Giả sử một ngôi nhà có một tính từ mơ hồ trong quảng cáo của nó , và tỷ lệ thế chấp trung bình là 6.5 và có 10,000 ngôi nhà chưa bán trong thành phố . Như thế feature vector cho ngôi nhà này sẽ là f = (1,6.5,10000) . Giả sử chúng ta sẽ học được weight vector là w =(w0,w1,w2,w3) = (18000,-5000,-3000,-1.8) . Như thế giá trị dự đoán cho ngôi nhà này sẽ tính bằng cách nhân các giá trị feature với weight của nó :

2

Thông thường , chúng ta sẽ giả vờ như là sẽ có thêm một feature mang giá trị 1 , gọi là Intercept feature , khi đó chúng ta có thể biểu diễn linear regression dự đoán cho y sẽ là :

3         2 . Quá trình học của linear regression

Làm sao để học ra các trọng số weights cho linear regression . Bằng trực giác , chúng ta sẽ mong muốn chọn được các weights sao cho giá trị y ước lượng sẽ gần nhất với giá trị thực tế chúng ta nhìn thấy trong tập training set .

Chúng ta có thể sử dụng sum squared cost function , định nghĩa như sau :

4

Chúng ta sẽ chọn tập weights tối ưu để làm cho sum-squared error nhỏ nhất . Sum Squared error cost function là một lựa chọn có lý do , và nó hoạt động tốt trong hầu hết các vấn đền , cho hầu hết bài toán regression . Có những cost functions khác hoạt động cũng tốt , nhưng sum squared error cost function là một trong những cost function sử dụng nhiều nhất cho bài toán regression [5]

Nếu chúng ta cho tất cả tập dữ liệu huấn luyện vào một ma trận X , với mỗi hàng trong ma trận sẽ là vector features ứng với observations x(i) (nên nhớ cột 1 của ma trận X sẽ mang giá trị 1 bởi vì chúng ta đã giả sử extra value bên trên) , và chúng ta sẽ cho hết các giá trị y vào  vector y . Như thế chúng ta sẽ tính ra được W bằng công thức :

5

 Ngoài Normal equation trên để tìm ra regression line , chúng ta có thể sử dụng gradrient descent . Đây cũng là một thuật toán thông dụng và không chỉ sử dụng trong linear regression [5] . So sánh giữa Gragient Descent và Normal Equation để tìm ra regression line

6

Nếu XT X không thể có nghịch đảo (khi det(XT X)=0)  , chúng ta sẽ xem xét các feature , xem các feature có phụ thuộc vào nhau không : Vì dụ có 1 feature là size in feet , 1 feature là size in meters squared , như thế 2 feature này sẽ không độc lập với nhau . Việc của chúng ta là sẽ xoá đi 1 features .

  • .Một vài vấn đề trong linear regression
    • Linear regression for classification [6]

7Scaling input features

3 . Thực thi

Chúng ta biết rằng , có thể tính W bằng công thức bên trên

8

Như vậy chúng ta sẽ đi xây dựng các phép toán trên ma trận : Nhân ma trận , chuyển vị ma trận , nghịch đảo ma trận

Object matrix

9

Class các phép toán với Matrix

Nhân hai ma trận

10

Chuyển vị ma trận

11

Nghịch đảo ma trận

Định nghĩa : Một ma trận nghịch đảo của ma trận vuông A là

A-1 sao cho A . A-1 = I

Công thức ma trận chuyển vị :

A-1 = 1/detA * adj(A^T)

12

Có thể thấy nếu det A = 0 thì không tồn tại ma trận nghịch đảo

Ta có thể tính định thức bằng quy nạp

* Nếu n = 1 Þ a = (a) Þ detA = a.

* Nếu n > 1 thì:

delA = (-1)i+1ai1|Ai1| + (-1)i+2ai2|Ai2| + … + (-1)i+jaij|Aij|+… + (-1)i+nain|Ain|.

Tức là ta tính định thức bằng cách khai triển theo dòng thứ i.

Trong đó:

* (-1)i+jaij|Aij| là phần bù đại số của aij.

* (-1)i+j  là dấu chỉ số của phần tử ở dòng i cột j.

* aij là phần tử ở dòng i cột j.

* |Aij| là định thức con được lập bằng cách bỏ dòng i cột j.

Tuy nhiên : + Một định thức cấp 3 ta khai triển được 3 định thức cấp 2.

+ Một định thức cấp 4 ta khai triển được 4 định thức cấp 3.

Như vậy: một định thức cấp n ta khai triển được (n!)/2 định thức cấp 2.

Nếu n>10 việc tính toán định thức rất chậm , dẫn đến việc tính toán ma trận nghịch đảo cũng thế

Chúng ta sẽ tìm hiểu một phương pháp có độ phức tạp  O(n^2.3) để tìm ma trận nghịch đảo của một ma trận vuông .

LU Decompostion

            Các ma trận vuông có thể được phân rã thành tích của một ma trận lower triangular và một ma trận upper triangular matrix U

A = L U

Ví dụ ma trận A 3*3

13

Chúng ta sẽ có 9 phương trình với 12 ẩn . Để phương trình có nghiệm duy nhất , chúng ta sẽ set các phần tử trên đường chéo của L là 1

14

Như thế chúng ta sẽ giải hệ phương trình 9 ẩn ,9 phương trình

15

Như thế thì :

16

17

Chúng ta có thể tổng quát hoá công thức U và L như sau

18

19

Thuật toán giả mã phân tích A thành L và U

 

 

lu

Giả sử chúng ta phân tích được A = L . U

Như thế det A = det L . det U

Mà hàng chéo của L = 1 nên det A = det U = tích hàng chéo của U

Nếu u jj  = 0 sẽ dẫn tới det U = 0 = det A => không có ma trận nghịch đảo

Giả sử ta có thể phân tích được A = L . U

với L : Lower triangular matrix

U : Upper triangular matrix

 

Capture3.JPG

Ví dụ : Sử dụng LU decompostion để tìm nghịch đảo của ma trận A

20

Chúng ta có thể tính ra được ma trận L với U như sau

21

Ta sẽ đi giải phương trình : L Z = I

Với cột 1 của Z và I

22

Sẽ cho ta phương trình :

23

Ta sử dụng thuật toán “forward substitution” từ phương trình đầu đến cuối sẽ ra

24

Như thế có thể viết được thuật toán forward substitution giải Phương trình L z = i

Capture

Cột 1 của Z sẽ là :

25

Giờ đi giải phương trình U   = Z

Với cột 1 của Z :

26

 

Thuật toán backward substitution sẽ bắt đầu từ phương trình thứ 3 ngược về :

27

28

Như thế , chúng ta có thể viết được thuật toán back substitution giải phương trình U x = d

 

Capture1

Như thế cột đầu tiên của nghịch đảo của A sẽ là :

29

Tương tự , giải các phương trình

30

31

Như thế :

32

Chúng ta có thể xác nhận lại bằng cách :

33

Sau khi viết được hàm tính toàn L, U từ A . Rồi từ  L , U tính toán nghịch đảo
Ta có thể tính được W 1 cách dễ dàng :

4. Đánh giá

  • Mean absolute error ( MAE)

MAE là đại lượng dùng để meansure độ gần của dự đoán với giá trị outcomes thực tế . Công thức của MAE như sau : [4]

36

Trong đó ,  là giá trị dự đoán và  là giá trị thực tế

  • . Root Mean Squared Error ( RMSE )

Căn của trung bình tổng các lỗi bình phương [3]

37

Tham khảo :
[1] Steven Chapra and Raymond Canale, Numerical Methods for Engineers, Fourth Edition, McGraw-

Hill, 2002 (see Sections 10.1-10.2).

[2] Jurafsky and Martin , Speech And Language Processing , Second Edition ,  2007 (Chapter 6 – Hidden Markov and maximum entropy models)

[3] http://statweb.stanford.edu/~susan/courses/s60/split/node60.html

[4] https://en.wikipedia.org/wiki/Mean_absolute_error

[5] Machine Learning , Andrew NG

[6] Machine Learning , Caltech

Câu hỏi

  1. Những dự án mà công ty mình có dùng regression , các feature chọn ra như thế nào , định lượng ra sao , kết quả thực tế như thế nào ?
  2. Với những feature hay dữ liệu không phải dạng số . Có cách nào có thể chuyển được sang số để dùng linear regression như dữ liệu ví dụ dưới đâyzz.png
  3. Với việc làm việc với vector , việc scaling dữ liệu luôn luôn cần thiết ?
Advertisements

Trả lời

Mời bạn điền thông tin vào ô dưới đây hoặc kích vào một biểu tượng để đăng nhập:

WordPress.com Logo

Bạn đang bình luận bằng tài khoản WordPress.com Đăng xuất / Thay đổi )

Twitter picture

Bạn đang bình luận bằng tài khoản Twitter Đăng xuất / Thay đổi )

Facebook photo

Bạn đang bình luận bằng tài khoản Facebook Đăng xuất / Thay đổi )

Google+ photo

Bạn đang bình luận bằng tài khoản Google+ Đăng xuất / Thay đổi )

Connecting to %s