A Concept Learning Tool Based On Calculating Version Space Cardinality

arXiv:1803.08625v1 [cs.AI] 23 Mar 2018

Kuo-Kai Hsieh
University of California, Santa Barbara
kuokai@umail.ucsb.edu

1

Li-C. Wang
University of California, Santa Barbara
licwang@ece.ucsb.edu

Abstract

those few traces, i.e. the causes. In this context, features
are used to describe the input stimuli.

In this paper, we proposed VeSC-CoL (Version Space Cardinality based Concept Learning) to deal with concept learning on extremely
imbalanced datasets, especially when crossvalidation is not a viable option. VeSC-CoL
uses version space cardinality as a measure
for model quality to replace cross-validation.
Instead of naive enumeration of the version
space, Ordered Binary Decision Diagram and
Boolean Satisfiability are used to compute the
version space. Experiments show that VeSCCoL can accurately learn the target concept
when computational resource is allowed.

Abstractly, the learning problem faced in those applications can be formulated as the following. Two classes
of samples are given, D+ and D− . Each sample s
is encoded with a set of discrete features f1 , . . . , fn .
Let mp = |D+ | and mn = |D− |. Usually we have
mp  mn , mp is very small or can be zero. The cause(s)
of the positive samples can be described as a target concept. And the learning goal is to uncover this target concept from D+ and D− . Without loss of generality, we
can assume the features are binary. This is because multiple binary features can be used to encode a single multivalue feature. Furthermore, we can assume the target
concept falls into the scope of a k-term disjuctive normal
form (DNF) with a small k. In practice, a single cause
for a property can be described as a combination of feature values, e.g. a monomial. If a property has multiple
causes, then they can be described as a k-term DNF. Because the number of causes for a property is small (e.g.
2 to 4), usually there is no need to consider a large k.

INTRODUCTION

In hardware Electronic Design Automation (EDA) and
Test, learning methods have been widely used in diverse
applications to analyze data from design simulation and
testing of silicon chips (Wang, 2017). In many applications, data can be encoded with discrete features and
the underlying learning approach can be formulated as
concept learning. However, in those applications, the applicability of concept learning is usually limited by the
availability of the data. For example, the data comprises
two classes of samples, positive and negative, and there
are very few or no positive samples. This scenario occurs
quite often when the goal of learning is to uncover the
cause for some special property observed on the positive
samples. To give an example, in functional verification
(e.g. for a System-on-Chip (SoC) design) the data are
simulation traces based on applying a set of input stimuli
to the design. The interest can be on a particular property
observed in the simulation traces. Usually, there are few
traces showing the property. The learning goal is to understand what characteristics in the input stimuli lead to

Cross-validation is a common way to select and validate
a learning model in practice. However, for the concept
learning problem described above, cross-validation is not
a viable option due to the lack of positive samples. Because the samples are obtained through simulation or silicon measurement, there is a significant cost to get an
additional sample. By the nature of the problem, getting
more positive samples is difficult without knowing the
cause, i.e. without learning the target concept.
Because cross-validation cannot be used, in practice validation of a learning result relies on a separate process
outside the learning. For example, this validation may involve expert’s investigation of a target concept or through
discussion among a group of engineers to determine its
meaningfulness. Because the cost associated with such
a model validation process can be significant, it is desirable for a learning tool to output a model with some sort

of guarantee.
In traditional concept learning, there is no requirement
that the output concept is unique. In other words, the version space can still contain many concepts that can fit the
data and the output concept is just one of them. Usually,
a tool can report several models if the user adjusts some
learning parameters. However, a tool does not report the
size of the version space, i.e. how many remaining concepts that can all fit the data.
Suppose we have a tool that can calculate the size of version space. Then, this tool can be used not only to find
the concept that fits the data but also to identify the concept hypothesis space that results in a small version space
based on the data. In other words, a learning strategy can
be implemented to search for the hypothesis space assumption that fits the data where the ”fitting” can be defined as resulting in a very small version space, e.g. size
< 10. Note that given a set of hypothesis space assumptions to choose from, it is possible that none of them can
fit the data. In this case, the learning fails. Then, the user
has two choices, either to expand the data or to include
additional hypothesis space assumptions.
Based on the discussion above, in this paper, we
present Version Space Cardinality based Concept Learning (VeSC-CoL). The idea of VeSC-CoL is to search for a
fitting hypothesis space with increased complexity. This
implies that VeSC-CoL works with a set of pre-defined
hypothesis space assumptions where the complexity of
each hypothesis space is defined and can be calculated.
Outputs from the VeSC-CoL tool include a learned concept and the version space cardinality as a quality measure for the concept. For example, if the cardinality is
one, this means that the concept is unique and this indicates the highest quality for the model. If the cardinality
is small, the tool can also list all fitting concepts.

