Title: EAI / 06_learning_from_examples

Q: What does learning do to the agent?
A: It modifies the agent's decission mechanisms to improve performance.

Explain the architecture of a learning agent.

Q: Name the four components of a learning agent.
A: 1. Performance element: select external actions
2. Critic: performance / result assessment
3. Learning element: make improvements
4. Problem generator: suggest actions for new experiences

Q: What does the learning element do?
A: The learning element (LE) makes changes to the "knowledge components" of an agent architecture

Q: What is the learning element (LE) design dictated by?
A: - type of performance element used (e.g. Utility-based agent)
- which functional component to be learned (e.g. transition model)
- representation for the functional component (e.g. neural net)
- available feedback (e.g. win/loss)

Q: Describe an example of a learning agent with its 4 components.
A: Drive a taxi
- Performance element: knowledge about driving, and procedures to do so
- Critic: assess status, reactions of customer / other drivers / pedestrians...
- Learning element: create rule not to turn steering wheel too quickly, break softly,...
- Problem generator: try brakes on slippery road, push back with side mirror only

How can states of the world be represented?

Q: What's an important factor for learning? Name 3 common learning modes.
A: Important for learning: feedback.
- Unsupervised learning: no explicit feedback, most common: clustering
- Reinforcement learning: occasional rewards or punishments in terms of payoff
- Supervised learning: correct answer for each instance ("label")

Q: What are issues from learning with data?
A: - noise
- inaccuracies (biased data)

Q: What is inductive learning?
A: Learn a function from examples.
Inductive learning problem:
Given a (finite) training set \((\mathbf{x_1},y_1,...,\mathbf{(x_n,y_n)}\) of examples, find a function (hypothesis) \(h\) that approximates \(f(h\approx f)\)

Q: Name two types of inductive learning problems.
A: - Classification
- Regression

Q: Explain bias and variance.
A: - bias: deviation from the expected output over different training sets
- variance: change in hypothesis \(h\) by change in the training set

Q: What is the Bias-Variance tradeoff?
A: tradeoff between
- complex hypothesis that fit the data well (overfitting)
- simpler hypothesis that might gneeralize better (underfitting)

Explain decision tree learning.

Q: What makes an attribute good for splitting?
A: a good attribute splits the exmaples into subsets that are (ideally) "all positive" or "all negative"

Q: How should you choose attributes for splitting?
A: Based on information gain

Q: Define Entropy.
A: general:\[H(\langle P_1, ..., P_n\rangle)=\sum_{i=1}^n -P_i \log_2(P_i)\]special case \(n=2\) (binary entropy):
\[H(\langle P_1,P_2\rangle)=-P_1 \log_2 P_1 - (1-P_1) \log_2(1-P_1)=:B(P_1)\]

Q: Define Information Gain (and the remainder)
A: \[\text{Gain}(A)=B(p/(n+p))-Rem(A)\]\[Rem(A)=\sum_k \frac{p_k+n_k}{p+n} B(p_k/(p_k+n_k))\]

Q: How many non-equivalent decision trees with \(n\) BOolean attributes exist?
A: \(2^{2^n}\)

Q: How many conjunctive hypotheses (conjunctions of literals) exist?
A: Each attribute can be 1) positive 2) negative or 3) out
\(\Rightarrow 3^n\)

Describe decision lists.

Q: Explain PAC learnability.
A: Describes how many examples are needed to learn a concept/function to be probably approximately correct with confidence \(1-\delta\) that the error is smaller than \(\varepsilon\).
Sample complexity \(N \geq \dfrac{1}{\varepsilon} \left(\ln (1/\delta)+\ln |\mathcal{H}|\right)\)

Q: What are remedies for overfitting?
A: - Decision tree pruning
- Cross-validation

Explain cross-validation

Describe model selection.

Describe gradient descend.

Q: What can you do to prevent overfitting in regression?
A: Add a regularization term \(\lambda \cdot \text{Complexity}(h)\) to \(Loss(w)\)

Q: Whats a linear classifier?
A: Regression used as a linear seperator, e.g.
\[h_{\mathbf{w}}(\mathbf{x})=1 \text{ if } \mathbf{w}\cdot\mathbf{x} \geq 0 \text{ else }0 \]

Q: Whats the update rule for gradient descend?
A: \(w_i \leftarrow w_i + \alpha (y-h_w(x))\)