Sự khác biệt giữa một vấn đề tuyến tính và một vấn đề phi tuyến tính? Bản chất của Dot-Product và Kernel trick

Question

Thủ thuật hạt nhân ánh xạ một vấn đề phi tuyến tính vào một vấn đề tuyến tính.

Câu hỏi của tôi là:
1. Sự khác biệt chính giữa vấn đề tuyến tính và phi tuyến tính là gì? Trực giác đằng sau sự khác biệt của hai loại vấn đề này là gì? Và làm thế nào để hạt nhân lừa giúp sử dụng các bộ phân loại tuyến tính trên một vấn đề phi tuyến tính?
2. Tại sao sản phẩm dấu chấm lại quan trọng trong hai trường hợp?

Cảm ơn.

Answer 1

Nhiều phân loại, trong số đó là tuyến tính Support Vector Machine (SVM), chỉ có thể giải quyết các sự cố có thể phân tách tuyến tính, tức là các điểm thuộc loại 1 có thể được tách ra khỏi các điểm thuộc lớp 2 bằng siêu kết nối.

Trong nhiều trường hợp, một vấn đề không tách rời tuyến tính có thể được giải quyết bằng cách áp dụng biến đổi phi() cho các điểm dữ liệu; biến đổi này được cho là biến đổi các điểm thành không gian tính năng . Hy vọng là, trong không gian tính năng, các điểm sẽ được tách biệt tuyến tính. (Lưu ý: Đây chưa phải là mẹo hạt nhân ... hãy chú ý theo dõi.)

Có thể chỉ ra rằng, kích thước của không gian tính năng càng cao thì số lượng sự cố có thể phân tách tuyến tính trong không gian đó càng lớn. Do đó, một lý tưởng sẽ muốn không gian tính năng trở nên cao nhất có thể.

Thật không may, vì kích thước của không gian tính năng tăng lên, do đó, số lượng tính toán được yêu cầu. Nhiều thuật toán học máy (trong số đó là SVM) có thể được xây dựng theo cách mà hoạt động duy nhất chúng thực hiện trên các điểm dữ liệu là một sản phẩm vô hướng giữa hai điểm dữ liệu. (. Tôi sẽ biểu thị một sản phẩm vô hướng giữa x1 và x2 bởi <x1, x2>)

Nếu chúng ta chuyển đổi điểm của chúng tôi để đặc trưng không gian, các sản phẩm vô hướng bây giờ trông như thế này:

<phi(x1), phi(x2)>

Sự thấu hiểu mấu chốt là tồn tại một lớp chức năng được gọi là hạt nhân có thể được sử dụng để tối ưu hóa tính toán của sản phẩm vô hướng này. Một hạt nhân là một hàm K(x1, x2) có những tài sản mà

K(x1, x2) = <phi(x1), phi(x2)>

đối với một số chức năng phi(). Nói cách khác: Chúng ta có thể đánh giá sản phẩm vô hướng trong không gian dữ liệu chiều thấp (nơi x1 và x2 "sống") mà không phải chuyển sang không gian tính năng chiều cao (nơi phi (x1) và phi (x2) "sống ") - nhưng chúng tôi vẫn nhận được lợi ích của việc chuyển đổi sang không gian tính năng chiều cao. Đây được gọi là thủ thuật hạt nhân .

Nhiều hạt nhân phổ biến, chẳng hạn như Gaussian kernel, thực sự tương ứng với biến phi() biến đổi thành không gian tính năng infinte-chiều. Thủ thuật hạt nhân cho phép chúng tôi tính toán các sản phẩm vô hướng trong không gian này mà không cần phải đại diện cho các điểm trong không gian này một cách rõ ràng (điều này rõ ràng là không thể đối với các máy tính có số lượng bộ nhớ hữu hạn).

Answer 2

1. Phương trình tuyến tính là đồng nhất và áp dụng chồng chất. Bạn có thể tạo các giải pháp bằng cách sử dụng các kết hợp của các giải pháp đã biết khác; đây là một trong những lý do tại sao biến đổi Fourier hoạt động rất tốt. Các phương trình phi tuyến tính không đồng nhất và chồng chất không áp dụng. Các phương trình phi tuyến tính thường phải được giải quyết bằng cách sử dụng các kỹ thuật lặp đi lặp lại, tăng dần.
2. Tôi không chắc chắn cách thể hiện tầm quan trọng của sản phẩm chấm, nhưng phải mất hai vectơ và trả về một vô hướng. Chắc chắn một giải pháp cho một phương trình vô hướng là ít công việc hơn là giải quyết một vector hoặc phương trình tensor bậc cao hơn, đơn giản chỉ vì có ít thành phần để xử lý.