2

VERSION SPACE LEARNING

Version space learning originates in (Mitchell, 1978).
Given a hypothesis space H, a set of positive samples
D+ , and a set of negative samples D− , version space is
defined as the set of hypotheses that are consistent to the
given samples. Formally speaking, V S = {h ∈ H|∀s ∈
D+ h(s) = 1, ∀s ∈ D− h(s) = 0}.
In (Mitchell, 1978), version space (V S) is represented
by the boundary sets S and G, where S is the set of
most specific hypotheses in V S and G is the set of most
general hypotheses in V S. Then, for every hypothesis
h ∈ V S, h is as or more general than some hypothesis in
S and as or more specific than some hypothesis in G.
Following research in version space learning include in-

vestigating new methods to manipulate S and G, e.g.
incremental version-space merging that utilizes set intersection idea to calculate the boundary sets (Hirsh,
1994), proposing alternative version space representations (Lau et al., 2003), and arguing that representation
is not the key problem in version space learning (Hirsh
et al., 2004).
Our work differs from the above research mainly in that
we investigate methods to calculate version space cardinality. Except for naive enumeration, there is no published work solving this problem.

3

VeSC-CoL OVERVIEW

In this work, VeSC-CoL adopts a particular learning
strategy enabled by the capability to calculate version
space cardinality. Given a general assumption of hypothesis space, a sequence of hypothesis sub-spaces are defined. Each sub-space comprises hypotheses of the same
complexity. VeSC-CoL then tries to find the simplest hypothesis sub-space that fits the data.
3.1

HYPOTHESIS SPACE PARTITION

The search of VeSC-CoL can be thought of as following
the Occam’s razor principle to find the simplest hypothesis to fit the data as well. The added-value of VeSCCoL is that it also identifies the simplest fitting hypothesis sub-space if it exists. As mentioned above, it is
possible that a fitting hypothesis can be found while the
simplest fitting hypothesis sub-space does not exist because the version space cardinality is too large. Hence,
VeSC-CoL can fail. This is in contrast to a traditional
learning tool where if there exists a fitting model, the
tool would not fail. Take decision tree classifier as an
example. Such learning can also follow the Occam’s razor principle where the process of node splitting stops
when a node contains only one class of data. Such learning would not fail if there exists a decision tree to fit the
data.
With above strategy, the learning problem can be stated
as the following: given a seqeunce of hypothesis subspaces H1 , H2 , . . ., a complexity measure comp, a hypothesis fitting evaluator f it, a cardinality bound B, and
data D, find a hypothesis h ∈ Hi such that comp(h)
is minimized subject to (1) f it(h, D) is true and (2) the
cardinality of the version space based on Hi is ≤ B.
Figure 1 illustrates a simple search process to solve the
learning problem. Given the complexity measure comp,
the original hypothesis space H is partitioned into a sequence of hypothesis sub-space H1 , H2 , . . . where each
sub-space comprises the hypotheses of the same com-

plexity. The search proceeds from the lowest-complexity
sub-space to highest-complexity sub-space. The search
process stops when it first finds a hypothesis that satisfies the two constraints.

The idea of minimization by search

|VS| = 0

Version Space
Learning

Hypothesis
space

|VS| > B

…

Return VS

0 <|VS| ≤ B

Partition by
complexity

Hypothesis
sub-spaces

Next level
complexity

Report
over-fitting

Figure 2: Illstration of VeSC-CoL flow

Search through increasing complexity

Figure 1: Sub-space partitioning based on complexity
Suppose Hi is a hypothesis sub-space where every hypothesis h does not satisfy the first constraint (f it(h, D)
is not true). This indicates an under-fitting situation. On
the other hand, suppose Hj for j > i contains a hypothesis h satisfying the first constraint but the version space
of Hj violates the second constraint. This indicates an
over-fitting situation. If j = i + 1, then there is no solution to the learning problem. This means that there is no
hypothesis sub-space to fit the data or there is not enough
data to obtain a small enough version space.
Recall that in this work VeSC-CoL is applied for learning
a k-term DNF formula. Given a k-term formula h, the
complexity measure comp used by VeSC-CoL is defined
as comp(h) = (l, k), where k is the number of terms and
l is the number of literals in h. We say (l1 , k1 ) < (l2 , k2 )
if and only if l1 < l2 or l1 = l2 ∧ k1 < k2 .
For example, suppose our hypothesis space is k-term
DNF with k no greater than 3.
The partitioned
sub-space in the order of increasing complexity is
(1, 1), (2, 1), (2, 2), (3, 1), (3, 2), (3, 3), (4, 1), . . ..
3.2

