• Artificial Intelligence
  • ethics
    • codes of ethics
    • engineering design process
    • handling ethical issues
  • definition of artificial intelligence
    • Turing test
      • total Turing test
    • thinking humanly
    • thinking rationally
    • knowledge-based system
  • intelligent agent
    • rational agent
    • task environment
    • agent structure
      • table-driven structure
      • simple reflex agent
  • search
  • example application
    • collaborative perception
    • anomaly detection
    • uninformed search
      • breadth-first search
      • uniform-cost search
      • informed search (heuristic search)
      • A* search (A-star search)
  • reinforcement learning
    • dynamic programming
    • discrete Markov decision process (discrete MDP)
      • find optimal policy
    • continuous Markov decision process (continuous MDP)
      • inverted pendulum
      • discretization
      • value function approximation
      • Mealy machine MDP
      • finite horizon MDP
      • policy searching method
    • partial observable MDP
      • reinforce with baseline
    • Monte Carlo method
    • time-difference learning (TD-learning)
      • on-policy TD (SARSA)
      • off-policy TD: Q-learning

Artificial Intelligence

most supervised learning when ppl talk about

ethics

• Mill’s utilitarianism: maximize benefit for everyone, mostly equally

  bane:

  • conflict of interest
  • personal benefit

• Kant’s formalism/ duty ethics: unconditional command for every individual

  bane: universal principle may harm specific people

• Locke’s Right Ethics: individual has right simply by existence

  bane: what to do when two people’s rights conflict

• Aristotle’s virtue ethics: objective goodness from human qualities

  bane: how to find the “golden mean”

the golden rule (all above agrees with)

Do unto others as you would have others do unto you

codes of ethics

statements of general principles, followed by instructions for specific conduct

defiens duties the professional owes to society/employers/clients/colleagues/subordinates/profession/self

engineering design process

1. recognize problem/need, gather information
2. define problem/goal
3. generate/propose solution/method
4. evaluate benefit&cost of alternatives

handling ethical issues

1. correct the problem
2. whistle blowing
3. resign in protest

definition of artificial intelligence

• humanly → acting
• ration → math/theory

Turing test

• NLP
• knowledge representation
• automated reasoning
• ML

total Turing test

perceptional abilities

• computer vision
• robotics

thinking humanly

• get inside the working of human mind
• general problem solver
• cognitive science

thinking rationally

• correctness
• logic
• fact-check

knowledge-based system

• general-purpose search
• domain-specific knowledge
• knowledge bottleneck

intelligent agent

rational agent

1. prior knowledge of environment
2. performable action
3. performance measurement
4. perception

task environment

PEAS: performance measurement, environment, actuators, sensors

properties

1. fully/partially observable
2. single/multiple agent
3. deterministic/stochastic
4. episodic/sequential
5. static/dynamic
6. known/unknown

agent structure

• function: perception → action
• architecture: sensory → actuator

table-driven structure

$$n_{entry}=\sum _{t=1}^T|P{|}^T$$

• simplest
• e.g. industrial robot
• #cases explode

simple reflex agent

match input against rule, return action

• model-based: only work for fully observable
• goal-based
• utility-based: maximize gain expectation

search

• breadth/depth first

example application

collaborative perception

• share raw data → huge overhead
• extract feature
• share object position

anomaly detection

• bidirectional optimization

uninformed search

• backtracking search

breadth-first search

• complete: will find shallowest goal if graph has finite depth
• optimal if path cost $g(n)$ is non-decreasing of depth $d$
• $O(b^d)$ where $b$ is branching factor

uniform-cost search

expand node with least path cost $g(n)$

• optimal
• $O(b^{1+\lfloor C^{\ast }/ϵ\rfloor })$ where every action cost $\ge ϵ$

informed search (heuristic search)

A* search (A-star search)

• cost $f(n)=g(n)+h(n)$
  • cost to reach node $g(n)$
  • estimated cost to goal, heuristic, $h(n)$
• optimal if $h(n)$ is admissible in tree search
  • admissibility: never overestimate
• optimal if $h(n)$ is consistent in graph search
  • consistency: triangle inequality $h(n)\le c(n,a,n^{\prime })+h(n^{\prime })$
• optimally efficient if $h(n)$ is consistent: expand fewest node among optimal algorithm

reinforcement learning

• control system
• model-based vs model-free

dynamic programming

• key: sub-problem

example

• Dijkstra’s algorithm: per node
• Bellman-Ford algorithm: per hop

discrete Markov decision process (discrete MDP)

finite tuple $\{S,A,\{P_{sa}\},\gamma ,R\}$

• space $S$

• action $A$

