Part 1

a) Construct a neural network

Inputs $I_{1}, I_{2}$

Outputs $O_{1}, O_{2}, O_{3}$

You can also draw a separate network for every output.

$\begin{array}{c|c||c|c|c}I_{1} & I_{2} & O_{1} & O_{2} & O_{3} \\\hline 1 & 1 & 1 & 1 & 1 \\1 & 0 & 0 & 0 & 0 \\0 & 1 & 1 & 1 & 0 \\0 & 0 & 0 & 1 & 1\end{array}$

Activation function:

$g(x)=\left\{\begin{array}{ll}1 & \text {if ~} \frac{1}{3} \cdot x \geq 2 \\0 & \text {otherwise }\end{array}\right.$

b) Explain goal-based agents - in what way are they different from utility-based agents?

3. Goal-based agents

Add on: explicit goals , ability to plan into the future, model outcomes for predictions

• model the world , goals, actions and their effects explicitly

• more flexible, better maintainability

• Search and planning of actions to achieve a goal

4. Utility-based agents

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

c) Explain the terms uninformed search, overfitting, activation function and deep learning.

Uninformed search

basic algorithms, no further information about solution costs (heuristics)

Overfitting

When the learned function fitted itself to the training set - but does not generalize well anymore

Tradeoff between complexity and simplicity

precision, fitting training data vs. generalizing, finding patterns

complex hypotheses - fit the data well vs. simpler hypotheses- might generalize better

Overfitting

The DTL algorithm will use any pattern it finds in the examples even if they are not correlated.

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

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

Activation function

The function that defines when the (mathematial model of a) neuron-unit fires.

It uses a threshold, linear or logistic function on the weighted sum of all inputs.

Where $g$ is an activation function :

Deep learning

Hierarchical structure learning: NNs with many layers

Feature extraction and learning (un)supervised

Problem: requires lots of data

Push for hardware (GPUs, designated chips): “Data-Driven” vs. “Model-Driven” computing

d) Multiple choice

1. Local beam search amounts to a locally confined run of $k$ random-restart searches. ✅

Idea keep $k$ states instead of just $1$

Problem often, all $k$ states end up on same local hill

Solution choose $k$ successors randomly, biased towards good ones

2. Neural networks are generally bad in object recognition. ❌

No - they are particularly good at it.

3. A rational agent does not necessarily always select the best possible action. ✅

Being rational does not mean being:

4. A game of poker is a discrete environment ✅

discrete vs. continuous

e) Construct a decision Tree

A decision tree uses the following example set:

$\begin{array}{c||c|c|c|c} & A & B & C & \text { Output } \\\hline 1 & a_{1} & b_{1} & c_{2} & T \\2 & a_{2} & b_{1} & c_{1} & F \\3 & a_{2} & b_{2} & c_{2} & T \\4 & a_{2} & b_{3} & c_{1} & F \\5 & a_{2} & b_{3} & c_{1} & T \\6 & a_{2} & b_{3} & c_{1} & T \\7 & a_{2} & b_{3} & c_{2} & F \\8 & a_{1} & b_{2} & c_{2} & T\end{array}$

Construct a decision tree from the given data, using the algorithm from the lecture. The next attribute is always chosen according to the predetermined order:$A, B, C$ . Which special case occurs? How does the algorithm deal with it?

We have a predefined order, therefore we do not have to calculate the importance of each attribute individually.

The domains of these attributes:

/*
- examples: (x, y) pairs
- attributes: attributes of values x_1, x_2, ... x_n in x in example
- classification: y_j = true / false
*/function DTL(examples, attributes, parent_examples) returns a decision tree
if examples is empty then return MAJORITY(parent_examples.classifications)
else if all examples have the same classification then return the classification
else if attributes is empty then return MAJORITY(examples.classification)
else
A = empty
for each Attribute A' do
A ← maxImportance(A, A', examples)tree ← a new decision tree with root test Afor each (value v of A) do //all possible values from domain of A
exs ← {e : e ∈ examples | e.A = v} //all examples where this value occured
subtree ← DTL(exs, attributes\{A}, examples) //recursive call
add a new branch to tree with label "A = v" and subtree subtreereturn tree

The algorithm is recursive, every sub tree is an independent problem with fewer examples and one less attribute.

The returned tree is not identical to the correct function / tree $f$ . It is a hypothesis $h$ based on examples.

• in depth explaination

  1. no examples left

     then it means that there is no example with this combination of values → We return a default value: the majority function on examples in the parents.

  2. Remaining examples are all positive or negative

     we are done

  3. no attributes left but both positive and negative examples

     These examples have the same description but different classifications, we return the plurality-classification (Reasons: noise in data, non determinism)

  4. some positive or negative examples

     choose the most important attribute to split and repeat this process for subtree

In this special case using this predefined order: we have no attributes left but both positive and negative examples .

f) Search problem - A* Search

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

Starting node $S$

Goal node $G$