Though this problem is intractable in theory, in practice
a useful tool can still be developed. In this paper, we
propose two methods to calculate version space cardinality. The first method is based on Ordered Binary Decision Diagram (BDD) (Bryant, 1986). The version space
cardinality can be obtained by calculating the number
of minterms in BDD. The second method is based on
Boolean Satisfiability (SAT). For the SAT implementation, VeSC-CoL does not calculate version space cardinality. Rather, VeSC-CoL tries to find at most B + 1
hypotheses in the version space.

4

BDD-BASED LEARNING

The basic idea of the proposed BDD-based version space
learning method is based on set intersection (Hirsh,
1994). Figure 3 illustrates this idea. BDD is used to
represent a set of hypothesis. In a version space BDD,
there is a bijection between a minterm of the BDD and a
DNF representation.

Hypothesis space

Hypothesis
sub-space

VeSC-CoL FLOW

Figure 2 depicts the flow of VeSC-CoL. It starts from
calculating the version space cardinality of the simplestcomplexity sub-space. If there is no hypothesis consistent with the data, i.e. |V S| = 0, then VeSC-CoL moves
onto the next hypothesis sub-space. The iteration stops
when both constraints are satisfied. At this point, VeSCCoL reports at most B hypotheses in version space as
well as version space cardinality as a measure of learning quality. B is an application-specific parameter and
usually is set to the maximum number of hypotheses that
a user can handle in model evaluation.
In theory, this problem is proved to be no easier than #Pcomplete (Hirsh et al., 2004). Even determining whether
a version space is empty or not for k-term DNF is NPhard (Pitt and Valiant, 1988).

Sample 1
space

Sample 2
space

Version space

Figure 3: Version space learning by set intersection
First, a set of hypotheses with a given complexity is created, which is the hypothesis sub-space in Figure 3. Then
each sample is converted into the set of hypotheses that
agree with the sample. The version space can be obtained
by intersecting the hypothesis sub-space and all the sample spaces.
Set intersection can be performed via Boolean AND operation of BDDs. To determine the size of version space,
because of bijection, we can simply count the number of

4.3

minterms in the version space BDD. Note that if a hypothesis has multiple representations, special treatment
is required and it is discussed in Section 4.6.1.

Algorithm 2 describes the method to create a BDD representing an n-feature, k-term DNF, l-literal space. Line
1 to Line 4 is the initialization process for dynamic programming. The idea is that at the end, an assignment that
makes lit dd[w] == 1 can be mapped to a DNF formula
having at least w literals.

In the description below, we assume the hypothesis subspace is a (l, k)-space, i.e. a k-term l-literal DNF. If another hypothesis sub-space definition is used, the BDD
encoding method will be different but the encoding ideas
can be reused.
4.1

IDEA OF ENCODING

Given the number of features n and the number of terms
k. Let xji represent the status of the i-th feature in the jth term, wherein xji ∈ {neg, pos, dcare}, which denotes
appearing in negative form, in positive form and don’t
care (not appearing). Since xji is a three-value variable,
we use two Boolean variables to represent it in BDD. An
example is shown in Figure 4. In sum, there are 2nk
variables in BDD.
x == neg

x == pos

x == dcare

1
2
3
4
5
6
7
8
9
10

F

F

T

T

F

T

11
12

F

1

T

F

0

0

T

1

13

0

1

14
15

Figure 4: Using BDD to encode a three-value variable

4.2

BASE HYPOTHESIS SPACE ENCODING

Algorithm 1 shows the method to create a BDD representing an n-feature and k-term DNF hypothesis space.
This algorithm simply forces each xji to be in its three
possible values. Note that there is a bijection between a
satisfiable assignment in the returned BDD and a k-term
DNF representation.

1
2
3

4
5
6

Algorithm 1: Creating a BDD representing a n-variable,
k-term DNF space
Input: Integers n, k
Output: BDD dd
dd ← BDD One();
for i ∈ {1, 2, . . . , n} do
tmp dd = BDD Or(xji == pos, xji == neg, xji ==
dcare);
dd ← BDD And(dd, tmp dd);
end
return dd;

HYPOTHESIS SUB-SPACE ENCODING