• state transition probabilities $P_{sa}$

• discount factor $\gamma \in [0,1)$

• reward function $R$: evaluation metric

• total payoff. maximize this

  $$V=\sum _i{\gamma }^{i}R(s_i)$$

• policy $\pi :s\mapsto a$. find this

find optimal policy

optimal policy ${\pi }^{\ast }$

$${\pi }^{\ast }=\underset{a}{\mathrm{argmax}}\sum _{s^{\prime }}{P}_{sa}(s^{\prime })V^{\ast }(s^{\prime })$$

• mapping state to expected total payoff $V^{\pi }:s\mapsto \mathbb{R}$

  $$\begin{gathered} V^{\pi }(s)=\mathbb{E}\left[\sum _i{\gamma }^{i}R(s_i)|s_0=s\right]=\mathbb{E}\left[[R(s)]+\gamma V^{\pi }(s^{\prime })\right] \\ \Rightarrow V^{\pi }(s)=R(s)+\gamma \sum _{s^{\prime }}{P}_{s\pi (s)}(s^{\prime })V^{\pi }(s^{\prime }) \end{gathered}$$

  Bellman equation

value iteration

1. $V(s):=0$

2. Bellman update: $\forall s,$

   $$V(s):=R(s)+\underset{a}{\max }\gamma \sum _{s^{\prime }}{P}_{sa}(s^{\prime })V(s^{\prime })$$

• linear system
• Bellman back operator $V^{\prime }:=B(V)$
• sync/async update
• $\gamma$ force $V$ to converge $V^{\ast }$ exponentially

policy iteration

1. random $\pi$

2. repeat:

   $$\begin{gathered} V:=V^{\pi }\text{by Bellman equation} \\ \pi (s):=\underset{a}{\mathrm{argmax}}\sum _{s^{\prime }}{P}_{sa}(s^{\prime })V(s^{\prime }) \end{gathered}$$

• when converge, guarantee optimal policy
• high complexity: linear system very step

exploration and exploitation

