---
tags: 大四

---

# 人工智慧(Artificial Intelligence) Spring 2021

[TOC]

## 1. Introduction

### What is AI

* 四個面向

| | Humanly | Rationally |
| -------- | ---------------- | ------------------- |
| Thinking | Thinking Humanly | Thinking Rationally |
| Acting | Acting Humanly | Acting Rationally |

### Acting Humanly

#### Turing Test

* 人無法分辨是人還是機器
* 包含：
* NLP
* knowledge representation
* automated reasoning
* ML
* More:
* computer vision
* robotics

#### Reverse Turing Tests: CAPTCHAs

* 我不是機器人
<img src="https://i.imgur.com/25kmNfs.png" width="30%">

## 2.

### Acting Rationally

#### Intelligent Agents (IA)

graph TB
    env -- Percepts --> Sensors
    subgraph Agent
    Sensors --> ?
    ? --> Actuators
    end
    Actuators -- Actions --> env

#### Rationality

> 根據agent所接收到的東西，一個rational agent應該要俊所接收到的資訊及其內建的知識，選擇能做出最大表現(performance)的動作

#### task environment

##### PEAS

* ==P==erformance
* ==E==nvironment
* ==A==ctuators
* ==S==ensors

##### Fully/partially observable

* 圍棋/暗棋

##### single/multi agent

+ single: crossword puzzle
+ multiple: 互相下棋對戰的 agent A, agent B

##### deterministic/stochastic

* 圍棋/大老二

##### Episodic/sequential

* 和前狀態不相關/相關

##### static/dynamic

* 隨時間不變化/變化
* dynamic: text driving
* static: crossword puzzle

##### Discrete/continuous

##### Known/unknown

* 知道該怎麼行動效益最好

#### IA Behavior

* Perception (sequence) to Action Mapping
* Performance measure
* (degree of) Autonomy
* 自治性（自理）
* 不可能在開始時完全自理

#### IA Types

* Reflex agents
* if-then
* Reflex agents with internal states
* 知道下一步會發生什麼事
* Goal-based agents
* 有目標性
* Utility-based agents
* utility function: 內部版的preformance measure
* 會看這麼做會有多大的效益
* Learning agents
* 評斷接收及行動效能，學習agent要有的效能

## 3. Problem Solving & Search

### Problem

* States
* Initial state
* Actions
* Transition model
* Goal test
* Path cost

#### Solution

* A sequence of actions from the initial (or current) state to the goal state

### Searching

#### Performance

* Completeness
* 有解的話，一定找得到嗎？
* Optimality
* 有找到最佳解嗎？
* Time complexity
* Space complexity

### Uninformed search

#### bfs

graph TB
    a --> b
    a --> c
    b --> d
    b --> e
    c --> f
    c --> g

FIFO
a->b->c->d->e->f->g

* Completeness
* Yes
* Optimality
* Yes
* Time complexity
* $b+b^2+b^3+...+b^d$
* $O(b^d)$
* Space complexity
* $O(b^d)$

#### ucs

graph TB
    f --211--> b
    s --80--> r
    s --99--> f
    r --97--> p
    p --101--> b

s --> b

1. s->r:80 s->f:99
2. s->r->p:80+97=177
3. s->f->b:99+211=310
4. s->r->p->b:177+101=278

#### dfs

graph TB
    a --> b
    a --> c
    b --> d
    b --> e
    c --> f
    c --> g

LIFO
a->b->d->e->c->f->g

* Completeness
* No
* Optimality
* No
* Time complexity
* $O(b^m)$
* m: maximum depth of any node
* Space complexity
* $O(bm)$

#### Depth-limited Search

DFS with depth limit

#### Iterative Deepening Search

先在depth = 1做dls，depth = 2做dls，以此類推

#### Bidirectional Search

Both searches forward from initial state, and backwards from goal.

### informed search

#### best-first search

每次都只考慮到目標最短的節點

f(n) = h(n)

#### A*

best-first search的延伸，不只考慮未來還考慮現在

f(n) = g(n) + h(n)

### memory-bounded

#### iterative-deepening A*(IDA*)

cutoff: g + h

#### Recursive BFS

* aim to use O(n) space
* 類似$\alpha-\beta$ purning，紀錄最好的子節點，回傳給父節點，可以移去不必要的部份

#### Heuristic function

* admissable: 不可多估計
* In A\* : 尤拉距離、歐氏距離

## 4.Beyond classical search

### Local Search

#### Hill-climbing

* 找最斜的(斜率絕對值最大的)

#### Simulated annealing

* 加上隨機因子，以離開區域最小值

#### Local beam search

* 等同在山坡上撒很多球
* 去找最小（大）值的那顆

#### Genotic algo

* Initial population
* Fitness function
* Selection
* Crossover
* Mutation
* 

## 5. Adversarial search

### Games

* search tree very large
* **Purning**
* evaluation function
* Abstraction
* Accessible environments
* Search
* Complexity
* Unpredictable opponent

#### Abstraction