Algorithm 2: Creating a BDD representing a n-variable,
k-term, l-literal space
Input: Integers n, k, l
Output: BDD dd
lit dd[0] ← BDD One();
for w ∈ {1, 2, . . . , l + 1} do
lit dd[w] ← BDD Zero();
end
for j ∈ {1, 2, . . . , k} do
for i ∈ {1, 2, . . . , n} do
var dd ← BDD Or(xji == pos, xji == neg);
for w ∈ {l + 1, l, . . . , 1} do
tmp dd ← BDD And(lit dd[w − 1], var dd);
lit dd[w] ← BDD Or(lit dd[w], tmp dd);
end
end
end
dd ← BDD And(lit dd[l], BDD Not(lit dd[l + 1]));
return dd;
Line 5 to Line 13 updates the BDDs used in dynamic programming. lit dd is used to save intermediate results. At
line 10, an assignment that makes lit dd[w] == 1 can be
mapped to a DNF formula with at least w literals in the
processed xji . The outer two loops iterate all xji , then for
each xji , lit dd is updated accordingly. Note that lit dd is
updated from the highest index to the lowest index. After processing all the xji , line 14 creates the result BDD
representing the l-literal sub-space.
Note that the returned BDD does not guarantee a bijection between a minterm and a DNF representation due to
the NOT operation. To have this bijection, a minterm in
the returned BDD must be in the base hypothesis space
BDD as well. Also, with proper BDD variable ordering,
it can be shown that the complexity of Algorithm 2 is
O(nkl).
4.4

POSITIVE SAMPLE SPACE ENCODING

Algorithm 3 converts a positive sample to a BDD representing a set of consistent hypotheses. Its input parameters are n, the number of features, k, the number of terms,
and s[i] ∈ {0, 1}, the value of the i-th feature. The key
idea is in line 12, given a hypothesis, at least one term of

the hypothesis must be evaluated as true so the hypothesis is evaluated as true.

1
2
3
4
5
6

7
8

9
10
11
12
13
14

Algorithm 3: Converting a positive sample to BDD
Input: Integers n, k, and an n-dimensional Boolean
vector s
Output: BDD dd
dd ← BDD Zero();
for j ∈ {1, 2, . . . , k} do
term dd ← BDD One();
for i ∈ {1, 2, . . . , n} do
if s[i] == 0 then
tmp dd ← BDD Or(xji == neg, xji ==
dcare);
else
tmp dd ← BDD Or(xji == pos, xji ==
dcare);
end
term dd ← BDD And(term dd, tmp dd);
end
dd ← BDD Or(dd, term dd);
end
return dd;

Suppose s = 101. For a single term to be evaluated as
true, feature 1 and feature 3 must not be negative literals
and feature 2 must not be a positive literal in the term.
Otherwise, this term is evaluated as false. The generalization of this idea shown in line 3 to line 11.
At line 10, each minterm in term dd can be mapped to
a single DNF term. At line 14, each minterm in dd can
be mapped to a k-term DNF formula. With proper BDD
variable ordering, the complexity of this algorithm 3 is
O(kn).
4.5

NEGATIVE SAMPLE SPACE ENCODING

The algorithm of converting a negative sample to its
space BDD is similar to algorithm 3. The differences are
(1) all the terms must be evaluated as false and (2) the
conversion rule for a single term is negated. Algorithm 4
shows the conversion algorithm.
Again, suppose s = 101. For a single term to be evaluated as false, one of the following conditions must hold:
at least one of feature 1 and feature 3 appears as a negative literal, or feature 2 appears as a positive literal. The
generalization of this idea shown in line 3 to line 11. At
line 12, since all the terms must be evaluated as false,
the result dd is the AND of all the term dd. With proper
BDD variable ordering, the complexity of this algorithm
4 is O(kn).

1
2
3
4
5
6
7
8
9
10
11
12
13
14

Algorithm 4: Converting a negative sample to BDD
Input: Integers n, k, and an n-dimensional Boolean
vector s
Output: BDD dd
dd ← BDD One();
for j ∈ {1, 2, . . . , k} do
term dd ← BDD Zero();
for i ∈ {1, 2, . . . , n} do
if s[i] == 0 then
tmp dd ← (xji == pos);
else
tmp dd ← (xji == neg);
end
term dd ← BDD Or(term dd, tmp dd);
end
dd ← BDD And(dd, term dd);
end
return dd;

4.6

OBTAINING VERSION SPACE

Version space can be obtained by performing an AND of
all the above BDDs. Recall that each BDD represents a
set of hypotheses inside the hypothesis sub-space, which
agree with a positive sample or a negative sample. The
AND is equivalent to the set intersection operation so the
resulting BDD represents the version space.
In actual implementation, the AND of a set of BDDs is
accomplished by performing a sequence of AND operations on two BDDs. We observed that the ordering of
AND operations on BDDs significantly influences the
runtime. There can be two prferences: (1) Process the
hypothesis sub-space BDD first and (2) If k ≤ 2, process
positive sample BDDs before negative sample BBDs;
otherwise process negative sample BDDs before positive
sample BDDs.
To illustrate the first preference, Figure 5 shows the number of BDD nodes in the version space BDD versus the
number of processed samples. There are 100 features, 3
positive samples, and 800 negative samples. For the red
line, the first AND operation is applied to the hypothesis
sub-space BDD and a positive sample BDD. The next
two ANDs involve the remaining two positive sample
BDDs. The negative sample BBDs are processed afterward. For the green line, the first three positive sample
BDDs are processed first, followed by processing negative sample BDDs. The hypothesis sub-space BDD is
processed last.
The runtime is proportional to the number of BDD nodes.
It can be clearly observed that the difference in runtime
between the two cases is significant. The reason is that

