May hoc

Xin hãy Đợi
Tổng Quan Về Máy Học
NHÓM THỰC HIỆN
-------O------

Nguyễn Đức Tiên

Giáo viên hướng dẫn:
Thầy : Đào Mạnh Hà

Môn Máy Học
1
Ầ
P
H
N
Vì dữ liệu rèn luyện thường hạn chế, nên thường khái quát hóa theo một số khía cạnh nào đó (heuristic) => tính thiên lệch quy nạp (inductive bias)
Có ba tiếp cận học:
Các phương pháp học dựa trên ký hiệu (symbol-based): ID3
Tiếp cận kết nối: Các mạng neuron sinh học
Tiếp cận di truyền hay tiến hóa: giải thuật genetic

II.Các Phương pháp học (Thuật toán):
Máy tính học thuật toán được tổ chức vào một phân loại tư duy dựa trên các kết quả mong muốn của thuật toán. Phổ biến các loại bao gồm các thuật toán.
A. Học có Giám sát:
Là một kỹ thuật máy tính học tập cho việc học một chức năng tạo từ các dữ liệu. Việc tạo bao gồm các dữ liệu của cặp đầu vào đối tượng (thường vectors), và mong muốn kết quả đầu ra. Các sản phẩm của các chức năng có thể là một giá trị liên tục (gọi là regression), hoặc có thể dự đoán một lớp học của các nhãn hiệu đầu vào đối tượng (được gọi là phân loại). Về công việc của các học viên được giám sát để dự đoán giá trị của các hoạt động hợp lệ đối với bất kỳ dữ liệu vào đối tượng sau khi nhìn thấy một số ví dụ điển hình (tức là cặp đầu vào và đầu ra mục tiêu). Để đạt được điều này, người học có thể generalize từ các dữ liệu để trình bày trong một tình huống unseen "hợp lý" cách nào (xem inductive bias). (So sánh với unsupervised học tập.) Những công việc song song trong tâm lý con người và động vật thường được gọi tắt là khái niệm học tập.

Học có giám sát có thể tạo ra các mô hình của hai loại. Hầu hết các thông thường, giám sát học tập toàn cầu, tạo ra một mô hình mà các bản đồ đầu vào đối tượng để mong muốn kết quả đầu ra. Trong một số trường hợp, tuy nhiên, bản đồ được thực hiện như là một tập hợp các mô hình địa phương (chẳng hạn như trong trường hợp dựa trên lý do hoặc các thuật toán láng giềng gần nhất).
Để giải quyết một vấn đề giám sát học tập (ví dụ như học tập để nhận biết viết tay) đã có một để xem xét các bước sau:
1. Xác định các loại hình đào tạo các ví dụ. Trước khi làm bất cứ điều gì khác, các kỹ sư sẽ quyết định những loại dữ liệu được sử dụng như là một ví dụ. Ví dụ, điều này có thể là một ký tự tay, toàn bộ một tay từ ngữ, hoặc toàn bộ một dòng viết tay.
2. Tập trung đào tạo một thiết lập. Công tác đào tạo thiết lập cần phải được đặc tính của các thực trên thế giới sử dụng các chức năng. Vì vậy, một bộ dữ liệu vào các đối tượng được tập hợp và kết quả đầu ra tương ứng cũng được tập hợp, hoặc từ các chuyên gia của con người hoặc từ đo lường
3. Xác định các dữ liệu vào chức năng đại diện của các học chức năng. Tính chính xác của các học chức năng phụ thuộc mạnh mẽ về cách thức các dữ liệu vào đối tượng là đại diện. Thông thường, các dữ liệu vào đối tượng được chuyển thể thành một tính năng véc tơ, trong đó có một số tính năng được mô tả của đối tượng. Số lượng các tính năng không nên quá lớn, bởi vì các curse của đa chiều, nhưng cần phải đủ lớn để dự đoán một cách chính xác sản lượng.
4. Xác định cấu trúc của các học chức năng và thuật toán tương ứng. Ví dụ, các kỹ sư có thể chọn để sử dụng mạng neural nhân tạo, quyết định cây.
5. Hoàn thành việc thiết kế. Các kỹ sư sau đó chạy thuật toán trên tập trung đào tạo thiết lập. Các tham số của thuật toán học có thể được điều chỉnh bằng cách tối ưu hóa hiệu suất trên một nhóm (gọi là xác nhận thiết lập) của công tác đào tạo thiết lập, hoặc thông qua cross-xác nhận. Sau khi điều chỉnh các tham số và học tập, hiệu quả hoạt động của các thuật toán có thể được đo lường trên một thử nghiệm được thiết lập riêng biệt từ việc đào tạo thiết lập.