* inital state $S_0$
* PLAYER(s)
* ACTIONS(s)
* RESULT(s, a)
* TERMINAL-TEST(s)
* UTILITY(s, p): so-called payoff function
* 贏的回報狀況。零和遊戲為$\frac{1}{2} + \frac{1}{2}$

#### Optimal decisions

##### Minimax

Minimax(s) =

​ Utility(s), if TERMINAL-TEST(s)

​ $max_{a\in Actions(s)}Minimax(Result(s, a))$, if PLAYER(s) = MAX

​ $min_{a\in Actions(s)}Minimax(Result(s, a))$, if PLAYER(s) = MIN

* complete and optimal
* time: $O(b^m)$
* space: O(m)

##### Alpha-Beta purning

先幫節點設定上下限，就可以不用檢驗部份節點

* 所有值皆界在$\alpha$和$\beta$間，$\beta$是用來更新Minimize node的最佳，$\alpha$用來更新Maximize node的最佳。若$\alpha >= \beta$或$\beta <= \alpha$皆是不合理的結果，因此可以不用繼續搜尋

#### Imperfect real time decisions

大部分遊戲中是無法直接搜尋到樹的底端的，可以用其他更快的方式估計

##### Evaluation function

EVAL(s) = $w_1f_1(s)+w_2f_2(s)+...=\sum^{n}_{i=1}w_if_i(s)$

ex:

井字遊戲下中間有80%會贏，15％會輸，5％平手

EVAL(s) = 0.8x1 + 0.15x(-1) + 0.05x0 = 0.65

##### Cutoff-test

TERMINAL-TEST -> **if** CUTOFF-TEST(*state*, *depth*) **then return** EVAL(*state*)

### Stochastic Game

Minimax。改

<img src="https://imgur.com/OVcqCQd.jpg" width="60%">

從所有可能中挑最大機會的

ex:

<img src="https://imgur.com/BvYrl4I.jpg" width="60%">

## 6. Constraint Satisfaction Problems

### Define CSP

#### Ex: Map coloring

##### Constraint graph

graph LR
	WA ---- NT
	NT ---- Q
	WA ---- SA
	SA ---- Q
	NT ---- SA
	SA ---- NSW
	Q ---- NSW
	SA ---- V
	NSW ---- V
	T

X = {WA, NT, Q, NSW, V, SA, T}

C = {$SA\ne WA, SA\ne NT, SA\ne Q, ..., NSW\ne V$} => eg. binary CSP

#### Variations

* discrete/continuous
* finite/infinite

#### Constraint

* unary, binary ...
* global:
* ex: alldiff，對任意數量的變數限制

### Inference in CSP

> A variable in a CSP is **arc-consisitent** if every value in its domain satisfies the variable's binary constraints

#### Arc consistency

ex: Map coloring

(SA, WA) => {(red, green), (red, blue), (green, red), (green, blue), (blue, red), (blue, green)}

#### AC-3 algo

逐一測試每個($X_i, X_j$)，看在定義域有沒有符合的，如果沒有就代表inconsistency

<img src="https://imgur.com/V6kzyGb.jpg" width="60%">

#### Path consistency

因為arc的限制，進一步限制周圍的其他arc，稱為path

ex: 2 color mapping

{WA, SA} and NT

=> {WA = blue, SA = red} or {WA = red, SA = blue}

NT can be neither blue nor red

=> unsatisfiable

#### backtracking

利用遞迴的方式，加進assignment後檢查有沒有符合條件，有就繼續遞迴，沒有的話跳回上層遞迴其他子節點

<img src="https://imgur.com/KSXSjnd.jpg" width="60%">

問題：怎麼找出下一個值？怎樣會最好？

#### value ordering

* 找最多限制的：minimum-remaining-value(MRV) => 用在開始時
* 找最少限制的：least-constraining-value => 用在第二個變數之後

#### Forward checking

* 根據現在的決定去維持新的arc consistency

| | WA | NT | Q | NSW | V | SA | T |
| --------- | -------- | ---- | -------- | ---- | -------- | ---- | ---- |
| init | RGB | RGB | RGB | RGB | RGB | RGB | RGB |
| WA = red | choose R | GB | RGB | RGB | RGB | GB | RGB |
| Q = green | choose R | B | choose G | RB | RGB | B | RGB |
| V = blue | choose R | B | choose G | R | choose B | | RGB |

#### Intelligent backtracking

在前面的backtracking中，如果出問題會跳回前一個變數，但前一個變數不一定跟出現的問題有關

sol:

* 追縱會造成衝突的集合(conflict set)
* 回跳(backjumping)到該狀態

**notice:**

* 在forward checking時，就可以直接追蹤到conflict set（在每次刪除變數的時候）

* 而實際上，backjumping本身就只在衝突發生時啟動，而forward checking則是已經主動避開衝突

在未定義完全部的狀況前，如果已定義的就有產生衝突，則也不必繼續嘗試，此類型稱為conflict-directed backjumping

### Local search for CSP

#### Min-conflict

在尋找新的值的時候，盡量去選擇衝突最少的那個位置，同第4章講的local search

<img src="https://imgur.com/Zo7Tmhb.jpg" width=60%>

#### other technique: constraint weighting

* 給每個constraint各一個weight，初始值為1
* 每次都挑出一組var/value pair，使得weight最小
* 接著提高會違反限制的assignment的weight

## 7. Logical agent

CSP沒有通用的表示可以表示所有不同種類的問題

=> logic support lnowledge-based agents

* propositional logic
* first-order logic

### 7.1 Knowledge-based agents

* **TELL** KB what it perceives
* **ASK** KB what should perform
* **TELL** KB which action was chosen
* agent do action

two type:

* declareative: 一步一步教，直到agent知道要怎麼做出對應的動作
* procedural: 把希望要有的行為直接寫進程式裡

### 7.2 the wupus world

<img src="https://imgur.com/QOzhTFn.jpg" width="30%">

### 7.3 Logic

$\alpha$ is true in model m => m is a model of $\alpha$

$M(\alpha)$ : the set of all models of $\alpha$

#### Entailment

> A ⊨ B => 陳述句子集合**A**語義上蘊涵句子集合**B**。
>
> <img src="https://upload.wikimedia.org/wikipedia/commons/d/d6/Venn_A_subset_B.png">

def:

$\alpha ⊨ \beta$ iff $M(\alpha) \subseteq M(\beta)$

ex:

x = 0 ⊨ xy = 0，因為 M(x=0) $\subseteq$ M(xy=0)

note : xy=0 means x=0 **or** y=0

=> x=0 is stronger than xy=0

=> $\alpha$ is stronger than $\beta$

#### Inference

> A ⊢ B => 陳述句子集合**A**邏輯蘊涵句子集合**B**。它可以讀作"B可以證明自A"

#### Soundness

* An inference algorithm that **derives only entailed sentences** called sound or truthpreserving

#### completeness

* a algorithm can derive any sentence that is entailed

#### grounfing（落地化）

* 連結現實與邏輯世界

### 7.4 proposition logic

same as in discrete math

#### simple KB

利用推理的方式去推出特定格子是否可以走

#### Entails check

<img src="https://imgur.com/fwP0qpW.jpg" alt="2021-04-26 18.59.41" style="zoom: 33%;" />

TT-ENTAILS? means can truth table entail?

* 逐一確認每個變數是True或是False的狀況，直到result為空
* 看KB ⊨ $\alpha$ 是否成立

### 7.5 Propositional theorem proving

* $\alpha \equiv \beta$ iff $\alpha ⊨ \beta$ and $\beta ⊨ \alpha$
* For any sentences $\alpha$ and $\beta$, $\alpha⊨\beta$ iff ($\alpha \Rightarrow \beta$) is valid

#### satisfiability

> 歸謬法即由此而來

$\alpha ⊨ \beta$ iff ($\alpha \wedge \neg \beta$) is unsatisfiable

#### Inference rules

##### Modus Ponens

$\frac{\alpha \Rightarrow \beta, \alpha}{\beta}$

means: whenever any sentences of the form $\alpha \Rightarrow \beta$ and $\alpha$ is given, then $\beta$ can be infered

##### And-Elimination

$\frac{\alpha \wedge \beta}{\alpha}$

$\alpha \wedge \beta$ is true, then $\alpha$ is true and $\beta$ is true

##### resolution rule

$\frac{\alpha \vee \beta, \neg \alpha \vee \theta}{\beta \vee \theta}$

同項的正負的可以以消去，基本跟邏設的概念一樣

##### Conjunctive normal form

>把所有不是and or not的化成只剩and or not，基本上就是化成POS格式(Product of Sum)

ex:

$B_{1,1} \Leftrightarrow (P_{1,2} \vee P_{2,1})$

=>

$(\neg B_{1,1} \vee P_{1,2} \vee P_{2,1}) \wedge (\neg P{1,2} \vee B_{1,1}) \wedge (\neg P_{2,1} \vee B_{1,1})$

#### Resolution algorithm

<img src="https://imgur.com/wRw23xI.jpg" style="zoom: 33%">

演算法停止點：

1. 沒有新的clauses能再被新增，代表 KB 沒有 entail $\alpha$
2. 一對clauses解出空集合，代表 KB entail $\alpha$

#### ground resolution theorem

> if a set of clauses is unsatisfiable, then resolution closure of those clauses contains the empty clause.

#### forward chaining

前遞移律，透過一系列的imply來達到最終的結果

ex:

P => Q

$L \wedge M$ => P

$B \wedge L$ => M

$A \wedge P$ => L

$A \wedge B$ => L

A

B

最終可以推得Q

#### backward chaining

後遞移律，推回到先決條件為止

### 7.6 model checking

#### complete backtracking

* early termination:
* 找到必為True或False的就返回
* 可以節省很多搜尋空間的成本
* Pure symbol heuristic:
* 檢查有沒有pure symbol（那種整個model都是同號的變數）
* 設成True
* Unit clause heuristic:
* 只有單變數的，可以直接設定使其變成True

#### Local search

##### walkSAT

每個iteration隨機找一個clause，且有一定機率做 filp random symbol 或是找 min-conflict

note:

overconstrained: number of clauses >> number of variables，容易造成無解