Trực giác của tôi trong vấn đề này dựa trên vật lý, vì vậy tôi gặp khó khăn khi dịch AI.

Answer 3

Sự khác biệt chính (cho mục đích thực tế) là: Một vấn đề tuyến tính hoặc có một giải pháp (và sau đó nó dễ dàng tìm thấy), hoặc bạn nhận được một câu trả lời rõ ràng rằng không có giải pháp nào cả. Bạn biết điều này nhiều, trước khi bạn thậm chí còn biết vấn đề. Miễn là nó tuyến tính, bạn sẽ nhận được một câu trả lời; Mau.

Trực giác là một thực tế là nếu bạn có hai đường thẳng trong một số không gian, nó khá dễ dàng để xem liệu họ giao nhau hay không, và nếu họ làm, thật dễ dàng để biết ở đâu.

Nếu vấn đề không phải là tuyến tính - tốt, nó có thể là bất cứ điều gì, và bạn biết chỉ là về không có gì.

Sản phẩm chấm của hai vectơ chỉ có nghĩa như sau: Tổng của các sản phẩm của các phần tử tương ứng. Vì vậy, nếu vấn đề của bạn là

c1 * x1 + c2 * x2 + c3 * x3 = 0 

(nơi bạn thường biết các hệ số c, và bạn đang tìm kiếm các biến x), phía bên tay trái là dấu chấm sản phẩm của các vectơ (c1,c2,c3) và (x1,x2,x3).

Phương trình trên là (khá nhiều) độ chính xác của một vấn đề tuyến tính, do đó, có kết nối của bạn giữa các vấn đề về sản phẩm chấm và tuyến tính.

Answer 4

Khi mọi người nói vấn đề tuyến tính liên quan đến vấn đề phân loại, họ thường có nghĩa là vấn đề có thể phân tách tuyến tính. Chia tách tuyến tính có nghĩa là có một số hàm có thể tách riêng hai lớp là kết hợp tuyến tính của biến đầu vào. Ví dụ, nếu bạn có hai biến đầu vào, x1 và x2, có một số số theta1 và theta2 sao cho hàm theta1.x1 + theta2.x2 sẽ đủ để dự đoán đầu ra. Trong hai kích thước này tương ứng với một đường thẳng, trong 3D nó trở thành một mặt phẳng và trong không gian chiều cao hơn nó trở thành một thủy phi cơ .

Bạn có thể nhận được một số loại trực giác về các khái niệm này bằng cách suy nghĩ về các điểm và đường thẳng trong 2D/3D. Dưới đây là một cặp rất giả tạo của ví dụ ...

Đây là một âm mưu của một vấn đề tuyến tính không thể tách rời. Không có đường thẳng có thể tách các điểm màu đỏ và màu xanh.

Tuy nhiên, nếu chúng ta cung cấp cho mỗi điểm thêm tọa độ (đặc biệt 1 - sqrt(x*x + y*y) ...Tôi đã nói với bạn nó đã được giả tạo), sau đó vấn đề trở nên tách biệt tuyến tính vì các điểm màu đỏ và màu xanh có thể được phân cách bằng một mặt phẳng 2 chiều đi qua z=0.

Hy vọng rằng, những ví dụ chứng minh một phần của ý tưởng đằng sau các trick kernel:

Lập bản đồ một vấn đề thành một không gian với một số lượng lớn kích thước làm cho nó nhiều khả năng rằng vấn đề sẽ trở thành tuyến tính tách.

Ý tưởng thứ hai đằng sau mẹo hạt nhân (và lý do tại sao nó rất khó) là nó thường rất khó xử và tính toán đắt tiền để làm việc trong một không gian rất cao. Tuy nhiên, nếu thuật toán chỉ sử dụng các sản phẩm chấm giữa các điểm (bạn có thể nghĩ là khoảng cách), thì bạn chỉ phải làm việc với ma trận vô hướng. Bạn hoàn toàn có thể thực hiện các phép tính trong không gian cao hơn mà không bao giờ thực sự phải lập bản đồ hoặc xử lý dữ liệu chiều cao.

Answer 5

Tôi nghĩ rằng sau liên kết cũng rất hữu ích ...
http://www.simafore.com/blog/bid/113227/How-support-vector-machines-use-kernel-functions-to-classify-data