4.6.1

processing the hypothesis sub-space BDD first can more
the version space.

Handling Non-Canonicality

BDD: complexityeffectively
constraint ordering
trim

# of BDD nodes
3000
2000

A hypothesis can be represented by different DNF formulas, e.g. a+b = b+a. Hence the size of version space
cannot be obtained by counting the number of minterms
in the version space BDD in general. Here we introduce
another BDD that forces each term in a DNF representation to be in lexicographical order, which reduces the permutation among terms. Algorithm 5 shows the procedure
to create a BDD having lexicographical order among two
terms. In total k−1 such BDDs are required. Next, when
the number of minterms in the version space BDD is in
the same order as B, we convert each minterm to its DNF
formula and then use a BDD to represent it. Since BDD
is a canonical representation, we are able to obtain the
size of version space.

k=0
Sub-space BDD last
k=3
Sub-space BDD first

0

1
52
103
154
205
256
307
358
409
460
511
562
613
664
715
766

1000

# of processed samples
Figure 5: Example to illustrate that processing hypothesis sub-space BDD at the beginning is more efficient
Table 1 shows the runtime comparison between processing positive sample BDDs first and processing negative
sample BDDs first. The comparison is presented as a ratio between the two. In each case, there are 100 features,
250 positive samples, and 250 negative negative samples.
The number of literals l is randomly selected in each run
and l ≤ 15. In each case, there are 10 runs for the positive first and 10 runs for the negative first. A geometric
mean of the 10 runtimes is calculated. Then, the ratio is
calculated from the two geometric means. The reason to
use the geometric mean is that the 10 runtimes can differ
significantly based on the selection of l. Table 1 shows
that for k ≤ 2, processing positive sample BDDs before
negative sample BDDs saves time, and vice versa.
Table 1: Runtime ratio of processing positive sample
BDDs first over processing negative sample BDDs first
k
1
2
3
4

pos-first/neg-first
1.89 ∗ 10−6
8.70 ∗ 10−2
1.76 ∗ 103
2.38 ∗ 105

For k = 1, the problem is monomial learning. For monomial learning, it is well known that positive samples are
far more important than negative samples, i.e. positive
samples are far more effective to reduce the version space
than negative samples. As a result, processing positive
sample BDDs first is more effective. This property seems
to somewhat carry over to the case k = 2. It is interesting
that the situation reverses for k = 3 and k = 4. The theoretical reason for this reverse is still unclear and should
be investigated further in the future.

1
2
3
4
5
6
7
8
9
10
11
12

Algorithm 5: BDD representing the k1 -th term is lexicographically smaller than the k2 -th term
Input: Integers n, k1 , k2
Output: BDD dd
dd ← BDD Zero();
eq dd ← BDD One();
for i ∈ {1, 2, . . . , n} do
cond1 ← BDD And(xki 1 == neg, xki 2 == pos);
cond2 ← BDD And(xki 1 == neg, xki 2 == dcare);
cond3 ← BDD And(xki 1 == pos, xki 2 == dcare);
cond = BDD Or(cond1, cond2, cond3);
tmp dd ← BDD And(eq dd, cond);
dd ← BDD Or(dd, tmp dd);
eq dd ← BDD And(eq dd, xki 1 == xki 2 );
end
return dd;

5

SAT-BASED LEARNING

The idea of SAT-based version space learning is similar to BDD-based encoding. The basic components are
the same: the hypothesis sub-space, the positive sample
spaces, and the negative sample spaces. The main difference is that SAT requires others encoding techniques
to restrict the number of clauses and the number of symbols. Let n be the number of features, l be the number
of literals, k be the number of terms, mp be the number of positive samples and mn be the number of negative samples. Then, the encoding method described below results in a CNF formula with Θ(nkl) symbols and
Θ(nkl + nkmp + kmn ) clauses.
Same as BDD encoding, each feature can appear in positive, negative or does not appear in a term. Hence, three
symbols are used to represent each case.

j
• Xi,1
is True iff the i-th feature in the j-th term appears in negative form
j
is True iff the i-th feature in the j-th term ap• Xi,2
pears in positive form
j
is True iff the i-th feature in the j-th term does
• Xi,3
not appear

