Different perspectives exist for defining learning problems. Analyse why the choice of performance measure fundamentally alters what is considered “learning success.”

Concept learning assumes the existence of a target concept. Explain why this assumption becomes problematic in real-world domains.

Version space represents all hypotheses consistent with observed data. Which statement best reflects this definition?

Explain why maintaining the entire version space is conceptually powerful but computationally difficult.

Candidate Elimination maintains specific and general boundaries. Explain how these boundaries jointly characterize uncertainty in concept learning.

Inductive bias is unavoidable in any learning system. Explain why learning without inductive bias is theoretically impossible.

Concept learning algorithms often assume noise-free data. Analyze why noise violates the fundamental assumptions of version space learning.

Consistency with training data is often treated as a goal. Explain why consistency alone does not guarantee good generalization.

Inductive bias influences hypothesis preference. Explain how bias resolves ambiguity when many hypotheses fit the data equally well.

Version space learning assumes the target concept lies within the hypothesis space. Explain the consequence if this assumption is violated.

Decision tree learning represents hypotheses differently from conjunctive concept learners. Explain why trees can naturally represent disjunctive concepts.

Decision trees impose an implicit inductive bias. Explain the nature of this bias in terms of preferred hypothesis structure.

Greedy learning strategies are widely used in decision tree induction. Explain why greediness is preferred despite lack of global optimality guarantees.

Representation plays a central role in learnability. Explain how hypothesis representation constrains what can be learned.

Heuristic space search is used when hypothesis spaces are large. Explain how heuristics trade optimality for computational feasibility.

Candidate Elimination explicitly represents uncertainty. Explain why this explicit uncertainty representation is rarely used in large domains.

Decision trees are considered interpretable models. Explain what property of tree representation enables interpretability.

Learning problems differ in supervision assumptions. Explain why concept learning typically assumes fully labeled data.

Inductive bias can be explicit or implicit. Explain the difference between these two forms in learning algorithms.

Overfitting is a central issue in learning. Explain why decision trees are particularly prone to overfitting.

Version space learning shrinks hypothesis sets monotonically. Explain why this monotonicity breaks in noisy environments.

Heuristic evaluation functions guide hypothesis search. Explain why poorly designed heuristics can mislead learning.

Decision tree learning implicitly performs feature selection. Explain how this occurs during the learning process.

Learning algorithms often assume stationary target concepts. Explain the implication when the target concept drifts over time.

Candidate Elimination requires maintaining boundary sets. Explain why boundary representation is sufficient to encode the entire version space.

Decision tree algorithms use entropy-based criteria. Explain the theoretical role of entropy in split selection.

Hypothesis space search can be complete or incomplete. Explain why completeness is often sacrificed in practical learning systems.

Concept learning typically assumes Boolean-valued target functions. Explain why this assumption is made in theoretical analysis.

Inductive bias affects sample complexity. Explain how stronger bias influences required training data.

Decision trees encode hierarchical decisions. Explain how this structure affects hypothesis expressiveness.

Candidate Elimination assumes deterministic target concepts. Explain why probabilistic concepts violate this assumption.

Heuristic search often avoids exhaustive enumeration. Explain the primary benefit of this approach.

Decision tree pruning improves generalization. Explain why pruning reduces variance.

Learning problem formulation precedes algorithm choice. Explain why incorrect formulation undermines learning regardless of algorithm.

Version space learning delays hypothesis commitment. Explain the advantage of this strategy.

Decision trees struggle with certain concept classes. Explain why XOR-like concepts are difficult for greedy tree induction.

Heuristic space search depends heavily on representation. Explain why representation affects search efficiency.

Inductive bias determines learnability limits. Explain why some target concepts are unlearnable under certain biases.

Decision trees assume axis-aligned splits. Explain how this assumption constrains representational power.

Learning systems balance bias and variance. Explain why increasing inductive bias often reduces variance.

In the Candidate Elimination algorithm, the specific boundary is updated after observing a positive example. Explain how minimal generalization is applied to ensure consistency while preserving maximal constraint on hypotheses.

The general boundary in Candidate Elimination is modified using negative examples. Analyze how minimal specialization prevents overly restrictive hypothesis elimination during this update.

Candidate Elimination maintains both S and G boundaries simultaneously. Explain algorithmically why maintaining both boundaries is essential for complete version space representation.

The Candidate Elimination algorithm fails in noisy environments. Explain at which algorithmic step noise causes the version space to collapse.

Decision tree learning follows a top-down recursive strategy. Explain how recursive partitioning simplifies hypothesis construction but risks suboptimal splits.

Information Gain is commonly used to select attributes in decision tree induction. Explain why this heuristic may prefer attributes with many distinct values.

Gain Ratio was introduced to address a limitation of Information Gain. Explain algorithmically how Gain Ratio corrects attribute selection bias.

Decision tree algorithms repeatedly recompute split criteria at each node. Explain why attribute usefulness is context-dependent across different tree levels.

Pruning is applied after decision tree construction in many algorithms. Explain how post-pruning improves generalization despite increasing training error.

Pre-pruning stops tree growth early based on heuristics. Analyze the algorithmic risk associated with aggressive pre-pruning.

Heuristic space search explores hypothesis space selectively. Explain how evaluation functions guide expansion of promising hypotheses.

Heuristic search algorithms are often incomplete. Explain why incompleteness is accepted in large hypothesis spaces.

Best-first search is commonly used in hypothesis space exploration. Explain how priority-based expansion affects convergence behavior.

Depth-first heuristic search uses limited memory. Analyze why this strategy risks missing globally optimal hypotheses.

Breadth-first search is rarely used in large hypothesis spaces. Explain why memory requirements make it impractical for learning problems.

Decision tree learning implicitly defines a hypothesis space. Explain how the choice of splitting criteria constrains this space.

Candidate Elimination does not rank hypotheses by preference. Explain why hypothesis ordering is unnecessary in this algorithm.

Decision trees handle discrete and continuous attributes differently. Explain the algorithmic step required to process continuous attributes.

Heuristic space search depends heavily on branching factor. Explain how hypothesis representation influences branching factor magnitude.

Candidate Elimination halts when S and G boundaries converge. Explain the algorithmic meaning of this convergence.

Decision tree induction assumes independent splits at each node. Explain why earlier splitting decisions cannot be revised later.

Heuristic evaluation functions are approximations. Explain how inaccurate heuristics affect hypothesis search quality.

Decision trees can grow very deep in noise-free datasets. Explain why depth increases even when training accuracy is perfect.

Candidate Elimination requires general-to-specific ordering of hypotheses. Explain how this partial order enables systematic boundary updates.

Heuristic search algorithms balance exploration and exploitation. Explain how heuristic strength influences this balance.

Decision tree pruning is evaluated using validation data. Explain why training data alone is insufficient for pruning decisions.

Candidate Elimination requires storing boundary sets explicitly. Explain why this storage becomes infeasible in high-dimensional spaces.

Heuristic space search may terminate early. Explain why early termination is acceptable in approximate learning.

Decision tree learning handles missing values heuristically. Explain why probabilistic assignment is often used.

Candidate Elimination initializes boundaries with extreme hypotheses. Explain the purpose of this initialization strategy.

Heuristic space search differs from gradient-based search. Explain why it is suitable for symbolic hypothesis spaces.

Decision trees use stopping criteria to end recursion. Explain why poor stopping criteria lead to poor generalization.

Candidate Elimination treats positive and negative examples asymmetrically. Explain why this asymmetry is required algorithmically.

Heuristic search may revisit similar hypotheses. Explain how memoization or closed lists reduce redundant computation.

Decision tree learning is sensitive to class imbalance. Explain how imbalance affects split evaluation heuristics.

Candidate Elimination assumes complete attribute information. Explain how missing attributes violate algorithmic assumptions.

Heuristic search algorithms may require restarts. Explain why restarts help escape poor search regions.

Decision trees are sensitive to small data perturbations. Explain why slight data changes can alter tree structure significantly.

Candidate Elimination explicitly maintains uncertainty. Explain why probabilistic confidence is not computed.

Heuristic space search trades optimality for tractability. Explain why this trade-off is unavoidable in realistic learning problems.

Assuming the most general and most specific hypotheses are included, determine the total hypothesis count.

A version space initially contains 500 hypotheses. After processing a negative example, 40% of the hypotheses are eliminated. Compute the remaining hypothesis count.

A decision tree node has class distribution (18 positive, 2 negative). Compute the entropy and analyze whether further splitting is likely to be useful.

A decision tree split reduces entropy from 0.94 to 0.52. Compute the information gain and interpret its significance for attribute selection.

A hypothesis space doubles in size with each added attribute. If 6 attributes are used, estimate the hypothesis space growth order.