• $\epsilon$-greedy

  $$a=\{\begin{array}{ll}\mathrm{argmax}V& probability1-\epsilon \\ randoma\in A& probability\epsilon \end{array}$$

  • $\epsilon$ is small and decrease

• softmax

continuous Markov decision process (continuous MDP)

$$V(s)=R(s)+\gamma \underset{a}{\max }{\mathbb{E}}_{s^{\prime }\sim P_{sa}}[V(s^{\prime })]$$

inverted pendulum

• kinematic model

discretization

• curse of dimensionality: $|S|={\mathbb{R}}^n$
• bad for smooth function

4 ~ 8 dimension

value function approximation

approximate $V^{\ast }$

$$V^{\ast }(s)={\theta }^T\varphi (s)$$

trial

1. model/simulator: $s^{\prime }\mapsto P_{sa}$

   • assume $A$ discrete

   $$s^{\prime }=s+\Delta t\dot{s}$$

2. learn from data

   • $n$ trial, each with $T$ time step
   • supervised learning $(s_t,a_t)\mapsto s_{t+1}$
     • linear regression $s_{t+1}=A{s}_t+B{a}_t,A\in {\mathbb{R}}^{m\times n},B\in {\mathbb{R}}^{n\times d}$
     • deterministic/stochastic model
       • noise term ${\epsilon }_t\in N(0,\epsilon )$
     • model-based reinforcement learning
     • fitted value iteration

fitted value iteration

approximate $V^{\ast }(s)$ from $s^{(i)},i\in \{1,\dots ,n\}$

1. trial: ramdomly sample $s^{(i)},i\in \{1,\dots ,n\}$

2. initialization: $\theta :=0$

3. repeat for $i\in \{1,\dots ,n\}$:

   1. repeat for $1\in A$:

      sample $s_i^{\prime }\sim P_{sa}^{(i)},i\in \{1,\dots ,k\}$

      $$q(a):=\frac{1}{k}\sum _{j=1}^k\left[R(s^{(i)})+\gamma V(s_j^{\prime })\right]$$

      is estimation of

      $$R(s)+\gamma {\mathbb{E}}_{s^{\prime }\sim P_{sa}}[V(s^{\prime })]$$

   $$y^{(i)}:=\underset{a}{\max }q(a)$$

any regression model, e.g.

$$\theta :=\underset{\theta }{\mathrm{argmin}}\sum _i{\left({\theta }^T\varphi (s^{(i)})-y^{(i)}\right)}^2$$

• for deterministic model, can set $k=1$

Mealy machine MDP

$R:S\times A\to \mathbb{R}$

Bellman equation:

$$\begin{gathered} V^{\ast }(s)=\underset{a}{\max }\left[R(s,a)+\gamma \sum _{s^{\prime }}{P}_{sa}(s^{\prime })V^{\ast }(s^{\prime })\right] \\ \Rightarrow {\pi }^{\ast }=\underset{a}{\mathrm{argmax}}\left[R(s,a)+\gamma \sum _{s^{\prime }}{P}_{sa}(s^{\prime })V^{\ast }(s^{\prime })\right] \end{gathered}$$

finite horizon MDP

• finite tuple $\{S,A,\{P_{sa}\},T,R\}$

• time horizon $T\in (0,+\infty )$

• maximize ${\sum }_{t=0}^{T}R(s_t,a_t)$

• action based on time ${\pi }_t^{\ast }$

• time-dependent dynamic

  $$\begin{gathered} V_t(s)=\mathbb{E}\left[\sum _{t^{\prime }=t}^{T}R(s_{t^{\prime }},a_{t^{\prime }})\right] \\ {V}_t^{\ast }(s)=\{\begin{array}{ll}\underset{a}{\max }\left[R^{(t)}(s,a)+{\mathbb{E}}_{s^{\prime }\sim P_{sa}^{(t)}}(V_{t+1}^{\ast }(s^{\prime }))\right]& t\in \{0,\dots ,T-1\}\\ \underset{a}{\max }\left[R^{(t)}(s,a)\right]& t=T\end{array} \end{gathered}$$

  • solution by dynamic programming: work way back from $V_T^{\ast }(s)$

linear quadratic regulation

• $S:{\mathbb{R}}^n,A:{\mathbb{R}}^d,n>d$

• linear transition with noise $P_{sa}$

  $$s_{t+1}=A{s}_t+B{a}_t+{\omega }_t$$

• negative quadratic reward to push system back
  $u_t:{\mathbb{R}}^{u\times n},v_t:{\mathbb{R}}^{n\times n},u_t,v_t\ge 0$

  $$R(s_t,a_t)=-s_t^T{u}_t{s}_t-a_t^T{v}_t{a}_t$$

policy searching method

• stochastic policy ${\pi }_{\theta }:S\times A\to \mathbb{R}$

• ${\pi }_{\theta }(s,a)$: probability of taking action $a$ at state $s$

• direct policy search: find reasonable $\theta$

  $$\underset{\theta }{\max }\mathbb{E}\left[\sum _{t=0}^{T}R(s_t,a_t)|{\pi }_{\theta }\right]$$

  • fixed initial state
  • greedy stochastic gradient ascent
  • learning rate $\alpha \in (0,1]$

repeat:

1. sample $s_t,a_t$

2. reinforce

   $$\theta :=\theta +\alpha \sum _t\left[\frac{{\nabla }_{\theta }{\pi }_{\theta }(s_t,a_t)}{{\pi }_{\theta }(s_t,a_t)}\right]\sum _{t}R(s_t,a_t)$$

reason it converge: product rule

partial observable MDP

reinforce with baseline

• arbitrary baseline $b(s)$
  • independent of $a$

$$\theta :=\theta +\alpha \sum _t\left[{\nabla }_{\theta }\ln {\pi }_{\theta }(s_t,a_t)\right](f(\tau )-b(s))$$

Monte Carlo method

• trial: $(s_t,a_t)$
• wait until end of episode return $G_t$
• $V(s_t):=V(s_t)+\alpha (G_t-V(s_t))$
• drawback: slow if episode long

time-difference learning (TD-learning)

at time $t+1$, update $V(s_t)$

$$V(s_t):=V(s_t)+\alpha ({\delta }_t)$$

• TD error ${\delta }_t$

  $${\delta }_t=R(s_{t+1})+\gamma V(s_{t+1})-V(s_t)$$

on-policy TD (SARSA)

• $\epsilon$-greedy

1. initialize arbitrary reward $Q(s,a)$
2. repeat for episode

   1. initialize $S$

   2. behavior policy: select $a_t$ based on $Q$

   3. repeat for each step

      1. select potential $a^{\prime }$ for $s^{\prime }$ based on $Q$

      2. update $Q(s,a)$

         $$Q(s_t,a_t):=Q(s_t,a_t)+\alpha \left[R(s_t)+\gamma Q(s_{t+1},a^{\prime })-Q(s_t,a_t)\right]$$

      3. $s:=s^{\prime }$

      until $s$ is terminal

off-policy TD: Q-learning

same as SARSA except

$$Q(s_t,a_t):=Q(s_t,a_t)+\alpha \left[R(s_t)+\gamma \underset{a}{\max }Q(s_{t+1},a)-Q(s_t,a_t)\right]$$

• greedy