TL;DR
This paper proves that "strict width two branching programs" (SW2), a specific type of computational model, are "properly PAC learnable" under any distribution. This means we can efficiently learn any function represented by an SW2 program using random examples, and the learned program will also be an SW2 program. This work also shows that learning a slightly restricted version of these programs (monotone SW2) is as hard as learning general DNF formulas, a long-standing open problem.
What Problem Does This Paper Address?
Branching programs are a way to represent Boolean functions, and their "width" refers to a restriction on how complex they can be at any given level. While general branching programs are too complex to learn efficiently, researchers have been investigating the learnability of restricted versions. Specifically, the paper addresses the learnability of "strict width two branching programs" (SW2). SW2 programs have a maximum width of two and exactly two sinks (outputs), one for "true" and one for "false." The paper builds upon previous work that showed learning width-five branching programs is hard and that ordered strict width two branching programs (a further restriction) are learnable. However, the learnability of general SW2 programs was an open question. Additionally, the paper investigates the hardness of learning "monotone width two branching programs," which have only one sink (labeled 0), and relates it to the well-known problem of learning Disjunctive Normal Form (DNF) formulas.
Methods
The core of the paper's contribution lies in establishing a novel characterization of strict width two branching programs (SW2). They prove that SW2 programs are equivalent to a specific type of "decision list" called "(⊕2, ⊕)-DL." Decision lists are a sequence of Boolean conditions, and the first condition that evaluates to true determines the output. The equivalence is shown through two lemmas: one demonstrating that SW2 programs can be converted into (⊕2, ⊕)-DL, and another showing the reverse.
With this equivalence established, the authors leverage existing PAC learning algorithms for decision lists. They show that learning (⊕1, ⊕)-DL is properly PAC learnable using a technique similar to Rivest's [R87] for learning decision lists. This result is then extended to (⊕2, ⊕)-DL, and finally, through the established equivalence, to SW2. The learning algorithm for SW2 is described as "distribution-free," meaning it works regardless of how the training examples are distributed.
Datasets
Not discussed in the paper. The paper focuses on theoretical learnability and does not present experimental results on specific datasets.
Key Insights and Ideas
- SW2 as Decision Lists: The most significant insight is the equivalence between strict width two branching programs (SW2) and (⊕2, ⊕)-DL decision lists. This connection is crucial because it allows the application of existing, powerful learning algorithms for decision lists to the problem of learning SW2.
- Proper PAC Learnability: The paper achieves "proper PAC learnability" for SW2. This is a strong result because it not only guarantees that we can learn SW2 functions but also that the learned hypothesis will be in the same class (SW2). This is often a more desirable outcome than learning a function from a different, potentially more complex, class.
- Hardness of Monotone SW2: The paper highlights that learning monotone width two branching programs is as hard as learning DNF formulas. This is important because learning DNF is a fundamental problem in machine learning, and this result places a lower bound on the complexity of learning this restricted class of branching programs.
Key Results
- Proper PAC Learnability of SW2: The paper proves that strict width two branching programs (SW2) are properly PAC learnable under any distribution. The sample complexity for this learning is shown to be $O(\frac{1}{\epsilon^2} (\frac{n^2}{\epsilon} + \log \frac{1}{\delta}))$.
- Hardness of Monotone SW2: Learning monotone width two branching programs is shown to be as hard as learning DNF formulas.
- Equivalence: Strict width two branching programs are shown to be equivalent to (⊕2, ⊕)-DL decision lists.
Limitations and Future Work
- Monotone SW2 Hardness: While the paper establishes the hardness of learning monotone SW2, it doesn't provide an algorithm for it. This remains an open area, likely tied to the difficulty of learning DNF.
- Ordered Strict Width Two: The paper mentions that their techniques can be used to properly PAC learn ordered strict width two branching programs, solving an open question from a previous work [ERR95]. This is presented as a direct application of their findings.
- General Width k: The paper focuses specifically on width two. Extending these results to learnability of general width $k$ branching programs remains a challenging open problem.
Summary updated