# Trí tuệ nhân tạo

## Bài 1: Giới thiệu
### 1. Định nghĩa AI:
- Tư duy như con người
- Tư duy hợp lý
- Hành vi như con người
- Hành vi hợp lý
- Một số năng lực điển hình:
- Học từ kinh nghiệm và áp dụng tri thức.
- Xử lý tình huống phức tạp
- Xác định và trích chọn các đặc trưng quan trọng của các đối tượng, sự kiện, quá trình
- Xử lý và thao tác ký hiệu
- Sáng tạo, có trí tưởng tượng
- Sử dụng heuristic
### 2. Turing test:
- Natural language process:
- Knowledge representation:
- Automated reasoning:
-
- Vision (for total Turing test):
- Motor control (total test):
- Other senses (total test): edition, smell, touch, ...

### 3. Thinking Humanly: Cognitive Science (Khoa học nhận thức)
### 4. Branches of AI:
- Logical AI
- Search
- Natural language processing
- Pattern recognition
- Knowledge representation
- Inference
- Automated reasoning
- Machine Learning
- Planning
- Epistemology (Nhận thức luận)
- Ontology: Study of the kinds of things that exist
- Genetic programming
- GeoSpatial

## Bài 2: Giải quyết vấn đề bằng tìm kiếm:

### 1. Giới thiệu:
- Bài toán: Có 3 thùng 3l, 5l, 9l, cần đổ 7l

- Các thành phần của bài toán tìm kiếm:
- Trạng thái bắt đầu, khởi tạo
- Các hành động: Đi thẳng, rẽ, ...
- Mô hình chuyển tiếp: Khi thực hiện các hành động thì các trạng thái cũng thay đổi
- Trạng thái kết thúc, đích
- Trọng số, chi phí đường đi.
- 
- Giải pháp tối ưu: Tổng chi phí nhỏ nhất

- Ví dụ: Romania
- 

- Không gian trạng thái:
- Tất cả các trạng thái có thể đạt được từ trạng thái bắt đầu từ mô hình chuyển đổi
- Có thể được biểu diễn dưới dạng đồ thi có hướng
- Cây tìm kiếm
- 
- Kiểm soát trạng thái lặp

- Cách tìm một giải pháp:
- Giải pháp: Chuỗi các hành động từ trạng thái hiện tại đến trạng thái đích.
- Chiến lược tìm kiếm: Được xác định theo thứ tự mở rộng của các nút
- Thuật toán chung: 
- Cài đặt thuật toán tìm kiếm:
- 

- Tiêu chí đánh giá:
- Độ hoàn chỉnh (Completeness): Có thể tìm được lời giải nếu nó tồn tại?
- Độ phức tạp về thời gian (Time complexity): Số lượng các trạng thái đã đến
- Độ phức tạp về không gian (Space complexity): Số lượng các trạng thái tối đa phải lưu trong bộ nhớ
- Độ tối ưu (Optimality): Có phải lúc nào cũng tìm ra nghiệm có chi phí nhỏ nhất không?
- Các tham số để tính độ phức tạp về không gian và thời gian:
- **b**: maximum branching factor of the search tree (số trạng thái kề)
- **d**: depth of the least-cost solution (độ sâu của trạng thái kết thúc)
- **m**: maximum depth of the state space (may be ∞)(độ sâu lớn nhất)

### 2. Các chiến lược tìm kiếm mù
#### a. Tìm kiếm theo chiều rộng: BFS
- Ý tưởng:
- Tại mỗi bước, chọn trạng thái để phát triển là trạng thái được sinh ra trước các trạng thái chờ phát triển khác
- Nói một cách khác, chúng ta sẽ quét cây tìm kiếm theo từng lớp tính từ gốc trở đi
- Đỉnh mới được sinh ra sẽ được lưu vào một danh sách tổ chức theo kiểu “hàng đợi” (**queue FIFO**)
- Mô tả thuật toán:
- 
- Tiêu chí đánh giá:
- Độ hoàn thành: Có, nếu **b** hữu hạn
- Độ phức tạp về thời gian: $1 + b^1 + b^2+...+b^d=O(b^d)$
- Độ phức tạp về không gian: $O(b^d)$
- Độ tối ưu: Có (giả sử rằng mỗi bước có chi phí là 1)
#### b. Tìm kiếm theo chiều sâu: DFS
- Ý tưởng:
- Tại mỗi bước, chọn trạng thái để phát triển là trạng thái được sinh ra sau cùng trong các trạng thái chờ phát triển
- Nói một cách khác, chúng ta sẽ quét cây tìm kiếm theo từng nhánh tính từ gốc trở đi
- Tương tự như thuật toán tìm kiếm chiều rộng chỉ khác là sử dụng một danh sách theo kiểu “ngăn xếp” (**stack LIFO**) chứ không phải theo kiểu “hàng đợi”.
- Mô tả thuật toán:
- 
- Tiêu chi đánh giá:
- Độ hoàn thành: Có nếu như có hữu hạn các trạng thái.
- Độ phức tạp về thời gian: $O(b^m)$
- Độ phức tạp về không gian: $O(bm)$
- Độ tối ưu: Không
- Tránh các trạng thái lặp: Đánh dấu các trạng thái đã thăm trước đó.
- Ví dụ về biểu diễn thuật toán BFS, DFS:
- 

#### c. Tìm kiếm theo chiều sâu có giới hạn (Depth-limited search):
- Ý tưởng: DFS với chiều sâu tối đa **l**
- Cài đặt: Các nút ở độ sâu **l** không có kế thừa
- Độ hoàn thành: Nếu điểm cắt được chọn phù hợp thì đảm bảo sẽ tìm ra giải pháp.
- Độ tối ưu: Không đảm bảo tìm được giải pháp có chi phí thấp nhất.

#### d. Tìm kiếm theo chiều sâu lặp (Iterative deepening search):
- Ý tưởng: Kết hợp tốt nhất các chiến lược tìm kiếm theo chiều rộng và chiều sâu.
- Mô tả thuật toán:
- 
- Tiêu chi đánh giá:
- Độ hoàn thành: Có.
- Độ phức tạp về thời gian: $O(b^d)$
- Độ phức tạp về không gian: $O(bd)$
- Độ tối ưu: Có, nếu mỗi bước có chi phí là 1
#### e. Tìm kiếm chi phí đều/cực tiểu (Uniform-cost search):
- Đối với mỗi nút ở đầu hàng đợi (queue), lưu chi phí đường đi từ nút bắt đầu đến nút đó.
- Mở rộng đường đi với nút ở đầu hàng đợi mà có chi phí thấp nhất.
- Cài đặt: Dùng priority_queue
- Tương đương với chiều rộng đầu tiên nếu chi phí bước đều bằng nhau
- Tương đương với thuật toán Dijkstra nói chung
- Tính chất:
- Độ hoàn thành: Có, nếu chi phí của mỗi bước lớn hơn 1 số nguyên dương không đổi $ε$
- Độ tối ưu: Có, các nút được mở rộng theo chi phí đường đi tăng dần
- Thời gian:
- Số nút có chi phí đường đi $≤$ chi phí của giải pháp tối ưu (C*) $O(b^{C*/ε})$
- Giá trị này có thể lớn hơn $O(b^d)$: tìm kiếm có thể khám phá các đường dẫn dài bao gồm các bước nhỏ trước khi khám phá các đường dẫn ngắn hơn bao gồm các bước lớn hơn
- Không gian: $O(b^{C*/ε})$
- Biểu diễn thuật toán: 
- So sánh các thuật toán tìm kiếm mù: 

## Bài 3: Chiến lược tìm kiếm kinh nghiệm