$h(S)=10,\\ h(a)=7, \\h(b)=8,\\ h(c)=5,\\ h(d)=3, \\h(e)=2,\\ h(f)=2, \\ h(h)=0,\\ h(G)=0$

If I marked it grey, that means its from another step.

Were using a graph search algorithm with an explored set.

This is the explored set (seen in the correct order): $\text{explored}=\{S,a,e,c,f,g\}$

g) Describe how hill climbing functions. Which problem can occur? Whats the solution to it?

Also called "hill-climbing":

Solution: Random-restart hill climbing: restart after step limit overcomes local maxima

• Pseudocode

  function HILL-CLIMBING(problem) returns a state that is a local maximum
  inputs: problem // a problem
  local variables:
  current, // a node
  neighbor // a node
  current ← MAKE-NODE(INITIAL-STATE[problem])
  loop do
  neighbor ← a highest-valued successor of current
  if VALUE[neighbor] ≤ VALUE[current] then return STATE[current]
  current ← neighbor

h) DFS vs. IDS - are they optimal with infinite branching factors?

They still must terminate at some point even with infinite branches, since they use a stack as their frontier-set data-structure.

They explore the tree in its full depth first before continuing with its breadth.

3) Depth-first search DFS

Fronier as stack.

Much faster than BFS if solutions are dense.

Backtracking variant: store one successor node at a time - generate child node with $\Delta$ change.

completeness No - only complete with explored set and in finite spaces.

time complexity$O(b^m)$ - Terrible results if $m \geq d$ .

space complexity$O(bm)$

solution optimality No

4) Depth-limited search DLS

DFS limited with $\ell$ - returns a $\text{cutoff}$ subtree/subgraph.

• Pseudocode

  function DEPTH-LIMITED-SEARCH(problem, limit) returns a solution, or failure/cutoff
  return RECURSIVE-DLS(MAKE-NODE(problem.INITIAL-STATE), problem, limit)function RECURSIVE-DLS(node, problem, limit) returns a solution, or failure/cutoff
  if problem.GOAL-TEST(node.STATE) then return SOLUTION(node)
  else if limit = 0 then return cutoff
  else
  cutoff occurred? ← false
  for each action in problem.ACTIONS(node.STATE) do
  child ← CHILD-NODE(problem, node, action)
  result ← RECURSIVE-DLS(child, problem, limit − 1)
  if result = cutoff then cutoff occurred? ← true
  else if result != failure then return result
  if cutoff occurred? then return cutoff else return failure

completeness No - May not terminate (even for finite search space)

time complexity$O(b^\ell)$

space complexity$O(b\ell )$

solution optimality No

5) Iterative deepening search IDS

Iteratively increasing $\ell$ in DLS to gain completeness.

• Pseudocode

  function ITERATIVE-DEEPENING-SEARCH(problem) returns a solution, or failure
  for depth = 0 to ∞ do
  result ← DEPTH-LIMITED-SEARCH(problem, depth)
  if result 6= cutoff then return result

completeness Yes

time complexity$O(b^d)$

space complexity$O(bd)$

solution optimality Yes, if step cost ≥ 1

Part 2

a) Cryptographic puzzle as a CSP

  E G G
+ O I L
-------
M A Y O

Defined as a constraint satisfaction problem:

Constraints:

b) 3-color-problem and backtracking-search heuristics

Least constraining value

Partial assignment: $1=\text {green}, 2=\text {red}$

Question: Which value would be assigned to the variable $3$ by the least-constraining-value heuristic?

Answer: $3=\text {red}$

Minimum remaining values

Partial assignment: $2=\text {blue, } 5=\text {red }, 7=\text {green}$

Question: Which variable would be assigned next using the minimum-remaining-values heuristic?

Answer $4$

Degree heuristic

Question: Which variable would be assigned a value from its domain first by the degree heuristic?

Answer: $4$

Explanation

Variable ordering: fail first

Value ordering: fail last

c) Multiple Choice

1. A CSP can only contain binary constraints ❌

Backtracking search algorithm

Depth-first search with single-variable assignments:

2. The backtracking search is an uninformed search algorithm. ✅

3. The axiom of continuity is: $A \succ B \succ C \Rightarrow \exists p[p, A ; 1-p, B] \sim C$ ❌

The right answer would be $A \succ B \succ C \Rightarrow \exists p\space[p, A ; 1-p, C] \sim B$

d) Axiom of monotonicity from utility theory

Monotonicity

e) Multiple Choice

1. Classical planning environments are static ✅

Classical Planning Environments

Used in classical planning:

2. $\exists x \operatorname{Meets}(x, b o b)$ is syntactically correct in STRIPS ❌

No, STRIPS does not support quantors.

3. Unlike STRIPS, ADL supports equality ✅

4. In partial order planning, the constraint $A \prec B$ means that $A$ must be executed immediately before $B$ ❌

It means that $A$ must be executed some time before $B$ .

f) Formalizing a STRIPS action

$\text{Action}(AttendingMeeting(emp, room)$