Exam on 2012-07-06

TU_Wien_Einfhrung_in_die_Knstliche_Intelligenz_VU_(Eiter_Tompits)_Prfung_2012-07-06_-_VoWi.pdf

1. Construct a neural network

boolean equivalence function $\Leftrightarrow$

Activation function:

$g(x)=\left\{\begin{array}{ll}1 & \text { if } x \geq 1, \\0 & \text { otherwise }\end{array}\right.$

2. Explain neuron units

Mathematical Model of Neuron

McCulloch and Pitts (1943)

The inputs stay the same, only the weights are changed.

Each unit has a dummy input $a_0 = 1$ with the weight $w_{0,j}$ .

The unit $j$ 's output activation $a_j$ is

aj=g(inj)=g(∑i=0nwi,jai)a_j = g(in_j) = g\biggl( \sum_{i=0}^n w_{i,j}a_i \biggl)aj=g(inj)=g(i=0∑nwi,jai)

Where $g$ is an activation function :

perceptron hard threshhold $g(x)=\left\{\begin{array}{ll}1 & \text { if } x \geq 0 \\0 & \text { otherwise }\end{array}\right.$

sigmoid perceptron logistic function $g(x) = \frac{1}{1+e^{-x}}$

3. Explain overfitting and ways to avoid it

Overfitting

The learn-algorithms will use any pattern they find in the examples even if they are not correlated.

Then the algorithm fits itself to the training examples and does not generalize well.

$\uparrow$ likelyhood of overfitting if $\uparrow$ hypothesis space, $\uparrow$ number of inputs

$\downarrow$ likelyhood of overfitting if $\uparrow$ examples.

To combat overfitting we therefore must:

use more training examples

reduce the hypothesis space size and the number of irrelevant inputs

Combating overfitting: in decision trees

Decision tree pruning

Combats overfitting, eliminates nodes that are not clearly relevant after tree got generated.

How do we detect nodes that test an irrelevant attribute?
Imagine being at a node with $p_k$ positive and $n_k$ negative examples, if the attribute is irrelevant we would expect it to split the examples into subsets that have roughly the same proportion of positive examples as the whole set.
pkpk+nk≈pp+n\frac{p_k}{p_k+n_k} \approx \frac{p}{p+n}pk+nkpk≈p+np

Splitting after sufficient information gain

Now we know what amount of gain is insufficient, but what information gain is suffucient for splitting on a particular attribute? → statistical significance test .

4. Explain the activation function, define 2 of them and sketch them out

Determine a threshhold, that makes the neuron fire if it is reached.

We use:

step function / hard limiter

linear function / treshold function

sigmoid function

5. Define consistency

Every consistent heuristic is also admissible. Consistency is stricter than admissibility.

Implies that $f$ -value is non-decreasing on every path .

For every node $n$ and its successor $n'$ :

$h(n) \leq c(n,a,n') + h(n')$

This is a form of the general triangle inequality.

$f$ is then non-decreasing along every path:

$f(n') = g(n') + h(n')= g(n) + {c(n, a,n') + h(n')}$

$f(n') = g(n) + \textcolor{pink}{c(n, a,n') + h(n')} \geq g(n) +\textcolor{pink}{ h(n)} = f(n)$ (because of consistency)

$f(n') \geq f(n)$

6. Explain rational agents

Being rational does not mean being:

omniscient (knowing everything) percepts may lack relevant information

clairvoyant (seeing into the future) predictions are not always accurate

successful (ideal outcome)

Rational agent

Chooses action that maximizes utility (measured with performance / success measure) for any percept sequence.

Decisions based on evidence:

percept history

built-in knowledge of the environment - ie. fundamental knowledge laws like physics

7. STRIPS vs. ADL

STRIPS

only positive literals in states

closed-world-assumption: unmentioned literals are false

Effect $P \wedge \neg Q$ means add $P$ and delete $Q$

only ground atoms in goals

Effects are conjunctions

No support for equality or types

ADL

positive and negative literals in states

open-world-assumption: unmentioned literals are unknown

Effect $P \wedge \neg Q$ means add $P$ and $\neg Q$ delete $Q$ and $\neg P$

goals contain $\exists$ quantor

goals allow conjunction and disjunction

conditional effects are allowed: $P:E$ means $E$ is only an effect if $P$ is satisfied

equality and types built in

8. Explain all algorithms from uninformed search

Uninformed Search

9. Explain the utility based agents components

Add on: take happiness into account (current state) → Humans are utility-based agents

assess goals with a utility function (maximizing happiness, concept from micro-economics)

resolve conflicting goals - goals are weighted differently, the aim is to optimize a set of values

use expected utility for decision making

10. Constraint graph

Constraint graph

Can only be used for binary CSPs (only have binary constraints)

11. CSP heuristics for backtracking search

Variable ordering: fail first

Minimum remaining (legal) values MRV

degree heuristic - (used as a tie breaker), variable that occurs the most often in constraints

Value ordering: fail last

least-constraining-value - a value that rules out the fewest choices for the neighbouring variables in the constraint graph.

12. Forward checking

Forward checking

During search: Adapt domains of all nodes, connected to the value of this one (in constraint graph).

Forward checking does not provide early detection for all inconsistencies:

It only checks arc consistency for the currently chosen node and its neighbours.

Constraint Propagation

Propagating the meaning of a constraint on one variable onto other variables.

The simplest form: Arc (= binary constraint) Consistency between nodes in a constraint graph.

Two connected nodes $X,Y$ are consistent iff for every value $x$ of $X$ there is some allowed value $y$ of $Y$ .

13. Explain the POP algorithm

Defines execution order of plan by searching in the space of partial-order plans.

Returns a consistent plan : without cycles in the ordering constraints and conflicts in the casual links.

Initiating empty plan
only contains the actions:
$\text{Start}$ no preconditions, effect has all literals, all preconditions are open, no casual links
$\text{Finish}$ has no effects, no open preconditions
ordering constraint: $\text { Start} \prec \text {Finish}$
no casual links

Searching
2.1 successor function: repeatedly choosing next possible state.
Chooses an open precondition $p$ of action $B$ and generates a successor plan (subtree) for every consistent way of choosing an action $A$ that achieves $p$ .
2.2 enforce consistency by defining new casual links in the plan:
$A \stackrel{p}{\longrightarrow} B, \space A \prec B$
If $A$ is new: $\text{Start} \prec A \prec\text{Finish}$
2.3 resolve conflicts
add $(B\prec C) \wedge (C\prec A)$
2.4 goal test
because only consistent plans are generated - just check if preconditions are open.
If goal not reached, add successor states

14. Explain all types of state space search algorithms

Totally ordered plan searches

Variants:

progression planing: initial state $\rarr$ goal

regression planing: initial state $\larr$ goal
(possible because of declarative representation of PDDL and strips)

Partial-order Planning

Order is not specified: can place to actions into a plan without specifying which one comes first.

Search in space of partial-order-plans.