Một thuật ngữ cho các giám sát học tập được phân loại. Một loạt các Classifiers có sẵn, đều có những mặt mạnh và yếu kém. Classifier hiệu suất phụ thuộc rất nhiều vào các đặc tính của dữ liệu sẽ được phân loại. Không có một classifier rằng hoạt động tốt nhất trên tất cả các vấn đề đưa ra; này cũng được gọi tắt là `Không có bữa ăn trưa miễn phí theorem`. Empirical các xét nghiệm khác nhau đã được thực hiện để so sánh hiệu suất tốt hơn và classifier để tìm kiếm các đặc tính của dữ liệu mà xác định classifier hiệu suất. Xác định một classifier thích hợp cho một vấn đề tuy nhiên vẫn còn nhiều hơn là một nghệ thuật là một khoa học.
Được sử dụng rộng rãi nhất là các Classifiers Mạng Neural (Multi-layer Perceptron), Hỗ trợ Vector máy, k-gần Neighbors, Gaussian mixture Model, Gaussian, Naive Bayes, cây quyết định và RBF Classifiers
6. Mpirical nguy cơ minimization
Mục đích của việc giám sát toàn cầu học tập của một mô hình là để tìm thấy một chức năng g, cho một bộ số điểm của các hình thức (x, g (x)).
Đó là giả định rằng các bộ số điểm mà các hành vi ứng xử của g được gọi là một cách độc lập và identically-phân phối ngẫu nhiên các biến mẫu kéo theo một xác suất phân phối không rõ p lớn hơn, có thể infinite, dân số. Hơn nữa, một trong những giả định sự tồn tại của một công việc cụ thể bị mất chức năng của loại L



Y là nơi codomain của g và L nonnegative bản đồ vào các con số thực tế (giới hạn hơn nữa có thể được đặt trên L). Số lượng L (z, y) là phải gánh chịu thiệt hại của z như dự đoán giá trị của g tại một điểm khi thật sự có giá trị là y.
Những rủi ro liên quan đến một hàm f sau đó sẽ có định nghĩa là những kỳ vọng của các tổn thất chức năng, như sau:  

nếu phân phối xác suất p là Discrete (analogous liên tục các trường hợp sử dụng một bộ definite mật độ xác suất và một chức năng).
Mục đích là ngay bây giờ để tìm thấy một hàm f * cố định giữa các subclass của các chức năng mà các rủi ro R (f *) là tối thiểu.
Tuy nhiên, từ khi có hành vi ứng xử của g thường chỉ được biết finite cho một tập hợp các điểm (x1, y1), ..., (x­­n , yn), một trong những chỉ có thể gần đúng thật sự rủi ro, ví dụ như với các nguy cơ empirical:
Chọn chức năng f * rằng minimizes empirical những rủi ro được gọi là nguyên tắc empirical nguy cơ minimization. Thống kê học tập lý thuyết tra dưới những điều kiện empirical nguy cơ minimization là admissible và làm thế nào để tốt cho approximations .
Trong đó các thuật toán tạo ra một chức năng mà các bản đồ đầu vào để mong muốn kết quả đầu ra. Một trong những tiêu chuẩn xây dựng các công việc giám sát học tập là vấn đề phân loại: người học là cần thiết để tìm hiểu (vào khoảng) các hành vi của một chức năng mà một bản đồ vectorơ vào một trong một lớp học bằng cách xem một số đầu vào-đầu ra ví dụ về các chức năng.
B. Học ko giám sát
(unsupervised learning)
Trong máy tính học tập, unsupervised học tập của lớp học là một vấn đề mà trong đó một trong những việc làm thế nào để xác định xem các dữ liệu được tổ chức. Nó được phân biệt giám sát việc học (reinforcement và học tập) trong đó người học được dành cho chỉ unlabeled ví dụ. Unsupervised học tập là có liên quan chặt chẽ đến vấn đề về mật độ trong dự toán số liệu thống kê. Tuy nhiên unsupervised học tập cũng bao gồm nhiều kỹ thuật khác mà tìm cách tóm tắt và giải thích các tính năng quan trọng của dữ liệu.