### 1. Tổng quan:
- Phương pháp tìm kiếm mù có khả năng thám hiểm không gian trang thái để tìm ra trạng thái đích, tuy nhiên nó rất là không hiệu quả trong hầu hết bài toán
- Với sự trợ giúp của kinh nghiệm, trí thức đặc trưng của vấn đề, phương pháp tìm kiệm kinh nghiệm rất là hiệu quả
- Là phương pháp mà sử dụng hàm đánh giá cung cấp trí thức đặc trưng về bài toán để hướng dẫn sự tìm kiếm

### 2. Hàm đánh giá (Heuristic function):
- Heuristic function h(n): Chi phí ước tính để đến đích từ nút n
- Ví dụ:
- 
- Từ một vị trí, không biết bản đồ xung quanh, hãy đến điểm cao nhất trong khu vực – **hàm đánh giá chính là độ cao tại mỗi điểm**
- Tìm đường trên phố để đến được tòa nhà cao nhất thành phố - hàm đánh giá là **khoảng cách từ mỗi điểm theo đường chim bay đến tòa nhà**
- Nhận xét:
- Có thể có nhiều cách đánh giá
- Các hàm đánh giá có thể không phải hàm tối ưu
- Cách chọn hàm đánh giá quyết định rất nhiều kết quả của các kỹ thuật tìm kiếm kinh nghiệm

### 3. Tìm kiếm kinh nghiệm:
- Các giai đoạn:
- Tìm biểu diễn thích hợp mô tả các trạng thái và các toán tử của vấn đề
- Xây dựng hàm đánh giá
- Thiết kế chiến lược chọn trạng thái để phát triển ở mỗi bước
- Có một lớp các thuật toán tìm kiếm tốt nhất đầu tiên (Best First Search) sử dụng các hàm đánh giá khác nhau

#### a. Tìm kiếm tốt nhất đầu tiên:
- Tìm kiếm tốt nhất đầu tiên = Tìm kiếm bề rộng + Hàm đánh giá
- Khác với tìm kiếm theo chiều rộng, tìm kiếm tốt nhất đầu tiên chọn đỉnh để phát triển là đỉnh tốt nhất được xác định bởi hàm đánh giá
- Đỉnh tốt nhất là đỉnh có giá trị hàm đánh giá là nhỏ nhất, đỉnh này có thể ở mức hiện tại hoặc ở các mức trên
- Mô tả:
- 
- Tính chất:
- Độ hoàn thành: Có, nếu không gian trạng thái là hữu hạn với kiểm tra trạng thái trùng lặp
- Thời gian: $O(b^m)$
- Không gian: $O(b^m)$
- Độ tối ưu: Không
- Một hàm đánh giá tốt có thể giảm thời gian và không gian nhớ một cách đánh kể

#### b. Beam search:
- Tương tự như tìm kiếm tốt nhất đầu tiên
- Tuy nhiên chỉ phát triển k đỉnh ở mức tiếp theo chứ không phát triển toàn bộ
- Ưu điểm: độ phức tạp tính toán tốt hơn
- Nhược điểm: không tìm kiếm toàn bộ, nên có thể không tìm thấy đỉnh tối ưu nhất

#### c. Tìm kiếm leo đồi (Hill-climbing Search):
- Tìm kiếm leo đồi = tìm kiếm theo độ sâu + hàm đánh giá
- Khác với tìm kiếm theo độ sâu, ta phát triển một đỉnh u thì bước tiếp theo, ta chọn trong số các đỉnh con của u, đỉnh có nhiều hứa hẹn nhất để phát triển
- Đỉnh hứa hẹn nhất là đỉnh có hàm đánh giá nhỏ nhất
- Mô tả:
- 

#### d. Tìm kiếm A* (A* Search):
- Thuật toán A* sử dụng hàm đánh giá f(n) = g(n) + h(n)
- g(n): chi phí thực tế từ điểm xuất phát đến nút n.
- h(n): chi phí ước tính của đường đi có chi phí rẻ nhất từ n đến đích.
- f(n): tổng chi phí ước tính của giải pháp rẻ nhất đi qua n.
- Tìm kiếm tốt nhất đầu tiên chọn h(n) nhỏ nhất
- Hiệu quả nhưng không tối ưu
- Tìm kiếm Uniform-cost chọn g(n) nhỏ nhất
- Tối ưu nhưng không hiệu quả
- Tìm kiếm A* là làm cho f(n) = g(n) + h(n) nhỏ nhất.
- Ý tưởng: duy trì hiệu quả của Tìm kiếm Tham lam nhưng tránh mở rộng con đường vốn đã tốn kém.
- Câu hỏi: Tìm kiếm A* có tối ưu và hoàn thành không?
- Trả lời: Có nếu h(n) là admissible - không vượt quá giá trị thực tế từ trạng thái n tới đích.
- Mô tả:
- 
- Admisible Heuristics:
- Hàm đánh giá chấp nhận được
- Hàm đánh giá h(n) là chấp nhận được nếu h(n) luôn “lạc quan”: không bao giờ đánh giá cao hơn giá trị thực.
- Nếu h(n) chấp nhận được thì A* luôn cho nghiệm tối ưu.
- Dominance (Tính áp đảo):
- 
- Cách tìm Hàm đánh giá chấp nhận được:
- Giảm bớt ràng buộc.
- Một bài toán với ít rằng buộc hơn trong các hành động được gọi là **bài toán nới lỏng (relaxed problem)**
- Giá của giải pháp tối ưu cho bài toán nới lỏng là hàm đánh giá chấp nhận được của bài toán ban đầu
- Ví dụ:
- Nếu luật của bài toán 8 số là nới lỏng để các quân có thể di chuyển tùy ý (bất cứ chỗ nào) thì h1(n) cho **giải pháp ngắn nhất**
- Nếu luật của bài toán 8 số là nới lỏng để các quân có thể di chuyển bất kì ô vuông liền kề, thì h2(n) cho **giải pháp ngắn nhất**
- h1(n) = số quân nằm không đúng vị trí
- h2(n) = Tổng số khoảng cách vị trí của các quân và vị trí đích của chúng

- Hàm heuristic tổng hợp:
- 
- Tìm kiếm có trọng số A*:
- Ý tưởng: tăng tốc độ tìm kiếm với chi phí tối ưu
- Lấy một heuristic có thể chấp nhận được, “thổi phồng” nó lên bội số α > 1, rồi thực hiện tìm kiếm A* như bình thường
- Ít nút hơn có xu hướng được mở rộng, nhưng giải pháp thu được có thể không tối ưu (chi phí của nó tối đa sẽ gấp α lần chi phí của giải pháp tối ưu)
- Cải tiến thuật toán A* bằng nhánh cận:
- 

## Bài 4: Các chiến lược tìm kiếm có đối thủ (trò chơi game)

### 1. Giới thiệu:
- Các thể loại game:
- 
- Why Games?
- Đối thủ “khó đoán”: giải pháp là chiến lược:
- Phải đáp lại mọi câu trả lời có thể có của đối thủ
- Giới hạn thời gian: phải dựa vào sự gần đúng
- Đánh đổi giữa tốc độ và độ chính xác
- Trò chơi là động lực chính cho các kỹ thuật mới trong CS và AI.
- Tìm kiếm có đối thủ:
- Sẽ nghiên cứu các trò chơi có 2 người tham gia
- Xem xét các vấn đề:
- Chơi cờ có thể xem như vấn đề tìm kiếm trong không gian trạng thái
- Chiến lược tìm kiếm nước đi Minimax
- Phương pháp cắt cụt α-β: α-β pruning

