Efficient learnability in the realizable case
In the realizable case, the examples are consistent with a perfect target conjunction.
From Binary Inputs to One Label
Suppose a learning problem uses n binary features. Each input is an n-component vector, so the input space is X = {0, 1}^n. A Boolean conjunction is a rule that takes one such input and produces one binary output from Y = {0, 1}. The first task is to understand this rule as a function. Only after that should we ask whether rules of this kind can be learned efficiently.
The Mapping Definition
A Boolean conjunction maps X = {0, 1}^n to Y = {0, 1}. Its input is an n-component binary vector, and its output is a single binary value.
The notation describes the kind of function involved. The set {0, 1}^n contains binary vectors with n components. The set {0, 1} contains the possible labels produced by the rule. Therefore, the defining question is: which single binary label does the proposition formula assign to each n-component binary input?
Reading the Input and Output Spaces
Consider a Boolean conjunction whose input has n binary components.
- 1Identify the input
The input is one vector from X = {0, 1}^n. It has n components, and every component is either 0 or 1.
- 2Identify the rule
The rule is represented by a proposition formula containing variables, possible negations, and conjunction symbols.
- 3Identify the output
The rule produces one value in Y = {0, 1}, rather than another n-component vector.
A Boolean conjunction is an n-bit-input-to-one-bit-output mapping.
Formula Parts and Variable Roles
The mapping can be expressed by a proposition formula. The formula has positive variables, negated variables, and conjunction symbols. A variable that appears without negation is a positive variable. A variable preceded by the negation symbol ¬ is a negated variable. The conjunction symbol ∧ joins the terms into the full proposition formula.
The indices on the variables identify components of the input vector. Thus, the formula does not refer vaguely to the input as a whole: its indexed variables identify which components participate in the proposition formula.
Classifying Formula Components
Consider the generated proposition formula x_1 ∧ ¬x_3 ∧ x_5.
- 1Find the positive variables
The terms x_1 and x_5 occur without the negation symbol, so they are positive variables.
- 2Find the negated variables
The term ¬x_3 includes the negation symbol, so x_3 occurs as a negated variable.
- 3Find the conjunction symbols
The two ∧ symbols join the three terms into one proposition formula.
- 4Read the indices
The indices 1, 3, and 5 identify the input components used by this formula.
The formula contains positive variables x_1 and x_5, the negated variable ¬x_3, and conjunction symbols joining them.
Tracing a Labeled Sample
Learning begins with labeled examples: inputs from X paired with outputs from Y. In the realizable case, the examples are consistent with a perfect target conjunction. The learner's task is then connected to the class definition: find or identify a Boolean conjunction that accounts for the labeled examples. The source establishes the class and its learnability conclusion, but it does not provide a further implementation trace, so the following flow is a conceptual illustration rather than an algorithm.
What Efficient Learnability Claims
The statement that Boolean conjunctions are efficiently learnable in the realizable case is a learnability conclusion about the class. It says that, when a perfect target conjunction exists for the labeled examples, Boolean conjunctions can be learned efficiently. This is a separate claim from the definition of a Boolean conjunction as a mapping from {0, 1}^n to {0, 1}.
| Question | Answer |
|---|---|
| What is a Boolean conjunction? | A mapping from X = {0, 1}^n to Y = {0, 1}. |
| How can it be represented? | By a proposition formula with positive variables, negated variables, and conjunction symbols. |
| What does the learnability statement say? | Boolean conjunctions are efficiently learnable in the realizable case. |
| What does realizable mean here? | A perfect target conjunction exists for the labeled examples. |
The function definition and the learnability claim answer different questions.
Mistakes Beginners Make
Common mistake Treating the output as an n-component vector.
What it looks likeDescribing the output as another element of {0, 1}^n.
Why it failsThe input is an n-component binary vector, but the output is a single value in Y = {0, 1}.
Do this insteadRead the mapping as n binary components in and one binary value out.
Common mistake Calling every variable a positive variable.
What it looks likeIgnoring the negation symbol in ¬x_j1.
Why it failsA variable preceded by ¬ occurs as a negated variable.
Do this insteadInspect each term for ¬ before classifying it.
Common mistake Ignoring the variable indices.
What it looks likeTreating x_i1 and x_j1 as if their indices did not identify input components.
Why it failsThe indices identify which components of the n-component input participate in the proposition formula.
Do this insteadUse the indices to track the input components named by the formula.
Common mistake Using the formula definition as evidence of efficient learnability.
What it looks likeSaying that a rule is efficiently learnable merely because it contains ∧ symbols.
Why it failsThe formula describes membership in the Boolean-conjunction class; efficient learnability is a separate theorem-level conclusion for the realizable case.
Do this insteadFirst identify the class from its formula structure, then state the separate learnability result.
Practice the Two-Level Test
A proposition formula contains positive variables, negated variables, and conjunction symbols. Explain, in two separate statements, first why it can be considered a Boolean conjunction, and second what additional claim is made when we say Boolean conjunctions are efficiently learnable in the realizable case.
Hints
- For the first statement, mention the mapping from X = {0, 1}^n to Y = {0, 1}.
- For the second statement, mention the existence of a perfect target conjunction and keep the learnability claim separate from the formula structure.
- 1Use a two-level test: identify the Boolean-conjunction structure from the proposition formula, then apply the separate result that this class is efficiently learnable when the labeled examples are realizable by a perfect target conjunction.
Key Takeaways
- A Boolean conjunction maps the n-component binary input space X = {0, 1}^n to the single-bit output space Y = {0, 1}.
- Its proposition formula contains positive variables, negated variables, and conjunction symbols.
- Variable indices identify the input components that participate in the formula.
- Efficient learnability in the realizable case is a separate claim: when a perfect target conjunction exists, Boolean conjunctions are efficiently learnable.
- The formula defines the class; the learnability statement describes what can be learned about that class.