Một trong những hình thức học tập là unsupervised clustering. Một ví dụ khác là mù mã nguồn tách dựa trên phần phân tích độc lập (ICA).
Trong số các mô hình mạng neural, thì tự bản đồ Tổ chức (SOM) và Adaptive resonance lý thuyết (ART) thường được dùng unsupervised học thuật toán. Các topographic SOM là một tổ chức mà trong đó các địa điểm gần đó trong bản đồ đại diện cho đầu vào tương tự với tài sản. Các mô hình cho phép ART số cụm với các vấn đề khác nhau tùy vào kích thước và cho phép người sử dụng kiểm soát mức độ tương tự giữa các thành viên trong cùng một cụm phương tiện của một người dùng xác định việc được gọi là các tham số Vigilance. ART mạng cũng được sử dụng cho nhiều mô hình công nhận nhiệm vụ, mục tiêu tự động, chẳng hạn như công nhận và xử lý tín hiệu seismic. Các phiên bản đầu tiên đã được ART "ART1", phát triển của Carpenter và Grossberg (1988).
Một đại lý mà các mô hình một tập hợp các yếu tố đầu vào: dán nhãn các ví dụ là không có.
C. Bán giám sát việc học
(Semi-supervised learning ).
Trong khoa học máy tính, bán giám sát học tập là một loại máy móc kỹ thuật học tập mà làm cho việc sử dụng cả hai nhãn unlabeled và dữ liệu cho đào tạo - thường là một lượng nhỏ dữ liệu có nhãn với một số lượng lớn unlabeled dữ liệu. Semi-giám sát học tập té ngã giữa unsupervised học tập (không có bất kỳ nhãn dữ liệu đào tạo) và giám sát việc học (có đào tạo hoàn toàn dữ liệu có nhãn). Nhiều máy móc-học tập nghiên cứu đã phát hiện thấy rằng unlabeled dữ liệu, khi được sử dụng trong kết hợp với một lượng nhỏ có nhãn dữ liệu, sản xuất có thể cải thiện đáng kể trong việc học chính xác. Việc mua lại nhãn dữ liệu cho một vấn đề học tập thường xuyên đòi hỏi phải có tay nghề của con người đại diện, để tự phân loại các ví dụ đào tạo. Các chi phí có liên quan đến việc xử lý nhãn hiệu như vậy, tháng năm vẽ lại một cách đầy đủ nhãn infeasible đặt đào tạo, trong khi mua unlabeled dữ liệu tương đối rẻ tiền. Trong tình huống như vậy, bán có thể được giám sát việc học của những giá trị thực tế.


Một ví dụ của một bán giám sát học tập kỹ thuật là đồng đào tạo, trong đó hai hoặc nhiều hơn có thể học được huấn luyện mỗi ngày một bộ các ví dụ điển hình, nhưng với mỗi học bằng cách sử dụng khác nhau, và lý tưởng độc lập, tập hợp các tính năng cho mỗi ví dụ.
Một cách khác là phương pháp tiếp cận các mô hình phân phối xác suất chung của các tính năng và nhãn hiệu. Đối với các nhãn unlabelled dữ liệu có thể được coi là `thiếu dữ liệu`. Nó được phổ biến để sử dụng thuật toán EM để tối đa hóa khả năng mô hình.
Kết hợp cả hai nhãn unlabeled và các ví dụ để tạo ra một chức năng thích hợp hoặc classifier.
D. Reinforcement học.
Lấy cảm hứng của tâm lý có liên quan đến lý thuyết, về khoa học máy tính, reinforcement học tập là một tiểu khu vực của máy tính có liên quan học tập như thế nào với một đại lý nên hành động trong một môi trường để tăng tối đa của một số notion dài hạn thưởng. Reinforcement học thuật toán cố gắng tìm một chính sách mà các bản đồ tiểu bang trên thế giới đến các hành động của đại lý nên để ở những tiểu bang. Trong kinh tế và lý thuyết trò chơi, reinforcement học tập được coi là boundedly rational giải thích về cách equilibrium .