### 2. Không gian trạng thái cho trò chơi
- Vấn đề chơi cờ có thể xem như vấn đề tìm kiếm trong không gian trạng thái:
- Mỗi trạng thái là một tình thế
- Trạng thái ban đầu là tình thế lúc bắt đầu cuộc chơi
- Các toán tử là các nước đi hợp lệ
- Các trạng thái kết thúc là các tình thế mà cuộc chơi dừng
- Một hàm kết cuộc ứng với mỗi trạng thái kết thúc với một giá trị nào đó, ví dụ thắng là 1, thua là -1, hòa là 0
- Vấn đề của Trắng là tìm một dãy nước đi sao cho xen kẽ với các nước đi của Đen tạo thành một đường đi từ trạng thái ban đầu tới giá trị kết cuộc là cao nhất
- Không biết trước nước đi của đối thủ:
- liệt kê hết các nước đi của đối thủ.
- Cây trò chơi:
- Để thuận lợi, ta biểu diễn không gian trạng thái dưới dạng cây trò chơi
- Cây trò chơi được xây dựng như sau:
- Gốc của cây ứng với trạng thái ban đầu
- Gọi đỉnh ứng với trạng thái mà Trắng (Đen) sẽ đưa ra nước đi là đỉnh Trắng (Đen)
- Ví dụ: 

### 3. Chiến lược Minimax
- Chọn nước đi với giá trị minimax lớn nhất:
- Trắng = Max, Đen = Min.
- Đi ngược từ các trạng thái kết thúc
- Gán giá trị cho các trạng thái kết thúc là giá trị của hàm kết cuộc
- Đi ngược từ dưới lên:
- nếu là đỉnh trắng thì gán giá trị là max của giá trị những nút con của nó;
- nếu là đỉnh đen thì gán giá trị là min của giá trị những nút con của nó
- Trắng: chọn nước đi là nút con có giá trị lớn nhất
- Cài đặt: 
- Nhận xét:
- Là thuật toán tìm kiếm theo độ sâu
- Cho phép ta chọn được nước đi tối ưu
- Tuy nhiên độ phức tạp quá lớn
- Có thể hạn chế độ sâu của cây trò chơi và sử dụng hàm đánh giá để giảm bớt cây tìm kiếm
- Cải tiến: 
- Đánh giá:
- Complete? Yes (if tree is finite)
- Optimal? Yes (against an optimal opponent)
- Time complexity? $O(b^m)$
- Space complexity? $O(bm)$ (depth-first exploration)
- Hàm đánh giá:
- Thường là giá trị đánh giá độ lợi thế của trạng thái u – eval(u)
- Trạng thái u càng thuận lợi cho Trắng thì eval(u) là số dương càng lớn: MAX
- Trạng thái u càng thuận lợi cho Đen thì eval(u) là số âm càng nhỏ: MIN
- eval(u) ≈ 0 đối với trạng thái u không lợi thế cho ai cả
- eval(u) = rất lớn – Trắng thắng
- eval(u) = rất nhỏ - Đen thắng
- Chất lượng của chương trình chơi cờ rất phụ thuộc vào hàm đánh giá
- Tuy nhiên độ tốt của một hàm đánh giá thường mâu thuẫn với thời gian để tính nó

### 4. Phương pháp cắt cụt alpha-beta
- Cho phép cắt bỏ các nhánh không cần thiết cho sự đánh giá đỉnh u
- Nếu a là đỉnh trắng, nếu u, v đã được gán và giá trị của u > giá trị của v thì không cần gán giá trị của a nữa
- Nếu a là đỉnh đen, nếu u, v đã được gán và giá trị của u < giá trị của v thì không cần gán giá trị của a nữa
- 
- Ví dụ: 
- Nhận xét:
- alpha là max
- beta là min
- Ta thấy rằng nếu alpha lớn hơn beta --> cắt cụt nhánh còn lại
- Nhận xét:
- Phương pháp cắt cụt alpha-beta không ảnh hưởng đến kết qủa cuối cùng, chỉ ảnh hưởng đến thời gian tìm kiếm.
- Thứ tự sắp xếp các bước đi trong cây tìm kiếm ảnh có ảnh hưởng lớn đến “chất lượng” của phương pháp cắt cụt alpha-beta.
- Với một “sắp xếp hoàn hảo”, time complexity = $O(b^{m/2})$ từ $O(b^m)$.
- Mô tả:
- 
- 
- 
- Các kỹ thuật nâng cao:
- **Bảng chuyển vị** để lưu trữ các trạng thái được mở rộng trước đó
- **Cắt tỉa về phía trước** để tránh xem xét tất cả các bước di chuyển có thể
- **Bảng tra cứu** nước đi mở đầu và tàn cuộc

## Bài 5: Học máy (Machine Learning)

### 1. Tại sao Học máy lại quan trọng?
- Kỷ nguyên dữ liệu lớn (Bigdata)
- Phát triển hệ thống là quá khó/đắt đỏ để xây dựng trí thức bằng tay bởi vì chúng yêu cầu các kỹ năng cụ thể và chi tiết hoặc điều chỉnh tri thức cho nhiệm vụ cụ thể (**knowledge engineering bottleneck**)

### 2. Học máy là gì?
- Học máy (Machine Learning – ML) là một lĩnh vực nghiên cứu của Trí tuệ nhân tạo (Artificial Intelligence – AI)
- Một số định nghĩa về học máy
- Một quá trình mà một chương trình máy tính cải thiện hiệu suất của nó trong một công việc thông qua kinh nghiệm [Mitchell, 1997]
- Việc lập trình các máy tính để tối ưu hóa một tiêu chí hiệu suất dựa trên các dữ liệu ví dụ hoặc kinh nghiệm trong quá khứ [Alpaydin, 2004]
- Học máy như tập các phương pháp có thể tự động xác định các mẫu trong dữ liệu và sau đó sử dụng các mẫu đã phát hiện để dự đoán dữ liệu trong tương lai [Murphy, 2012]
- Biểu diễn một bài toán học máy [Mitchell, 1997]
- Một công việc (nhiệm vụ) T
- Đối với các tiêu chí đánh giá hiệu năng P
- Thông qua (sử dụng) kinh nghiệm E
- Ví dụ: Lọc thư rác – Email spam filtering
- T: Dự đoán (để lọc) những thư điện tử nào là thư rác (spam email)
- P: % of các thư điện tử gửi đến được phân loại chính xác
- E: Một tập các thư điện tử (emails) mẫu, mỗi thư điện tử được biểu diễn bằng một tập thuộc tính (vd: tập từ khóa) và nhãn lớp (thư thường/ thư rác) tương ứng.

- Ứng dụng:
- **Viễn thám**: phân tích ảnh chụp từ trên cao …
- **Nhận dạng** (Pattern Recognition): nhận dạng tiếng nói, chữ viết tay, vân tay,
- **Thị giác máy** (Computer Vision) …
- **Xử lý ngôn ngữ tự nhiên** (Natural Language Processing): xử lý văn bản, giao tiếp người – máy, …
- **Tìm kiếm** (Search Engine, Ranking, Information Retrieve)
- **Chẩn đoán trong y tế**: phân tích ảnh X-quang, các hệ chuyên gia chẩn đoán tự động.
- **Tin sinh học**: phân loại chuỗi gene, quá trình hình thành gene/protein
- **Phát hiện gian lận tài chính** (financial fraud): gian lận thẻ tỉn dụng
- **Phân tích thị trường chứng khoán** (stock market analysis)
- **Chơi trò chơi**: tự động chơi cờ, hành động của các nhân vật ảo
- **Rôbốt**: là tổng hợp của rất nhiều ngành khoa học, trong đó học máy tạo nên hệ thần kinh/bộ não của người máy.

- Cách tiếp cận tổng quát:
- Phát biểu bài toán (Formulate task)
- Mô hình học (tham số, cấu trúc)
- Thu thập dữ liệu
- Biểu diễn dữ liệu của bài toán như thế nào? (đặc trưng/ giá trị)
- Gán nhãn dữ liệu
- Học mô hình với dữ liệu (huấn luyện)
- Sử dụng mô hình để phân lớp hoặc đoán dữ liệu mới (kiểm thử)
- Đánh giá độ chính xác

- Kiến trúc hệ thống học máy:
- 

### 3. Các vấn đề trong Học máy
- Các ví dụ học (Training examples)
- Bao nhiêu ví dụ học là đủ?
- Kích thước của tập học (tập huấn luyện) ảnh hưởng thế nào đối với độ chính xác của hàm mục tiêu học được?
- Các ví dụ lỗi (nhiễu) và/hoặc các ví dụ thiếu giá trị thuộc tính (missing-value) ảnh hưởng thế nào đối với độ chính xác?
- Quá trình học (Learning process)
- Chiến lược tối ưu cho việc lựa chọn thứ tự sử dụng (khai thác) các ví dụ học?
- Các chiến lược lựa chọn này làm thay đổi mức độ phức tạp của bài toán học máy như thế nào?
- Các tri thức cụ thể của bài toán (ngoài các ví dụ học) có thể đóng góp thế nào đối với quá trình học?
- Khả năng/giới hạn học (Learning capability)
- Hàm mục tiêu nào mà hệ thống cần học?
- Biểu diễn hàm mục tiêu: Khả năng biểu diễn (vd: hàm tuyến tính / hàm phi tuyến) vs. Độ phưc tạp của giải thuật và quá trình học
- Các giới hạn (trên lý thuyết) đối với khả năng học của các giải thuật học máy?
- Khả năng khái quát hóa (generalize) của hệ thống từ các ví dụ học?
- Để tránh vấn đề “over-fitting” (đạt độ chính xác cao trên tập học, nhưng đạt độ chính xác thấp trên tập thử nghiệm)
- Khả năng hệ thống tự động thay đổi (thích nghi) biểu diễn (cấu trúc) bên trong của nó?
- Để cải thiện khả năng (của hệ thống đối với việc) biểu diễn và học

### 4. Đánh giá hệ thống học máy
- Độ chính xác của phân lớp (Classification Accuracy)
- Tính đúng đắn của giải pháp (Solution correctness)
- Chất lượng của giải pháp (Solution quality (length, efficiency))
- Tốc độ thực hiện (Speed of performance)

### 5. Phân loại hệ thống học máy
- **Học có giám sát** (Supervised Learning): Máy tính được xem một số mẫu gồm **đầu vào** (input) và **đầu ra** (output) tương ứng trước. Sau khi học xong các mẫu này, máy tính quan sát một đầu vào mới và cho ra kết quả.
- **Học không giám sát** (Unsupervised Learning): Máy tính chỉ được xem các mẫu không có **đầu ra**, sau đó máy tính phải tự tìm cách phân loại các mẫu này và các mẫu mới.
- **Học nửa giám sát** (Semi-supervised Learning): Một dạng lai giữa hai nhóm giải thuật trên.
- **Học tăng cường** (Reinforcement Learning): Máy tính đưa ra quyết định **hành động** (action) và nhận kết quả **phản hồi** (response/rewiew)

## Bài 6: Đánh giá hiệu năng

### 1. Đánh giá hiệu năng hệ thống học máy
- Thường được thực hiện dựa trên trên **thực nghiệm** (experimentally) hơn là dựa trên phân tích (analytically)
- Các đánh giá phân tích (analytical evaluation) nhằm chứng minh một hệ thống là đúng đắn (correct) và hoàn chỉnh (complete) (vd: các bộ chứng minh định lý trong Logics)
- Không thể xây dựng một đặc tả (định nghĩa) hình thức của vấn đề mà một hệ thống học máy giải quyết
- Tập trung vào việc đánh giá hiệu năng của hệ thống
- Thực hiện một cách tự động, sử dụng một tập các ví dụ (tập thử nghiệm)
- Không cần sự tham gia (can thiệp) của người dùng

### 2. Các phương pháp đánh giá
- 
- Làm thế nào để thu được một đánh giá đáng tin cậy về hiệu năng của hệ thống?
- Tập huấn luyện càng lớn, thì hiệu năng của hệ thống học càng tốt
- Tập kiểm thử càng lớn, thì việc đánh giá càng chính xác
- **Vấn đề**: Rất khó (ít khi) có thể có được các tập dữ liệu (rất) lớn
- Hiệu năng của hệ thống không chỉ phụ thuộc vào giải thuật học máy được sử dụng, mà còn phụ thuộc vào:
- Phân bố lớp (Class distribution)
- Chi phí của việc phân lớp sai (Cost of misclassification)
- Kích thước của tập huấn luyện (Size of the training set)
- Kích thước của tập kiểm thử (Size of the test set)

#### a. Hold-out (Splitting)
- Toàn bộ tập ví dụ $D$ được chia thành 2 tập con **không giao nhau**
- Tập huấn luyện $D_{train}$ - để huấn luyện hệ thống
- Tập kiểm thử $D_{test}$ - để kiểm thử hệ thống
- Thường là $|D_{train}| >> |D_{test}|$
- Yêu cầu:
- Bất kỳ ví dụ nào ở tập $D_{test}$ đều không được sử dụng để huấn luyện
- Bất kỳ ví dụ nào ở tập $D_{train}$ đều không được sử dụng để kiểm thử
- Các ví dụ trong $D_{test}$ cho phép đánh giá không thiên vị đối với hiệu năng của hệ thống
- Các lựa chọn thường gặp:
- $|D_{train}| =\frac{2}{3} \cdot |D|$
- $|D_{test}| =\frac{1}{3} \cdot |D|$
- Phù hợp cho tập ví dụ *D* có kích thước lớn

#### b. Stratified sampling
- Đối với các tập ví dụ có kích thước nhỏ hoặc không cân xứng (unbalanced datasets), các ví dụ trong tập huấn luyện và thử nghiệm có thể không phải là đại diện
- Ví dụ: Có (rất) ít, hoặc không có, các ví dụ đối với một số lớp
- Mục tiêu: Phân bố lớp (class distribution) trong tập huấn luyện và tập kiểm thử phải xấp xỉ như trong tập toàn bộ các ví dụ (D)
- Lấy mẫu phân tầng (Stratified sampling)
- Là một phương pháp để cân xứng (về phân bố lớp)
- Đảm bảo tỷ lệ phân bố lớp (tỷ lệ các ví dụ giữa các lớp) trong tập huấn luyện và tập kiểm thử là xấp xỉ nhau
- Phương pháp lấy mẫu phân tầng không áp dụng được cho bài toán học máy dự đoán/hồi quy (vì giá trị đầu ra của hệ thống là một giá trị số, không phải là một nhãn lớp)

#### c. Repeated hold-out
- Áp dụng phương pháp đánh giá Hold-out nhiều lần, để sinh ra (sử dụng) các tập huấn luyện và thử nghiệm khác nhau
- Trong mỗi bước lặp, một tỷ lệ nhất định của tập D **được lựa chọn ngẫu nhiên** để tạo nên tập huấn luyện (có thể sử dụng kết hợp với phương pháp lấy mẫu phân tầng – stratified sampling)
- Các giá trị lỗi (hoặc các giá trị đối với các tiêu chí đánh giá khác) ghi nhận được trong các bước lặp này được lấy trung bình cộng (averaged) để xác định giá trị lỗi tổng thể
- Phương pháp này vẫn không hoàn hảo
- Mỗi bước lặp sử dụng một tập kiểm thử khác nhau
- Có một số ví dụ trùng lặp (được sử dụng lại nhiều lần) trong các tập kiểm thử này

#### d. Cross-validation
- Để tránh việc trùng lặp giữa các tập kiểm thử (một số ví dụ cùng xuất hiện trong các tập kiểm thử khác nhau)
- *k*-fold cross-validation
- Tập toàn bộ các ví dụ D được chia thành k tập con **không giao nhau** (gọi là “fold”) có kích thước xấp xỉ nhau
- Mỗi lần (trong số k lần) lặp, một tập con được sử dụng làm tập kiểm thử, và (k-1) tập con còn lại được dùng làm tập huấn luyện
- *k* giá trị lỗi (mỗi giá trị tương ứng với một fold) được tính trung bình cộng để thu được giá trị lỗi tổng thể
- Các lựa chọn thông thường của **k: 10, hoặc 5**
- Thông thường, mỗi tập con (fold) được lấy mẫu phân tầng (xấp xỉ phân bố lớp) trước khi áp dụng quá trình đánh giá Cross-validation
- Phù hợp khi ta có tập ví dụ $D$ vừa và nhỏ

#### e. Leave-one-out crossvalidation
- Một trường hợp (kiểu) của phương pháp Cross-validation
- Số lượng các nhóm (folds) bằng kích thước của tập dữ liệu ($k=|D|$)
- Mỗi nhóm (fold) chỉ bao gồm một ví dụ
- Khai thác tối đa (triệt để) tập ví dụ ban đầu
- Không hề có bước lấy mẫu ngẫu nhiên (no random sub-sampling)
- Áp dụng lấy mẫu phân tầng (stratification) không phù hợp
- Vì ở mỗi bước lặp, tập thử nghiệm chỉ gồm có một ví dụ
- Chi phí tính toán (rất) cao
- Phù hợp khi ta có một tập ví dụ $D$ (rất) nhỏ

#### f. Bootstrap sampling
- Phương pháp Cross-validation sử dụng việc lấy mẫu không lặp lại (sampling without replacement)
- Đối với mỗi ví dụ, một khi đã được chọn (được sử dụng), thì không thể được chọn (sử dụng) lại cho huấn luyện
- Phương pháp Bootstrap sampling sử dụng việc **lấy mẫu có lặp lại** **(sampling with replacement)** để tạo nên tập huấn luyện
- Giả sử tập toàn bộ $D$ bao gồm $n$ ví dụ
- Lấy mẫu có lặp lại $n$ lần đối với tập $D$, để tạo nên tập huấn luyện $D_{train}$ gồm $n$ ví dụ
- Từ tập $D$, lấy ra *ngẫu nhiên* một ví dụ $x$ (nhưng không loại bỏ $x$ khỏi tập D)
- Đưa ví dụ $x$ vào trong tập huấn luyện: $D_{train}=D_{train} \cup x$
- Lặp lại 2 bước trên n lần
- Sử dụng tập $D_{train}$ để huấn luyện hệ thống
- Sử dụng tất cả các ví dụ thuộc $D$ **nhưng không thuộc** $D_{train}$ để tạo nên tập thử nghiệm: $D_{test}= \{z \in D; z \notin D_{train} \}$
- Trong mỗi bước lặp, một ví dụ có xác suất $=(1-\frac{1}{n})$ để không được lựa chọn đưa vào tập huấn luyện
- Vì vậy, xác suất để ví dụ (sau quá trình lấy mẫu lặp lại - bootstrap sampling) được đưa vào tập kiểm thử là: $(1-\frac{1}{n})^n \approx e^{-1} \approx 0.368$
- Có nghĩa rằng:
- Tập huấn luyện (có kích thước $= n$) bao gồm xấp xỉ $63.2\%$ các ví dụ trong $D$ (Lưu ý: Một ví dụ tập $D$ có thể **xuất hiện nhiều lần** trong tập $D_{train}$)
- Tập kiểm thử (có kích thước $< n$) bao gồm xấp xỉ $36.8\%$ các ví dụ trong $D$ (Lưu ý: Một ví dụ tập $D$ có thể **xuất hiện tối đa 1 lần** trong tập $D_{test}$)
- Phù hợp khi ta có một tập dữ liệu $D$ có kích thước (rất) nhỏ

### 3. Tập tối ưu
- Các ví dụ trong tập kiểm thử không thể được sử dụng (theo bất kỳ cách nào!) trong quá trình huấn luyện hệ thống
- Trong một số bài toán học máy, quá trình huấn luyện hệ thống bao gồm 2 giai đoạn
- Giai đoạn thứ 1: Huấn luyện hệ thống (= Học hàm mục tiêu)
- Giai đoạn thứ 2: Tối ưu giá trị các tham số của hệ thống
- Tập kiểm thử không thể được sử dụng cho mục đích tối ưu (điều chỉnh) tham số
- Chia tập toàn bộ các ví dụ D thành 3 tập con không giao nhau: tập *huấn luyện*, tập *tối ưu*, và tập *kiểm thử*
- Tập tối ưu (validation set) được sử dụng để tối ưu giá trị các tham số trong giải thuật học máy được sử dụng
- Đối với một tham số, giá trị tối ưu là giá trị giúp sinh ra *hiệu năng cực đại đối với tập tối ưu*

### 4. Các tiêu chí đánh giá
- Tính chính xác (Accuracy)
- Mức độ dự đoán (phân lớp) chính xác của hệ thống (đã được huấn luyện) đối với các ví dụ kiểm chứng (test instances)
- Tính hiệu quả (Efficiency)
- Chi phí về thời gian và tài nguyên (bộ nhớ) cần thiết cho việc huấn luyện và kiểm thử hệ thống
- Khả năng xử lý nhiễu (Robustness)
- Khả năng xử lý (chịu được) của hệ thống đối với các ví dụ nhiễu (lỗi) hoặc thiếu giá trị
- Khả năng mở rộng (Scalability)
- Hiệu năng của hệ thống (vd: tốc độ học/phân loại) thay đổi như thế nào đối với kích thước của tập dữ liệu
- Khả năng diễn giải (Interpretability)
- Mức độ dễ hiểu (đối với người sử dụng) của các kết quả và hoạt động của hệ thống
- Mức độ phức tạp (Complexity)
- Mức độ phức tạp của mô hình hệ thống (hàm mục tiêu) học được

#### a. Tính chính xác
- Đối với bài toán phân loại
- Giá trị (kết quả) của đầu ra của hệ thống là một giá trị định danh $Accuracy=\frac{1}{|D_{test}|} \cdot \displaystyle \sum_{x \in D_{test}} Identical(o(x), c(x))$
- $Identical(a, b) = 1$ nếu $a = b$
- $Identical(a, b) = 0$ nếu không
- $x$: Một ví dụ trong tập thử nghiệm $D_{test}$
- $o(x)$: Giá trị đầu ra (phân lớp) bởi hệ thống đối với ví dụ $x$
- $c(x)$: Phân lớp thực sự (đúng) đối với ví dụ $x$
- Đối với bài toán hồi quy (dự đoán)
- Giá trị (kết quả) của đầu ra của hệ thống là một giá trị số $Error=\frac{1}{|D_{test}|} \cdot \displaystyle \sum_{x \in D_{test}}Error(x)$
- $Error(x)=|d(x)-o(x)|$
- $o(x)$: Giá trị đầu ra (dự đoán) bởi hệ thống đối với ví dụ $x$
- $d(x)$: Giá trị đầu ra thực sự (đúng) đối với ví dụ $x$
- $Accuracy$ là một hàm đảo (inverse function) đối với $Error$

#### b. Ma trận nhầm lẫn (Confusion Matrix)
- Còn được gọi là Contingency Table
- Chỉ được sử dụng đối với bài toán phân loại
- 
#### c. Precision and Recall
- 
- 
#### d. $F_1$
- 

### 5. Lựa chọn mô hình học được
- Việc lựa chọn mô hình cần tìm ra sự thỏa hiệp (compromise) phù hợp giữa
- Mức độ phức tạp của mô hình hệ thống học được
- Mức độ chính xác về dự đoán của hệ thống đối với tập huấn luyện
- Nguyên lý Occam’s razor. Một mô hình tốt là một mô hình **đơn giản** đạt **độ chính xác (về phân loại/dự đoán) cao** đối với tập dữ liệu được sử dụng

## Bài 7: Phương pháp học máy Bayesian (Bayesian Learning)

### 1. Giới thiệu:
#### a. Bài toán phân lớp có giám sát:
- Dữ liệu huấn luyện: Các ví dụ theo dạng (d,h(d))
- trong đó d là đối tượng dữ liệu cần phân lớp (đầu vào)
- và h(d) là lớp đúng của d, $h(d) \in \{1,…K\}$
- Mục tiêu: Biết d_new, xác định h(d_new)
- 

#### b. Tại sao là Bayesian?
- Cung cấp **thuật toán học trong thực tế**
- VD: Naïve Bayes (Bayes ngây thơ)
- Trí thức biết trước và dữ liệu quan sát có thể kết hợp với nhau
- Nó là mô hình sinh (generative model):
- Bất kỳ loại đối tượng có thể phân lớp dựa vào sự cụ thể của mô hình xác suất của các lớp đó.

#### c. Định luật Bayes
- 
#### d. Chọn giả thuyết
- Một cách tổng quát chúng ta muốn giả thuyết có thể nhất được cho bởi dữ liệu huấn luyện. Đây là làm cực đại giả thuyết hậu nghiệm:
- **Ích lợi từ dữ liệu quan sát**: Nó không phụ thuộc vào mẫu số P(d)
- 
- 

### 2. Phân lớp Bayes ngây thơ (Naïve Bayes Classifier)
- 
- 
- 

## Bài 8: Neural Networks
### 1. Giới thiệu:
#### a. Mô hình Bayes ngây thơ
- 
#### b. Mô hình tuyến tính
- 
#### c. Giới hạn của tuyến tính
- Chúng ta có thể gán cho mỗi đặc điểm một trọng số
- Nhưng không phải các mối quan hệ giá trị phức tạp hơn, ví dụ:
- mọi giá trị trong khoảng [0;5] đều tốt như nhau
- giá trị trên 8 là xấu
- cao hơn 10 không phải là tệ hơn
#### d. Nhiều lớp
- 

#### e. Phi tuyến tính
- 
- 

#### f. Ví dụ:
- 
- 
- 
- 

## Bài 9: Support Vector Machines

### 1. Giới thiệu:
- Máy vectơ hỗ trợ (Support vector machine - SVM)
- SVM là một phương pháp **phân lớp tuyến tính** (linear classifier), với mục đích xác định một siêu phẳng (hyperplane) để phân tách phân tách **hai lớp** của dữ liệu – ví dụ: lớp các ví dụ có nhãn dương (positive) và lớp các ví dụ có nhãn âm (negative)
- **Các hàm nhân (kernel functions)**, cũng được gọi là các hàm biến đổi (transformation functions), được dùng cho các trường hợp phân lớp phi tuyến
- SVM đã được biết đến là một trong số các phương pháp phân lớp tốt nhất đối với các bài toán phân lớp văn bản (text/document classification)
- SVM là một phương pháp tốt (phù hợp) đối với những bài toán phân lớp có không gian biểu diễn thuộc tính lớn – các đối tượng cần phân lớp được biểu diễn bởi một tập rất lớn các thuộc tính
- Biểu diễn tập *r* các ví dụ huấn luyện (training examples)
- $\{(x_1, y_1), (x_2, y_2), ...,(x_r, y_r) \}$
- Trong đó:
- $x_i$ là một **vector đầu vào** được biểu diễn trong không gian $X\subseteq \mathbb{R}^n$
- $y_i$ là một **nhãn lớp** (giá trị đầu ra), $y_i\in \{-1,1\}$
- $y_i = -1$ là lớp âm, $y_i = 1$ là lớp dương
- 

### 2. Mặt phẳng siêu phân tách
- Mặt siêu phẳng phân tách các ví dụ huấn luyện lớp dương và các ví dụ huấn luyện lớp âm: $〈w ⋅ x〉 + b = 0$
- Còn được gọi là ranh giới (bề mặt) quyết định
- Tồn tại nhiều mặt siêu phẳng phân tách.
- 

#### a. Mặt siêu phẳng có lề cực đại
- SVM lựa chọn mặt siêu phẳng phân tách có lề (margin) lớn nhất
- Lý thuyết học máy đã chỉ ra rằng một mặth siêu phẳng phân tách như thế sẽ tối thiểu hóa giới hạn lỗi (phân lớp) mắc phải
- 

### 3. Dữ liệu phân tách được tuyến tính
- Giả sử rằng tập dữ liệu (tập các ví dụ huấn luyện) có thể phân tách được một cách tuyến tính
- Xét một ví dụ của lớp dương $(x^+,1)$ và một ví dụ của lớp âm $(x^-,-1)$ *gần nhất* đối với siêu phẳng **phân tách** $H_0$ $(<w⋅x>+b=0)$
- 

### 4. Tính toán mức lề
- **Mức lề** (margin) là khoảng cách giữa 2 siêu phẳng lề $H_+$ và $H_-$ Trong hình vẽ nêu trên:
- $d_+$ là khoảng cách giữa $H_+$ và $H_0$
- $d_-$ là khoảng cách giữa $H_-$ và $H_0$
- $(d_+ + d_−)$ là mức lề
- 
- 

### 5. Học SVM - Cực đại hóa mức lề
- 
- 

### 6. Lý thuyết tối ưu có ràng buộc
- 
- 
- Còn lại xem tại: https://courses.uet.vnu.edu.vn/pluginfile.php/371665/mod_resource/content/1/2016_Slide12-SVM.pdf

## Bài 10: Logic mệnh đề

### 1. Dữ liệu – Thông tin – Tri thức:

- **Dữ liệu (Data)**: theo khái niệm của nghành khoa học máy tính, dữ liệu là các con số, chữ cái, hình ảnh và âm thanh … mà máy tính có thể tiếp nhận và xử lý được.
- **Thông tin (Information)**: là tất cả những gì con người có thể cảm nhận được một cách trực tiếp qua các giác quan của mình hoặc gián tiếp thông quan các phương tiện kỹ thuật.
- **Tri thức (Knowledge)**:
- **Các dữ liệu** được sắp xếp theo một thứ tự hoặc được tập hợp theo một quan hệ nào đó sẽ chứa đựng **các thông tin**.
- Và những quan hệ đó nếu được chỉ ra một cách rõ ràng thì đó là **các tri thức**.
- Về mức độ trừu tượng tri thức là khái niệm trừu tượng nhất trong ba khái niệm trên.
- **Tri thức sự kiện (events)**: các khẳng định về một sự kiện, khái niệm nào đó (các định luật khoa học, ..)
- **Tri thức thủ tục (procedure)**: diễn tả các phương pháp giải quyết vấn đề (các thuật toán, thuật giải, …)
- **Tri thức mô tả (description)**: đối tượng, sự kiện, vấn đề, khái niệm, … được thấy, cảm nhận và mô tả ntn ?
- **Tri thức heuristic**: là dạng tri thức cảm tính, ước lượng, phỏng đoán thông quan kinh nghiệm.