Since exactly one of the three cases is true, one-hot constraints are required to enforce the requirement:
j
j
j
j
j
Πki=j Πni=i (Xi,1
+ Xi,2
+ Xi,3
)(¬Xi,1
+ ¬Xi,2
)
j
j
j
j
(¬Xi,1 + ¬Xi,3 )(¬Xi,2 + ¬Xi,3 ).

5.1

HYPOTHESIS SUB-SPACE ENCODING

For a given (l, k), we need to constrain the space to contain only l literals. It is the cardinality constraint. The
performance of different encoding methods for a cardinality constraint can be found in (Ben-Haim et al., 2012).
In our implementation, we choose the sequential counter
method (Sinz, 2005) because its performance is comparable to other encoding methods and it has the unit propagation property (Ben-Haim et al., 2012). The encoding
formula shown in (Sinz, 2005) cannot be used directly
because it is for cardinality ≤ l. A straightforward modification is used for cardinality = l, based on converting
the sequential counter circuit to SAT clauses. The encoding for the cardinality constraint requires additional
l(nk − 1) new symbols and Θ(nkl) clauses.
For this encoding, we use the same notation and symbol in (Sinz, 2005), so it is easier to get the difference between the modification and the original encoding, wherein k is the number of symbols passing to the
cardinality constraint and Si,j are additional symbols.
(x1 + ¬S1,1 )(¬x1 + S1,1 ),
Πkj=2 (¬S1,j ),
n
Πi=2 (¬xi + ¬Si−1,k ),
Πn−1
i=2 (xi + Si−1,1 + ¬Si,1 )(¬xi + Si,1 )(¬Si−1,1 + Si,1 ),
k
Πn−1
i=2 Πj=2 (xi + Si−1,j + ¬Si,j )(Si−1,j−1 + Si−1,j +
¬Si,j )(¬Si−1,j + Si,j )(¬xi + ¬Si−1,j−1 + Si,j ),
(xn + Sn−1,k )(Sn−1,k−1 + Sn−1,k ).
5.2

POSITIVE SAMPLE SPACE ENCODING

Again, given a positive sample s = 101. For a single
term to be evaluated as true, feature 1 and feature 3 must
not appear in negative form and feature 2 must not appear in positive form. Then, at least one term must be
evaluated as true. A naive encoding leads to nk clauses,
which is not feasible. To overcome this challenge, additional k symbols, A1 , A2 , . . ., Ak , are used such that Aj

is true if and only if the j-th term is evaluated as true.
With these additional symbols, the number of clauses reduces to (n + 1)k + 1. The requirement of at least one
term is evaluated as true is encoded by a single clause:
(Σkj=1 Aj ),
j
and for each j, the relation of Aj and Xi,δ
is maintained
by
j
Πni=1 (¬Xi,2−s[i]
+ ¬Aj ), and
j
+ Aj ).
(Σni=1 Xi,2−s[i]

5.3

NEGATIVE SAMPLE SPACE ENCODING

Given a negative sample s = 101. For a single term to
be evaluated as false, at least one of feature 1 and feature
3 must appear in negative form or feature 2 appear in
positive form. Besides, all the terms must be evaluated
as false. For each sample, k clauses are required and
each clause encodes that a term is evaluated as false. The
overall encoding is
j
Πkj=1 (Σni=1 Xi,2−s[i]
).

5.4

SIZE OF VERSION SPACE

Each satisfiable assignment in the above SAT problem
can be mapped to a DNF formula. The size of version space can be obtained by counting the number of
satisfiable assignments. A common approach is to add
new clauses to remove previous satisfiable assignments
and then call the SAT solver again. Removing a satisfiable assignment is a standard approach and omitted here.
Note that we use the same approach to deal with the noncanonicality problem described in BDD-based learning,
except the lexicographical order constraint is represented
by SAT clauses.

6

EXPERIMENTS

We use CUDD-3.0.0 (Somenzi, 2015) to implement the
BDD-based learning and use Lingeling (Biere, 2013)
for the SAT-based learning. The dynamic variable reordering option in CUDD is disabled to facilitate the
study of various aspects of the tool performance.
6.1

RUNTIME COMPARISON

We observed different characteristics of runtime between
the SAT-based method and the BDD-based method. For
example, we use a simple experiment to illustrate their
differences. In this experiment, the target concept is assumed to be a 5-literal monomial (i.e. k = 1 and l = 5).

BDD vs SAT: runtime trend
BDD vs SAT: runtime trend

0 positive sample
0 positive sample

log10(second)

Hypothesis space (l)

2 positive samples

Hypothesis
space (l) space (l)
Hypothesis
Computational limitation in BDD

There are 1000 randomly generated negative samples.
There can be 0, 1, and 2 positive samples. Figure 7 and
Figure 6 show the runtime results. Each point is the average of runtimes over 10 runs. The size bound B is set
to 1, so if the size of version space is large than 1, the
SAT-based learning would stop after finding the second
fitting hypothesis. Note that in this experiment, for all
cases with l < 5 the calculated size of version space is
always 0, for l = 5 the calculated size of version space
is exactly 1, and for l > 5 the calculated size of version space is always larger than 1. This shows that both
learning methods can identify the correct hypothesis subspace and the correct hypothesis.
The results show that the runtime of the BDD-based
method is exponential to l. On the other hand, the SATbased method has a peak runtime at l = 5, i.e. the size
of version space is 1. Figure 8 shows another interesting property of BDD-based learning where the number
of positive sample is 1. In each case, the positive sample BDD is processed first, followed by processing the
negative sample BDDs. The figure shows the number
of BDD nodes as a function of the number of processed
samples. As it can be observed, the peak number of BDD
nodes occurs earlier in the process than later, for example within the first 200 samples. This implies that the
computational limitation occurs within the processing of
the first 200 samples. As a result, it is not the case that
a larger dataset implies a longer run time. As mentioned
above, the deciding factor for the runtime is the length l.
Figure 9 shows similar runtime results as those shown
in Figure 8. In this experiment, the target concept is a
2-term DNF with l = 5 where one term is of length 2
and the other item is of length 3. The number of positive
samples is 5, the number of negative samples is 500, and
the number of features is 100. Similarly, positive sample
BDDs are processed first. Observe that the peak number
of BDD nodes also occurs earlier in the process and the
length l is the deciding factor for the runtime.

Figure 7: SAT runtime

100 var, 2 pos, target l = 5

# of BDD nodes (million)
2
1.5

1

l=6
l=5
l=4

0.5
0

# of processed samples

Figure 8: The peak number of nodes grows as l increases
# of BDD nodes (million)
1.4
1.2
1
0.8
0.6
0.4
0.2
0

l=6
l=5
l=4

1
35
69
103
137
171
205
239
273
307
341
375
409
443
477

Figure 6: BDD runtime

1 positive sample
1 positive sample

1
60
119
178
237
296
355
414
473
532
591
650
709
768
827
886
945

1 positive sample
2 positive samples

log10(second)

log10(second)

0 positive sample

# of processed samples

Figure 9: Similar result for 2-term DNF

6.2

COMPARISON WITH OTHER METHODS

To compare VeSC-CoL with other concept learning
methods such as CART (Breiman et al., 1984) and
ID3 (Quinlan, 1986), we continue the experiment above
where the target concept is a 5-literal monomial. There
are 100 features, 2 positive samples, and 1000 negative
samples. Table 2 shows the learning result. In each case,
VeSC-CoL is able to correctly identify the target concept. On the other hand, the results from CART are less
meaningful. For the first three tasks, each CART result
has only 1 literal relevant to the target concept while providing 6 unrelated literals and missing 4 literals in the
target. For the last task, the CART learning result is a
2-term DNF in which no feature is related to the target.

Table 2: VeSC-CoL learns the target monomial, while CART and ID3 produce irrelevant results
VeSC-CoL
x2 x63 x75 x78 x80
x39 x45 x72 x74 x95
x2 x14 x52 x57 x87
x40 x45 x64 x74 x87
x57 x58 x77 x95 x98

CART
x3 x4 x28 x47 x53 x55 x80
x5 x16 x35 x45 x55 x56 x59
x11 x14 x24 x61 x64 x90 x92
x4 x8 x45 x47 x64 x74 x89
x5 x29 x38 x43 x79 x99 + x3 x5 x29 x38 x43 x49 x79 x99

The learning results from ID3 are dissimilar to the target
concept as well.
6.3

of positive samples is larger than 5 and the number
of negative samples is 10000.

COMPLEXITY ORDERING

As mentioned before, for two hypothesis sub-space Hi
and Hj of k-term DNF, we consider the complexity of Hi
is smaller than Hj if li < lj where li and lj are the numbers of literals in the hypotheses in Hi and Hj , respectively. Recall that each hypothesis sub-space comprises
hypotheses of equal length. Note that this complexity
ordering is based on two main reasons: (1) As shown
above, BDD-based learning is sensitive to the length l.
Hence, the ordering ensures that the learning processes
the computationally-easier hypothesis sub-spaces first.
(2) In practice, a concept with a smaller length is easier to interpret than that with a larger length. Therefore,
it is preferred to uncover a shorter concept if possible.
6.4

ID3
x2 x3 x4 x30 x47 x53 x81
x8 x40 x45 x64 x74 x87
x5 x6 x16 x35 x45 x56 x59
x2 x14 x24 x61 x64 x90 x92
x5 x6 x11 x14 x18 x34 x45

ACCURACY OF VeSC-CoL

In the experiments to compare VeSC-CoL with CART
and ID3, we observe that VeSC-CoL can always uncover
the correct answer. Note that it is possible to construct
a dataset to fool the VeSC-CoL tool so that it reports an
incorrect answer even with the cardinality bound B = 1.
However, with randomly generated datasets, we observe
that when the data is sufficiently large and B = 1, VeSCCoL always finds the correct target concept assuming the
concept is in the hypothesis space considered (e.g. 3term DNF up to length 15). In particular, we observed
in the following experiments that VeSC-CoL always find
the correct answer:
• All 1-term DNF cases with up to 100 features and l
up to 7. The number of positive samples can be 0 to
2 and the number of negative samples is 10000.
• All 1-term DNF cases with up to 500 features and
l up to 8. The number of positive samples is larger
than 5 and the number of negative samples is 10000.
• All 2-term DNF cases with up to 100 feature and l
up to 8. For each term, there exists a positive sample
that can be explained only by the term. The number

• All 3-term DNF cases with up to 100 feature and l
up to 9. For each term, there exists a positive sample
that can be explained only by the term. The number
of positive samples is larger than 10 and the number
of negative samples is 10000.

7

CONCLUSION AND FUTURE WORK

We propose VeSC-CoL, a version space cardinality
based concept learning tool, for learning extremely imbalanced datasets. We use experiment results to note
several key properties of the tool. VeSC-CoL is applicable without cross-validation. The version space cardinality bound is used to control the quality of the learning
result. In our study, we observed that VeSC-CoL can always identify the correct target concept assuming that the
concept is included in one of the hypothesis sub-spaces
to be analyzed. VeSC-CoL is supported by two implementations, one based on BDD and the other based on
SAT. Their runtimes can be quite different. Therefore
VeSC-CoL runs the two methods in parallel and stops
when one of them completes.
One challenge is to generalize the encoding method. The
current encoding method is closely related to the k-term
DNF representation and the complexity measure. Suppose a hypothesis is represented in BDD and the complexity measure is the number of BDD nodes, the encoding will be different. Given a hypothesis representation
and a complexity measure, finding an encoding method
is a non-trivial task that needs further investigation.
While the experiments show several interesting properties of the implementations, further research is required
to analyze the theoretical reasons behind those properties and to formalize their descriptions. While the current
work focuses on the development of the tool, its performance in actual applications (such as those in EDA and
Test) will be assessed and reported in the near future.

References
Yael Ben-Haim, Alexander Ivrii, Oded Margalit, and
Arie Matsliah. Perfect hashing and CNF encodings
of cardinality constraints. In International Conference
on Theory and Applications of Satisfiability Testing,
pages 397–409. Springer, 2012.
Armin Biere. Lingeling, plingeling and treengeling entering the sat competition 2013. Proceedings of SAT
Competition, 2013.
L. Breiman, J. Friedman, R. Olshen, and C. Stone.
Classification and Regression Trees. Wadsworth and
Brooks, Monterey, CA, 1984.
Randal E Bryant. Graph-based algorithms for boolean
function manipulation. Computers, IEEE Transactions on, 100(8):677–691, 1986.
Haym Hirsh. Generalizing version spaces. Machine
Learning, 17(1):5–46, 1994.
Haym Hirsh, Nina Mishra, and Leonard Pitt. Version
spaces and the consistency problem. Artificial Intelligence, 156(2):115–138, 2004.
Tessa Lau, Steven A Wolfman, Pedro Domingos, and
Daniel S Weld. Programming by demonstration using version space algebra. Machine Learning, 53(1-2):
111–156, 2003.
Tom Michael Mitchell. Version spaces: an approach
to concept learning. Technical report, STANFORD
UNIV CALIF DEPT OF COMPUTER SCIENCE,
1978.
Leonard Pitt and Leslie G Valiant. Computational limitations on learning from examples. Journal of the ACM
(JACM), 35(4):965–984, 1988.
J. Ross Quinlan. Induction of decision trees. Machine
learning, 1(1):81–106, 1986.
Carsten Sinz. Towards an optimal CNF encoding of
boolean cardinality constraints. In International Conference on Principles and Practice of Constraint Programming, pages 827–831. Springer, 2005.
Fabio Somenzi. CUDD: CU decision diagram package
release 3.0.0. Public software, University of Colorado
at Boulder. 2015.
Li-C Wang. Experience of data analytics in eda and
testprinciples, promises, and challenges. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 36(6):885–898, 2017.