Các môi trường thường được xây dựng như là một finite Markov-nhà nước, quyết định xử lý (MDP), và các thuật toán reinforcement học tập cho các bối cảnh này là rất cao có liên quan đến năng động, chương trình kỹ thuật. Nhà nước và chuyển đổi probabilities thưởng probabilities trong MDP thường stochastic nhưng stationary qua khóa học của vấn đề.
Reinforcement học khác nhau từ các giám sát trong vấn đề học tập mà đúng đầu vào / đầu ra cặp sẽ không bao giờ được trình bày, và cũng không phụ tối ưu rõ ràng các hành động sửa chữa. Ngoài ra, còn có tập trung vào on-line hiệu quả hoạt động, trong đó bao gồm việc tìm kiếm một sự cân bằng giữa khai thác (của uncharted lãnh thổ) và khai thác (của kiến thức hiện tại). Các thăm dò khai thác thương mại vs-off reinforcement trong học tập đã được nghiên cứu chủ yếu là thông qua nhiều vấn đề vũ trang bandit.


Chính thức, cơ bản reinforcement học tập mô hình,
như áp dụng cho MDPs, bao gồm:
1. một bộ các môi trường tiểu bang S;
2. một bộ các hành động Đáp A; và
3. một bộ scalar "phần thưởng" trong .
Tại mỗi thời gian t, các đại lý nhận các nhà nước và các bộ có thể có các hành động Đáp A(st). Nó chọn một hành động và nhận được từ môi trường mới, nhà nước,
st + 1 và một phần thưởng rt + 1. Dựa trên những tương tác, học tập reinforcement các đại lý phải phát triển một chính sách mà tôi đa cho số lượng cho MDPs đó có một terminal của tiểu bang, hay số lượng .
R =∑γrtt