### 2. Biểu diễn tri thức:

- Tri thức được mô tả dưới dạng các câu trong **ngôn ngữ biểu diễn tri thức**.
- Mỗi câu có thể xem như là một sự đặc tả hình thức của một sự hiểu biết của chúng ta về thế giới hiện thực.
- Ngôn ngữ biểu diễn tri thức (cũng như mọi ngôn ngữ hình thức khác) bao gồm hai thành phần cơ bản là **cú pháp** và **ngữ nghĩa**.
- **Cú pháp (Syntax)**: gồm các ký hiệu và các quy tắc liên kết các ký hiệu (các luật cú pháp) để tạo thành các câu (công thức) trong ngôn ngữ.
- **Ngữ nghĩa (Semantic)**: cho phép ta xác định ý nghĩa của các câu trong một miền nào đó của thế giới hiện thực.
- **Ngôn ngữ biểu diễn tri thức = Cú pháp + Ngữ nghĩa + Cơ chế lập luận**.
- Ngoài ra ngôn ngữ biểu diễn tri thức cần được cung cấp **cơ chế lập luận (reasoning mechanism)**.
- **Lập luận tự động (automated reasoning)** được hiểu là một quá trình tính toán, nó lấy đầu vào là các công thức (các đặc tả hình thức của các tri thức đã biết) và cho ra các công thức mới (các đặc tả hình thức của các tri thức mới).
- Lập luận trong các ngôn ngữ biểu diễn tri thức được tiến hành bằng các sử dụng các **luật suy diễn (rule of inference)** cho phép ta suy ra một công thức từ một tập nào đó các công thức.

### 3. Các phương pháp biểu diễn tri thức
- Logic mệnh đề.
- Logic vị từ.
- Luật dẫn xuất (luật sinh).
- Mạng ngữ nghĩa.
- Frame.
- Script.

