# Artificial Intelligence Exam 2019
###### tags: `Exam`

## 1. Properties of Search Algorithm
Which of the following search algorithms is guaranteed to find the optimal solution?
* **Uniform Cost Search:** is optimal
* **Breadth-First Search:** BFS is optimal only if cost is constant (the same for all actions); not optimal in general: it finds the solution with the shortest path
* **Depth-First Search:** DFS is not optimal: will find “left-most” solution, not cheapest one
* **Iterative Deepening Depth-First Search:** is optimal - like BFS
* **Greedy Best-First Search:** Not optimal (heuristic may lead search to suboptimal solution first)
* **$A^{*}$ Search:** If A* search is given a heuristic function $h(n)$ that is admissible, then $A^{*}$ search is optimal. If the heuristic function is admissible, meaning that it never overestimates the actual cost to get to the goal, $A^{*}$ is guaranteed to return a least-cost path from start to goal.

---

## 2. Logical Inference

- Conversion KB to CNF:
(A <=> B) ∧ (B => C) ∧ A
(A => B) ∧ (B => A) ∧ (¬B ∨ C) ∧ A
(¬A ∨ B) ∧ (¬B ∨ A) ∧ (¬B ∨ C) ∧ A

We want to proof KB entails C so, apply resolution rule to CNF ∧ ¬C

- Proof:
from (¬A ∨ B) and (¬B ∨ C) follows (¬A ∨ C)
from (¬A ∨ C) and (A) follows C
from C and ¬C follows a contradiction

So, C follows logically from KB

---

## 3. Probability and Bayesian Networks

a) $P(c)\cdot P(\neg s |c)\cdot P(\neg r|c)\cdot P(w|\neg r \land \neg s) = 0.5\cdot 0.9\cdot 0.2\cdot 0.01 = 0.0009$


b)

$\alpha = \frac{1}{P(r,s)}$

$\alpha\dot (P(C,r,s,w)+P(C,r,s,\neg w))$

$P(\mathbf{X}|e) = \alpha P(\mathbf{X},e)=\alpha \sum_yP(X,e,y)$


c) NEIN


d)2^4. Why would it make sense to sample more events than are possible?

---
## 4. Concept Learning via Logistic Regression

a) The loss function for the logistic regression is the Binary Cross Entropy.

b) The output is between 0 and 1 and it can be interpreted as a probability for each class. If we want to have a decision, then we introduce a threshhold at $\hat{y}=0.5$


---
## 5. Reinforcement Learning

a) For some path (not optimal) we get:$\pi(A)=B, \pi(B)=D, \pi(D)=C \implies V^*(A)=60+60\cdot0.5+60\cdot0.25=105$

If we look at the optiam path (A->B->A->B->...) we get:
$\pi(A)=B, \pi(B)=A \implies V_\pi=60\sum_{t=0}^\infty0.5^t >105$



b) $r=60$

$\max_{a'\in\cal{A}}Q[B,a'] = 10$

$Q[A,\rightarrow] \leftarrow 60 + 0.5 \cdot 10 = 65$