t
MDPs cho các tiểu bang mà không có terminal (là nơi mà một số "trong tương lai thưởng" chiết khấu yếu tố).
Vì vậy, reinforcement học tập tốt, đặc biệt là phù hợp với vấn đề đó bao gồm một thời gian dài so với ngắn hạn thưởng thương mại-off. Nó đã được áp dụng thành công vào các vấn đề khác nhau, bao gồm cả robot điều khiển, thang máy lên lịch, viễn thông, và cờ backgammon .
E. Transduction
( sự truyền tính trạng)
Trong logic, thống kê inference, giám sát và học tập, transduction hoặc transductive inference là lý do từ quan sát, cụ thể (đào tạo) cho các trường hợp cụ thể (kiểm tra) trường hợp. Ngược lại, induction là lý do quan sát từ đào tạo cho các trường hợp quy định chung chung, mà sau đó được áp dụng cho trường hợp kiểm tra. Sự khác biệt thú vị nhất là trong trường hợp dự đoán của các mô hình transductive không có bất kỳ inductive thành công của mô hình. Lưu ý rằng việc này là do transductive inference đặt ra những thử nghiệm khác nhau trên cùng không nhất quán, sản xuất dự báo.
Transduction đã được giới thiệu của Vladimir Vapnik trong 1990`s, động cơ của mình xem là thích rằng transduction để induction từ, theo ông, induction đòi hỏi phải giải quyết một vấn đề tổng quát hơn (inferring một chức năng) trước khi giải quyết một vấn đề cụ thể hơn (tính toán kết quả đầu ra cho các trường hợp mới ): "Khi giải quyết một vấn đề quan tâm, không được giải quyết một vấn đề chung chung như là một bước trung. Hãy thử để có được câu trả lời rằng bạn thực sự cần thiết, nhưng không phải là một tổng quát hơn một."


Ví dụ về học tập mà không phải là inductive sẽ là trong trường hợp phân loại nhị phân, nơi mà các yếu tố đầu vào có xu hướng cụm trong hai nhóm. Đáp lớn tập hợp các bài kiểm tra đầu vào có thể giúp tìm các cụm, thì cung cấp thông tin hữu ích về việc phân loại các nhãn. Cùng dự đoán sẽ không có obtainable từ một mô hình mà induces một chức năng chỉ dựa trên việc đào tạo các trường hợp. Một số người có thể gọi đây là một ví dụ về sự liên quan đến bán giám sát việc học, từ Vapnik của động lực là hơi khác nhau. Ví dụ về một thuật toán trong thể loại này là Transductive Hỗ trợ Vector Machine (TSVM).


Một động lực thứ ba mà có thể dẫn đến transduction phát sinh thông qua việc cần phải gần đúng. Nếu chính xác inference là computationally prohibitive, ta có thể ít nhất là cố gắng để đảm bảo rằng các approximations tốt ở bài kiểm tra đầu vào. Trong trường hợp này, các bài kiểm tra đầu vào có thể đến từ một arbitrary phân phối (không nhất thiết phải liên quan đến việc phân phối của các yếu tố đầu vào đào tạo), trong đó sẽ không được cho phép trong bán giám sát học tập. Ví dụ về một thuật toán té ngã trong thể loại này là Ủy ban Bayesian máy (BCM). tương tự như giám sát việc học, nhưng hiện không rõ ràng xây dựng một chức năng: thay thế, cố gắng để dự đoán kết quả đầu ra mới dựa trên các yếu tố đầu vào đào tạo, đào tạo kết quả đầu ra, và đó là bài kiểm tra đầu vào có sẵn trong khi đào tạo
F. Học để biết
(Nhiều công việc học tập):
Nhiều công việc học tập là một cách tiếp cận với máy tính học tập, mà học cùng với một vấn đề khác liên quan đến các vấn đề tại cùng một thời gian, chia sẻ bằng cách sử dụng một đại diện. Điều này thường dẫn đến một mô hình tốt hơn cho các nhiệm vụ chính, vì nó cho phép người học sử dụng commonality một trong những nhiệm vụ được giao. Vì vậy, nhiều công việc học tập là một loại inductive chuyển.
- máy tính học tập lý thuyết
Các máy tính phân tích của máy tính học thuật toán và hiệu suất của chúng là một chi nhánh của lý thuyết khoa học máy tính được gọi là máy tính học tập lý thuyết. Bởi vì đào tạo được đặt ra những finite và tương lai là bấp bênh, học tập lý thuyết thường không đảm bảo năng suất tuyệt đối của hiệu suất của thuật toán. Thay vào đó, probabilistic bounds trên hiệu quả hoạt động khá phổ biến.
Ngoài hiệu suất bounds, máy tính học tập theorists thời gian học tập phức tạp và khả thi của việc học. Trong máy tính học tập lý thuyết, một tính toán được xem là khả thi, nếu nó có thể được thực hiện trong thời gian polynomial. Có hai loại thời gian kết quả phức tạp. Hiển thị các kết quả tích cực đó, một lớp học của một số chức năng có thể được học trong thời gian polynomial. Phủ định kết quả cho thấy một số lớp học có thể không được học trong thời gian polynomial.
- trong đó có những thuật toán học inductive bias riêng của mình dựa trên kinh nghiệm trước đó.
Các máy tính phân tích của máy tính học thuật toán và hiệu suất của chúng là một chi nhánh của lý thuyết khoa học máy tính được gọi là máy tính học tập lý thuyết. Bởi vì đào tạo được đặt ra những finite và tương lai là bấp bênh, học tập lý thuyết thường không đảm bảo năng suất tuyệt đối của hiệu suất của thuật toán. Thay vào đó, probabilistic bounds trên hiệu quả hoạt động khá phổ biến.


PHẦN 2
PHẦN 2
PHẦN 2
ĐỊNH NGHĨA VỀ CÂY ĐỊNH DANH :
Cây định danh là cây mà nếu ta đi từ nút gốc đến các lá ta sẽ có một quyết định hay một quy luật dựa vào các thuộc tính trên đường đi từ gốc đến lá, như vậy mỗi đường đi từ nút gốc đến nút lá sẽ cho ra một quyết định hay một quy luật. Vì vậy người ta còn gọi cây định danh là cây quyết định.
Ví dụ 1: Dữ liệu của một bảng quan sát gồm 4 thuộc tính của con người như sau: