TU Wien:Einführung in die Künstliche Intelligenz VU (Eiter, Tompits)/Prüfung 2012-10-02 Ausarbeitung

Fragen übernommen aus dem Informatik-Forum.

Planning

Write a STRIPS action

Drive(car, from, to)
PRECOND (at(car, from), car(car), Location(from), location(to))
EFFECT (at(car, to), not at(car, from))

What is a consistent plan? What is a solution?

A consistent plan is: A plan with no cycles in the ordering constraints and no conflicts with the causal links

A solution is: A consistent plan with no open preconditions

Describe the two possible ways in state space search

• progression planning (forward state-space search) - from initial state to goal

• regression planning (backward state-space search) - from goal to initial state

Multiple choice ADL/STRIPS

• Does ADL allow equality? - Yes

• Does STRIPS allow Conjunctions in goals? - Yes, but no disjunction.

Given a Lottery L, ...

A expected monetary value EMV(L) and Utility Function U(L), a risk-averse agent would

• prefere U(L) > U(S(EMV(L))
• prefere U(L) < U(S(EMV(L))

where S(EMV(L)) is the state of having money EMV(L).

Describe 3 Axioms of Utility theory: Orderability, Continuity and Monotonicity

• Orderability: Given any two lotteries, a rational agent cannot avoid deciding which one it prefers, or whether it is indifferent between them.
  • Exactly one of $(A\prec B),(B\prec A),(A\sim B)$ holds.
• Continuity: If some lottery B is between A and C in preference, then:
  • there is some probability p for which the agent will be indifferent between getting B for sure and the lottery that yields $A$ with probability $p$ and $C$ with probability $1-p$.
    • $A\prec B\prec C\Rightarrow \exists p[p,A;1-p,C]\sim B$
• Monotonicity: Suppose two lotteries have the same possible outcomes $A$ and $B$.
  • If an agent prefers $A$ to $B$, then the agent must prefer precisely the lottery that has a higher probability for outcome $A$.
  • $A\prec B\Rightarrow (p<q\Leftrightarrow [p,A;1-p,B]\prec [q,A;1-q,B])$

Describe the components of a decision network

• Chance nodes (ovals): represent random variables.
  • E.g., the agent is uncertain about construction costs, the level of air traffic, the potential for litigation.
  • There are also the Deaths, Noise, and Cost variables, depending on the site chosen.
  • Chance nodes are associated with a conditional probability distribution that is indexed by the state of parent nodes.
• Decision nodes (rectangles): represent points where decision maker has a choice of actions; e.g., the choice of an airport site influences the cost, noise, etc.
• Utility nodes (diamonds): represent the agent’s utility function.
  • It has as parents all variables describing the outcome that directly affect utility.

Searches

Admissible heuristics have a problem with graph search. Which? How can this be changed?

Even if h is admissible, A*-Search can reach goals in graph search with non optimal costs. To fix this problem we can change the algorithm and add complicated bookkeeping (might ruin run time) or impose a stronger restriction on h: consistence (f-value is non-decreasing on every path)

Learning from Observation

What is inductive learning?

Given a training set (x1, y1) ... (xn, yn) of examples find a function h that approximates f. h is then called hypothesis and must be from a restricted class of functions (hypothesis space). If h = f is possible then the learning problem is realizable. Consider Ockham's razor when creating this function "maximise simplicity under consistency"

What is a learning curve? Which correlation is described by it? Which two circumstances have negative effect on the learning curve?

% correct on test set as a function of training set size (x-axis: size of training set, y-axis: % correct on test set) Describes correlation between test set size and % of correct outcomes Depends on realizability (non realizable through missing attributes or too restrictive hypothesis space) and redundant expressiveness (due to loads of irrelevant attributes)

Describe a learning agent + diagram

learning element: make improvements

performance element: select external actions

critic: performance, result assessment

problem generator: suggest actions for new experiences

Advantages & Disadvantages of neural networks (or learning by observation)

PROs

• less need for determining relevant input factors
• inherent parallelism
• easier to develop than statistical methods
• capability to learn and improve
• good for complex pattern recognition tasks
• usable for unstructured and difficult input (like images)
• fault tolerance

CONs

• choice of parameters (layers, units) requires skill
• requires sufficient training material
• resulting hypothesis cannot be understood easily
• knowledge implicit (subsymbolic representation)
• verification, behaviour prediction difficult