#### a. Logic mệnh đề:
- Cú pháp:
- Các ký hiệu
- Hai hằng logic là **True** và **False**.
- Các ký hiệu (biến) mệnh đề : các chữ cái la tinh như a, b,c …
- Các kết nối logic: $\land, \lor, \neg, \rightarrow, \leftrightarrow$
- Các dấu mở ngoặc và đóng ngoặc
- Các quy tắc xây dựng công thức
- Các biến mệnh đề là các công thức.
- Nếu $A$ và $B$ là các công thức thì $(A\land B), (A\lor B), (\neg A), (A\rightarrow B), (A\leftrightarrow B)$ cũng là các công thức.
- Ngữ nghĩa:
- Cho phép ta xác định ý nghĩa của các công thức trong thế giới hiện thực nào đó.
- Ngữ nghĩa được thực hiện bằng cách kết hợp mỗi ký hiệu mệnh đề với một mệnh đề phát biểu một khẳng định nào đó về thế giới hiện thực, và sự kết hợp như thế được gọi là một **minh họa (Interpretation).**
- Ta có thể hiểu một minh họa là một cách gán cho mỗi ký hiệu mệnh đề một giá trị chân lý **True** hoặc **False.**
- Một số khái niệm ngữ nghĩa:
- Công thức **thỏa được** (satisfiable): đúng trong một minh họa nào đó. Ví dụ: $(P ∨ \neg Q) ∧ B)$ có giá trị **true** trong minh họa (P: true, Q: False, B: true)
- Công thức **vững chắc** (valid or tautology): đúng trong mọi minh họa.
- Công thức **không thỏa được**: sai trong mọi minh họa.
- **Mô hình** (model) của một công thức là một minh họa sao cho công thức đó đúng trong minh họa này.
- Bảng giá trị chân lý: 
- **Sự tương đương**: 
- Dạng chuẩn tắc
- Để dễ dàng viết các chương trình máy tính chúng ta chuẩn hóa các công thức đưa chúng về **dạng chuẩn hội**, tức là hội của các câu tuyển.
- Áp dụng thủ tục sau:
- Bỏ các dấu kéo theo →: $A→B = \neg A∨B$
- Chuyển các dấu phủ định $\neg$ vào sát các ký hiệu mệnh đề bằng luật De Morgan
- Áp dụng luật phân phối $A ∨ (B ∧ C) = (A ∨ B) ∧(A ∨ C)$
- Các luật suy diễn
- Một công thức H được xem là hệ quả logic của một tập công thức G = {G1,…,Gm} nếu từ G1, … , Gm ta có thể suy ra H (trong bất cứ minh họa nào mà G đúng thì H cũng đúng
- Khi có một cơ sở tri thức, ta muốn sử dụng các tri thức trong cơ sở này để suy ra tri thức mới mà nó là hệ quả logic của các công thức trong cơ sở tri thức.
- Được thực hiện bằng cách sử dụng các luật suy diễn
- Một luật suy diễn gồm hai phần: một tập các điều kiện và một kết luận
- Ta sẽ biểu diễn các luật suy diễn dưới dạng “phân số”:
- trong đó tử số là danh sách các điều kiện
- còn mẫu số là kết luận của luật
- mẫu số là công thức mới được suy ra từ các công thức ở tử số
- Luật Modus Ponens (khẳng định): \begin{equation} \frac{ \begin{eqnarray*} \alpha \rightarrow \beta \\ \alpha \end{eqnarray*} }{\begin{eqnarray*}
\beta \end{eqnarray*} }\end{equation}
- Luật Modus Tollens (phủ định): \begin{equation} \frac{ \begin{eqnarray*} \alpha \rightarrow \beta \\ \neg \beta \end{eqnarray*} }{\begin{eqnarray*} \neg \alpha \end{eqnarray*} }\end{equation}
- Luật bắc cầu (tam đoạn luận): \begin{equation} \frac{ \begin{eqnarray*} \alpha \rightarrow \beta \\ \beta \rightarrow \gamma \end{eqnarray*} }{\begin{eqnarray*} \alpha \rightarrow \gamma \end{eqnarray*} }\end{equation}
- Luật rút gọn: \begin{equation} \frac{ \begin{eqnarray*} \alpha \\ \beta \end{eqnarray*} }{\begin{eqnarray*} \alpha \end{eqnarray*} }\end{equation}
- Luật cộng: \begin{equation} \frac{ \begin{eqnarray*} \alpha \end{eqnarray*} }{\begin{eqnarray*} \alpha \lor \beta \end{eqnarray*} }\end{equation}
- Luật tam đoạn luận rời: \begin{equation} \frac{ \begin{eqnarray*} \alpha \lor \beta \\ \neg \alpha \end{eqnarray*} }{\begin{eqnarray*} \beta \end{eqnarray*} }\end{equation}
- Luật theo trường hợp: \begin{equation} \frac{ \begin{eqnarray*} \alpha \rightarrow \gamma \\ \beta \rightarrow \gamma \end{eqnarray*} }{\begin{eqnarray*} (\alpha \lor \beta) \rightarrow \gamma \end{eqnarray*} }\end{equation}
- Luật phân giải: \begin{equation} \frac{ \begin{eqnarray*} \alpha \lor \beta \\ \neg \beta \lor \gamma \end{eqnarray*} }{\begin{eqnarray*} \alpha \lor \gamma \end{eqnarray*} }\end{equation}
- Luật suy diễn mâu thuẫn: 
- Luật phân giải: 
- Các thuật toán trên logic mệnh đề
- Phát biểu bài toán
- Input: Tập các công thức
- Công thức cần chứng minh.
- Output: một cách lập luận từ input ra các công thức cần chứng minh
- Thuật toán:
- Thuật giải Robinson
- Chứng minh bằng thuật toán phân giải:
- Hoạt động dựa trên phương pháp chứng minh phản chứng và luật phân giải.
- Lần lượt ghép hai cặp câu với nhau và áp dụng định luật phân giải sinh ra câu mới đưa vào tập tri thức.
- Cứ làm như vậy cho đến khi không sinh ra được câu mới thì thôi.
- Thuật toán phân giải: Đặc tả
- 
- Thuật toán phân giải: Ví dụ minh họa
- 

## Bài 11: Logic vị từ

### 1. Hạn chế của logic mệnh đề
- Trong phần trước chúng ta đã đề cập đến logic mệnh đề sử dụng để mô tả hệ thống tri thức
- Hệ thống sự kiện
- Các phép toán logic thể hiện mối quan hệ giữa các sự kiện
- Các cơ chế chứng minh:
- Chứng minh bằng bác bỏ
- Suy diễn tiến (đi từ tập sự kiện)
- Suy diễn lùi (dò ngược từ tập kết luận)
- Các cơ chế trên cũng được con người sử dụng trong quá trình học tập, suy lý
- Vấn đề lớn nhất của logic mệnh đề là chỉ tập trung vào sự kiện mà không thể hiện được sự tương quan giữa cá thể và thế giới
- Khả năng diễn đạt hạn chế
- Biểu diễn các sự kiện
- Không thể mô tả đầy đủ thế giới các đối tượng, tính chất và mối quan hệ giữa các đối tượng
- Ví dụ:

### 2. Logic vị từ
- 

### 3. Thành phần của logic vị từ
- Hằng: các đối tượng cụ thể trong miền nào đó
- a, b, c, Mai, Nam, John,...
- Biến: chỉ đối tượng tổng quát hóa
- x, y, z, u, v, w,...
- Hàm: thuộc tính của đối tượng hoặc nhóm đối tượng
- best_friend(x), father(x), distance(x,y), …
- Vị từ: các mối quan hệ giữa các đối tượng hoặc tính chất của đối tượng
- friend(x,y), father(x,y), love(x,y), good(x),...
- Phép lượng tử: với mọi ($∀$), tồn tại ($∃$)

#### a. Lượng tử logic "với mọi"
- ∀ (biến_1, biến_2,…, biến_n): <mệnh đề>
- Ví dụ:
- An là bạn của tất cả mọi người
- ∀x: friend(An, x)
- Tất cả những người nuôi động vật đều yêu động vật
- ∀x, ∀y: rear(x, y) ᴧ animal(y) → love_animal(x)
- Tất cả sinh viên công nghệ thông tin Thủy Lợi đều chăm học
- ∀x: tlu_cntt_student(x) → chăm(x)
- Mệnh đề (∀x: P) đúng khi và chỉ khi P đúng với mọi đối tượng trong thế giới
- Ví dụ: 

#### b. Lượng tử logic "tồn tại"
- ∃(biến_1, biến_2 ,…, biến_n): <mệnh đề>
- Ví dụ:
- Có một người là bạn của An
- ∃x: friend(An, x)
- Tồn tại một người nuôi một con động vật nào đấy nhưng lại không yêu động vật
- ∃x, ∃y: rear(x,y) ᴧ animal(y) ᴧ ¬love_animal(x)
- Tồn tại một sinh viên công nghệ thông tin Thủy Lợi chăm học
- ∃x: tlu_cntt_student(x) ᴧ chăm(x)
- Tồn tại một sinh viên học tất cả các môn học của ngành công nghệ thông tin
- ∃x, ∀y: student(x) ᴧ learn(x, y) ᴧ it_subject(y)
- Mệnh đề (∃x:P) đúng khi P đúng với ít nhất một đối tượng trong thế giới
- Ví dụ: 

### 4. Đặc điểm của logic lượng tử
- Tính hoán vị:
- $(∀x ∀y) ≡ (∀y ∀x)$
- $(∃x ∃y) ≡ (∃y ∃x)$
- Tuy nhiên, (∃x ∀y) không tương đương với (∀x ∃y)
- ∃x ∀y know(x, y): tồn tại 1 người biết tất cả các lĩnh vực
- ∀x ∃y know(x, y): tồn tại 1 lĩnh vực mà mọi người đều biết
- Đưa các phép lượng tử vào từng vị từ
- ∀x ((G(x) ᴧ H(x)) ≡ (∀x G(x)) ᴧ (∀x H(x))
- ∃x ((G(x) v H(x)) ≡ (∃x G(x)) v (∃x H(x))
- Loại bỏ ∀: ∀x G(x) ≡ G(x)
- Đặt lại tên biến
- ∀x G(x) ≡ ∀y G(y)
- ∃x G(x) ≡ ∃y G(y)
- Loại bỏ ¬
- ¬(∀x G(x)) ≡ ∃x (¬G(x))
- ¬(∃x G(x)) ≡ ∀x (¬G(x))
- Mỗi lượng tử (∀, ∃) đều có thể biểu diễn bởi lượng tử kia
- ∀x friend(An, x) ≡ ¬(∃x ¬friend(An, x))
- An là bạn của mọi người ≡ không có ai An không là bạn
- ∃x friend(An, x) ≡ ¬(∀x ¬friend(An, x))
- Có 1 người là bạn của An ≡ không phải tất cả mọi người đều không là bạn của An

### 5. Chứng minh logic vị từ
- 

#### a. Luật thay thế
- Một cách tổng quát, một phép thay thế $θ$ là một dãy các cặp $x_i/t_i$: $θ = [x_1/t_1, x_2/t_2, …, x_n/t_n]$ trong đó $x_i$ là các biến khác nhau, $t_i$ là các hạng thức không chứa $x_i$
- Áp dụng phép thay thế $θ$ vào công thức $G$, ta nhận được công thức $Gθ (Subst(θ, G))$
- Ví dụ: $G = P(x, y, f(a,x))$ và $θ = [x|b,y|g(z)]$ thì $Gθ = P(b,g(z),f(a,b))$
- Phép thay thế $θ$ được gọi là phép hợp nhất (unification) cho $C$ và $D$ nếu $Cθ = Dθ$, phép thay thế $θ$ được gọi là **hợp nhất tử** của $C$ và $D$. $C$ và $D$ gọi là **hợp nhất được**.
- Một hằng số a không được thay bằng một biến x
- Một biến x không được thay bằng một hạng thức có chứa x

#### b. Luật thay thế phổ dụng
- 

#### c. Luật Modus Ponens tổng quát
- Ví dụ:
- $Student(x) \land Male(x) → Like(x,football)$ và $Student(Anh), Male(Anh)$. Với phép thế $θ=[x|Anh]$, các cặp câu $Student(x), Student(Anh)$ và $Male(x), Male(Anh)$ hợp nhất được, do đó suy ra câu $Like(Anh,Football)$.

#### d. Luật phân giải tổng quát
- Luật phân giải trên các câu tuyển
- Luật phân giải trên các các câu Horn
- Thuật toán hợp nhất: 
- Ví dụ: 
- 
- Sự khác biệt giữa hai biểu thức được xác định như sau:
- Đọc hai biểu thức đồng thời từ trái sang phải cho tới khi gặp hai ký hiệu khác nhau trong biểu thức. Trích ra hai biểu thức con bắt đầu tư các ký hiệu đó.
- Ví dụ: Sự khác biệt giữa Like(x,f(a,g(z))) và Like(x,y) là cặp f(a,g(z)) và y
- Sự khác biệt giữa Know(x,f(a,u)) và Know(x,f(a,g(b)) là cặp u và g(b)
- Tìm hợp nhất tử tổng quát nhất cho: P(a, x, y, z) và P(x, y, z, w), a là hằng.
- Chứng minh bằng luật phân giải: