Efficient learnability in the realizable case
A Boolean conjunction maps X = {0, 1}^n to Y = {0, 1}.
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.
Identify the input: The input is one vector from X = {0, 1}^n. It has n components, and every component is either 0 or 1.
Identify the rule: The rule is represented by a proposition formula containing variables, possible negations, and conjunction symbols.
Identify 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.
Find the positive variables: The terms x_1 and x_5 occur without the negation symbol, so they are positive variables.
Find the negated variables: The term ¬x_3 includes the negation symbol, so x_3 occurs as a negated variable.
Find the conjunction symbols: The two ∧ symbols join the three terms into one proposition formula.
Read 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
Treating the output as an n-component vector.
The input is an n-component binary vector, but the output is a single value in Y = {0, 1}.
Fix:
Read the mapping as n binary components in and one binary value out.Calling every variable a positive variable.
A variable preceded by ¬ occurs as a negated variable.
Fix:
Inspect each term for ¬ before classifying it.Ignoring the variable indices.
The indices identify which components of the n-component input participate in the proposition formula.
Fix:
Use the indices to track the input components named by the formula.Using the formula definition as evidence of efficient learnability.
The formula describes membership in the Boolean-conjunction class; efficient learnability is a separate theorem-level conclusion for the realizable case.
Fix:
First 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.
- Use 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.