Learning Logistic Circuits
Yitao Liang Guy Van den Broeck








Learning Logistic Circuits
    Yitao Liang Guy Van den Broeck

Computer Science Department

University of California, Los Angeles




    December 30, 2023
==========================================================================================================




This paper proposes a new classification model called logistic circuits. On MNIST and Fashion datasets, our learning algorithm outperforms neural networks that have an order of magnitude more parameters. Yet, logistic circuits have a distinct origin in symbolic AI, forming a discriminative counterpart to probabilistic-logical circuits such as ACs, SPNs, and PSDDs.
We show that parameter learning for logistic circuits is convex optimization, and that a simple local search algorithm can induce strong model structures from data.




§ INTRODUCTION

Circuit representations are a promising synthesis of symbolic and statistical methods in AI. They are “deep” layered data structures with statistical parameters, yet they also capture intricate structural knowledge.
Recently, many representations have been proposed for learning tractable probability distributions: arithmetic circuits <cit.>, weighted SDD <cit.>, PSDD <cit.>, cutset networks <cit.> and sum-product networks (SPNs) <cit.>. 
Collectively, these approaches achieve the state of the art in discrete density estimation and vastly outperform classical probabilistic graphical model learners <cit.>. However, we have not observed the same success when deploying circuit representations for classification or discriminative learning. Probabilistic circuit classifiers significantly lag behind the performance of neural networks <cit.>.

In this paper, we propose a new classification model called logistic circuits, which shares many syntactic properties with the representations mentioned earlier. One can view logistic circuits as the discriminative counterpart to probabilistic circuits. Owing to their elegant properties, learning the parameters of a logistic circuit can be reduced to a logistic regression problem and is therefore convex. 
Learning logistic circuit structure is reduced to a simple local search problem using primitives from the probabilistic circuit learning literature <cit.>.

We run experiments on standard image classification benchmarks (MNIST and Fashion) and achieve accuracy higher than much larger MLPs and even CNNs with an order of magnitude more parameters. For example, logistic circuits obtain 99.4% accuracy on MNIST. 
Compared to other tractable learners on MNIST, and the state-of-the-art discriminative SPN learner in particular <cit.>, our logistic circuit learner cuts the error rate by a factor of three.
Furthermore, we show our learner is highly data efficient, managing to still learn well with limited data. 
 
This paper proceeds as follows. 
Section <ref> introduces the syntax and semantics of logistic circuits. 
Sections <ref> and <ref> describe our parameter and structure learning algorithms, which Section <ref> evaluates empirically.
Section <ref> elaborates on the connection with tractable generative models, after which we conclude with related and future work.

 


§ REPRESENTATION
 
This section introduces the logistic circuit representation.



  §.§.§ Notation

We use uppercase X to denote a Boolean random variable and lowercase x for a specific assignment to it. Interchangeably, we also interpret Boolean random variables as logical variables. A set of variables X and their joint assignments x are denoted in bold. A complete assignment x to all variables is a possible world, or interchangeably, a data sample. Literals are variables X or their negation X. Logical sentences are constructed from literals and connectives such as AND and OR in the standard way. An assignment x that satisfies a logical sentence α is denoted as xα. 





 §.§ Logical Circuits


A logical circuit is a directed acyclic graph  representing a logical sentence, as depicted in Figure <ref> (ignoring parameters for now). 
Each inner node is either an AND gate or an OR gate.[We consider negation-normal-form circuits where no negation is allowed except at the leafs/inputs <cit.>.] 
A leaf (input) node represents a Boolean literal, that is, X or X, where the node can only be satisfied if X is set to 1 (true) respectively 0 (false).

The following properties are key for logical circuits to be well-behaved <cit.>.
An AND gate is decomposable if its inputs depend on disjoint sets of variables.  
For example, the top-most AND gates in Figure <ref> depend on A in their one input and on {B,C,D} in their other input. 
When an AND gate has two inputs, they are called its prime (left) and sub (right).
An OR gate is deterministic if for any single complete assignment, at most one of its inputs can be set to 1. For example, the left input to the root OR gate  in Figure <ref> is 1 precisely when A=1, and its other input is 1 precisely when A=0.


Logical circuits can be extended to probabilistic circuits that represents a probability distribution over binary random variables, for example by parameterizing wires with conditional distributions <cit.>.
Probabilistic circuits have been successfully used for generative learning <cit.>. Section <ref> will discuss probabilistic circuits in more detail.



 §.§ Logistic Circuits


This paper proposes logistic circuits for classification. Syntactically, they are logical circuits where every AND is decomposable and every OR is deterministic. 
However, logistic circuits further associate real-valued parameters θ_1, …, θ_m with the m input wires to every OR gate. For example, the root OR node in Figure <ref> associates parameters -2.6 and -5.8 with its two inputs.

To give semantics to logistic circuits, we first characterize how a particular complete assignment x (one data example) propagates through the circuit.



Consider a deterministic OR gate n.
The Boolean flow f(n, x,c) of a complete assignment x between parent n and child c is 

    f(n, x,c) =  
        1     x c 
     
        0


For example, under the assignment A=0, B=1, C=1, D=0, the root node in Figure <ref> has a Boolean circuit flow of 0 with its left child and 1 with its right child.
Note that the determinism property guarantees that under every OR gate, for a given example x, at most one wire has a flow of 1, and the rest has a flow of 0. 

We are now ready to define the logistic circuit semantics.


A logistic circuit node n defines the following weight function _( x).


  – If  is a leaf (input) node, then _( x) = 0.


  – If  is an AND gate with children c_1,…,c_m, then

    _( x) =  ∑_i=1^m _c_i( x).



  – If  is an OR gate with (child node, wire parameter) inputs (c_1,θ_1),…, (c_m, θ_m), then

    _( x) =    ∑_i=1^m  f(n,  x, c_i) ·(_c_i( x) + θ_i).


At root node r with weight function _r( x), the logistic circuit defines the posterior distribution on class variable Y as

    ( Y = 1 | x) = 1/1 + exp(-_r( x)  ).


Using Boolean circuit flow, this definition essentially collects all the parameters on wires with flow 1 that reach the root, in order to then make a prediction.
This is illustrated in Figure <ref> by coloring red the gates and wires whose parameters and weight function are propagated upward for the example assignment A=0, B=1, C=1, D=0.
The logistic circuit in Figure <ref> defines the same posterior predictions as the table in Figure <ref>. Specifically, for the example assignment, the weight function simply sums the parameters colored in red: -5.8+2.3+3.9+1.5 = 1.9. We then apply the logistic function (Eq. <ref>) to get the classification probability (Y=1 |) = 1/1+exp(-1.9) = 86.99%. 




 §.§ Real-Valued Data


The semantics given so far assume Boolean inputs , which is a rather restrictive assumption and prohibits many machine learning applications.
Next, we augment the logistic circuit semantics such that they can classify examples with continuous variables.

We interpret real-valued variables q ∈ [0,1] as parameterizing an (independent) Bernoulli distribution (cf. <cit.>). Each continuous variable represents the probability of the corresponding Boolean random variable X. For example, with q setting A=0.4, B=0.8, C=0.2, and D=0.7, the probability of A  D would be (1-0.4)· 0.7=0.42. The same distribution defines a probability for each logical sentence, and therefore each node in the logistic circuit.
This allows us to generalize Boolean flow as follows.



Consider a deterministic OR gate n.
Let q be a vector of probabilities, one for each variable in X.
The probabilistic flow f(n, q,c) of vector q between parent n and child c is 

    f(n, q,c) = _ q(c | n) = _ q(c  n)/_ q(n)  = _ q(c)/_ q(n) ,

where _ q(.) is the fully-factorized distribution where each variable in  X has the probability assigned by q.

Logistic circuit semantics now support continuous data (after normalizing to [0,1]), simply by replacing Boolean flow with probabilistic flow in Definition <ref>.
Note that probabilistic circuit flow has Boolean circuit flow as a special case, when q happens to be binary. 
Furthermore, due to the determinism and decomposability properties, the probabilities in Definition <ref> can be computed efficiently, together with all probabilistic circuit flows and weight functions in the logistic circuit. We defer the discussion of these computational details to Section <ref>.  
In the rest of this paper, we will abuse notation and have  refer to Boolean inputs as well as continuous inputs q interchangeably.



§ PARAMETER LEARNING



A natural next question is how to learn logistic circuit parameters from complete data, for a fixed given circuit structure (structure learning is discussed in Section <ref>). Furthermore, we ask whether those learned parameters are guaranteed to be optimal, globally minimizing a loss function.
We address these questions by showing how parameter learning can be reduced to logistic regression on a modified set of features, owing to logistic circuits' strong properties.



 §.§ Special Cases


Before presenting the general reduction, we briefly discuss two special cases that establish some intuition.



  §.§.§ Linear Weight Functions
 
Consider a vanilla logistic regression model on input variables (features) X. 
Does there exist an equivalent logistic circuit with the same weight function?
For sample , logistic regression with parameters θ would have weight function ·θ. 
Following Definition <ref>, we obtain such a simple weight function (linear in the input variables) by placing OR gates over complementary pairs of literals and associating a θ parameter which each wire (see Figure <ref>).[The negated variable inputs and parameters θ_ X are redundant, but we keep them for the sake of consistency. Alternatively, we can fix θ_ X = 0 for all X to remove this redundancy.] A large parent AND gate collects these variable-wise weights into a single linear sum. Finally, an OR gate at the root adds the bias term regardless of the input.

For each classical logistic regression model, there exists an equivalent logistic circuit model.








  §.§.§ Boolean Flow Indicators

Next, let us consider a special case that makes no assumptions about circuit structure, but that requires the inputs to be fully binary. 
Such a circuit would have Boolean flows through every wire. 
Instead of working with the input variables X, we can introduce new features that are indicator variables, telling us how the example propagates through the circuit, and which wires have a Boolean flow that reaches the circuit root. The circuit flows (indicators) decide which parameters are summed into the weight function; this process has been implicitly revealed in Figure <ref>. By introducing such indicators, we can always obtain a linear weight function of composite features that are extracted from sample . 
Next, we generalize this idea of introducing wire features to arbitrary logistic circuits.



 §.§ Reduction to Logistic Regression

We will now consider the most general case, with continuous input data and no assumptions on the circuit structure.

 

Any logistic circuit model can be reduced to a logistic regression model over a particular feature set.



Logistic circuit cross-entropy loss is convex.


To prove Proposition <ref>, we need to rewrite the classification distribution in Definition <ref> as follows.

    ( Y = 1 | x) = 1/1+ exp(- x·θ).
 
Here, x is some vector of features extracted from the raw example x. This feature vector can only depend on x; not on the parameters θ. 
Thus, the fundamental question is whether we can decompose _n() into x·θ for all nodes n. We prove this to be true by induction:


  – Base case:  is a leaf (input) node. It is obvious _n can be expressed as x·θ since _n always equals 0.



  – Induction step: assume  of all the nodes under node n can be expressed as x·θ. We need to consider two cases:



  * If  is an AND gate having (w.l.o.g.) two children, prime p and sub s. Given _p = x_p·θ_p and _s =x_s ·θ_s, 

    _   =  x_p·θ_p + x_s ·θ_s 
    
       = [ x_p; x_s ]·[ θ_p; θ_s ].



  * If  is an OR gate with (child node, wire parameter) inputs {(c_1,θ_1),…,(c_m,θ_m)}. Given _c_i =  x_c_i·θ_c_i,

    _    = ∑_i  f(n, x,c_i) ·( x_c_i·θ_c_i+ θ_i) 
       = [ f(n, x,c_1) ·x_c_1;        f(n, x,c_1);                  ⋮; f(n, x,c_m) ·x_c_m;        f(n, x,c_m) ]·[ θ_c_1;   θ_1;     ⋮; θ_c_m;   θ_m ].




Note that this proof holds true regardless of whether the input sample x is binary or real-valued.
With this proof, it is obvious that learning the parameters of a logistic circuit is equivalent to logistic regression on features x. 
We refer readers to <cit.> for a detailed proof that logistic regression is convex. 

Given this correspondence, any convex optimization technique can now be brought to bear on the problem of learning the parameters of a logistic circuit. In particular, we use stochastic gradient descent for this task.




 §.§ Global Circuit Flow Features


In the proof of Proposition <ref>, features x  are computed recursively by induction. However, it is not clear what these features represent, and how they are connected to the input data. In this section we assign semantics to those extracted features. They are the global circuit flow of the observed example through the circuit. Global circuit flow is defined with respect to the root of a logistic circuit.


    
    Consider a logistic circuit over variables X rooted at OR gate r.  
    The global circuit flow f_r(n, , c) of input  between parent n and child c is defined inductively as follows.
    The global circuit flow between root r and its child c is the (local) probabilistic circuit flow: f_r(r, , c) = f(r, , c).
    Then, for any node n with parents v_1,…,v_m, we have that
    
        
  – if n is an AND gate, global flow from child c is
        
    f_r(n, , c) = ∑_i=1^m f_r(v_i, , n),

        
  – if n is an OR gate, global flow from child c is
        
    f_r(n, , c)    =  f(n, ,c) ·∑_i=1^m  f_r(v_i, , n).

    

The red wires in Figure <ref> have a global circuit flow of 1 for the given Boolean input. In general, global circuit flow assigns a continuous probability value to each wire.

Based on global circuit flow, we postulate the following alternative semantics for logistic circuits.


Let 𝒲 be the set of all wires (n,
θ,c) between OR gates n and children c with parameters θ.
Then, a logistic circuit rooted at node r defines the weight function

    _r() = ∑_(n,θ,c) ∈𝒲 f_r(n,,c) ·θ.


 
Note that the definition of global circuit flows, as well as our alternative semantics, follow a top-down induction. 
In contrasts, the original semantics in Definition <ref> follow a bottom-up induction.
We resolve this discrepancy next.


The features x constructed in the proof of Proposition <ref> are equivalent to global flows f_r(n,,c).


The bottom-up semantics of Definition <ref> and the top-down semantics of Definition <ref> are equivalent.

We defer the proof of this proposition to Appendix <ref>.

Recall that without parameters, a logistic circuit is simply a logical circuit, which means that gates in a logistic circuit have real meaning: they correspond to some logical sentence. Hence, the values of global circuit flow features x correspond to probabilities of these logical sentences according to the input vector . This provides us with a precious opportunity to assign meaning to the features learned by logistic circuits. We will revisit this point in Section <ref>, where we also visualize some global circuit flow features.



 §.§ Computing Global Flow Features Efficiently


While logistic circuit parameter learning is convex, we would like to also guarantee that the required feature computation is tractable. This section discusses efficient methods to calculate global flow features x (i.e., f_r(n, , c)) from training samples x offline, before parameter learning. 
 
As is clear from Definition <ref>, circuit flows make extensive use of node probabilities.
We design our computation to consist of two parts, and dedicate the first part to the calculation of node probabilities. The first part is a bottom-up linear pass over the circuit starting with leaf nodes whose probabilities are directly provided by the input sample; see the details in Appendix <ref>.
The second part makes use of these node probabilities to calculate the global circuit flow features in linear time. 
It is a top-down implementation of the recursion in Definition <ref>; see its details in Appendix <ref>. 
Note that these computations correspond to the partial derivative computations used in arithmetic circuits for the purpose of probabilistic inference <cit.>.

Our algorithm is completely compatible with fast vector arithmetic: instead of inputting one single sample each time,  one can directly supply the algorithms with a vector of samples (e.g., a mini batch), and this yields significant speedups. 




§ STRUCTURE LEARNING
 
This section presents an algorithm to learn a compact logical circuit structure for logistic circuits from data. 
For simplicity of designing the primitive operations, we assume AND gates always have two inputs (prime and sub).



 §.§ Learning Primitive

The split operation was first introduced to modify the structure of PSDD circuits <cit.>. We adopt it here with minor changes[Compared to the splits in LearnPSDD <cit.>, we do not limit constraints to be on primes.] as the primitive operation for our structure learning algorithm. 
Splitting an AND gate happens by imposing two additional constraints that are mutually exclusive and exhaustive, in particular by making two opposing variable assignments.
Executing a split creates partial copies of the gate and some of its decedents. Furthermore, one can choose to duplicate additional nodes up to a fixed depth (3 in our experiments).
We refer readers to <cit.> for further details on the algorithm for executing splits.

Splits are ideal primitives to change the classifier induced by a logistic circuit: they directly affect the circuit flows (see Figure <ref>). By imposing constraints on AND gates, splits alter the node probabilities associated with the affected AND gates. Following Definition <ref>, the circuit flows on the wires out of those AND gates adapt accordingly. While Figure <ref> focuses on the immediately affected wires, the effect of a split on circuit flows can propagate downward for several levels, depending on the depth of node duplication. Still the effects of a split on both the structure of a logistic circuit and the circuit flows are very local and contained in the sub-circuit rooted at the OR parent of the split AND gate. However, its effect on the parameters is global. Once a split is executed, the whole parameter set needs to be re-trained.

	




   


 §.§ Learning Algorithm

The overall structure learning algorithm for logistic circuits, built on top of the split operation, proceeds as follows. Iteratively, one split is executed to change the structure, followed by parameter learning. 
We only consider single-variable split constraints and first select which AND gate to split, followed by a selection of which variable to split on.

When using gradient descent, one hopes that the parameter on the AND gate output consistently has its partial derivatives pointing in the same direction for all training examples. This will steadily push the parameter to a large magnitude. 

If this is not the case, we will use splits to alter the flow of examples through the circuit.
Specifically, those AND gates whose associated output parameter has a large variance of its partial derivative (that is, the derivative of the loss function w.r.t. that parameter) requires splitting for the parameters to improve.  We simply select the AND gate whose output parameter has the highest training variance.

Given an AND gate to split, we consider candidate variables X to execute the split with. We construct two sets of training examples that affect this node: in one group, each example is weighted by the marginal probability of X; in the other, 
with the marginal probability of X.  
Next, we calculate the within-group weighted variances of the partial derivatives.
The variable with the smallest weighted variances gets picked, as this suggests the split will introduce new parameters with gradients that align in one direction.
   

   
          
     
   



§ EMPIRICAL EVALUATION
 

In this section, we empirically evaluate the competitiveness of our learner on three aspects: classification accuracy, model complexity,  and data efficiency.[Open-source code and experiments are available at 
<https://github.com/UCLA-StarAI/LogisticCircuit>.]
 Moreover, we visualize the most important active feature with regards to the given sample to provide local interpretation for why the learned logistic circuit makes such classification.
 

 §.§ Setup & Data Preprocessing

 We choose MNIST and Fashion[A dataset of Zalando's images,  intended as a more challenging drop-in replacement of MNIST <cit.>.] as our testbeds.
 Since logistic circuits are intended for binary classification, we use the standard “one vs. rest" approach to construct an ensemble multi-class classifier such that our method can be evaluated on these two datasets. When running the binary logistic circuit, we transform pixels that are smaller than their mean plus 0.05 standard deviation to 0 and the rest to 1. When running the real-valued version, we transform pixels to [0,1] by dividing them by 255. All experiments start with a predefined initial structure; we defer its details to Appendix <ref>.
  The learned structure with the highest F1 score on validation after 48 hours of running is used for evaluation. All experiments are run on single CPUs.


   


 §.§ Classification Accuracy


Table <ref> summarizes the classification accuracy on test data. Learning a logistic circuit on the binary data is on par with a 3-layer MLP; the real-valued version outperforms 5-layer MLPs and even CNNs with 3 convolutional layers. The fact that logistic circuits achieve better accuracy than CNNs is surprising, since logistic circuits do not use convolutions, which are specifically designed to exploit image invariances. 

In addition, we would like to emphasis our comparison with two of the baselines. As parameter learning of logistic circuits is equivalent to logistic regression, one can view structure learning of logistic circuits as a process of constructing composite features from raw samples.  
The significant improvement over standard logistic regression demonstrates the effectiveness of our method in extracting valuable features; using kernel logistic regression can only partially bridge the gap in performance, yet as shown later, it does so at the cost of introducing many more parameters. 

We also want to call attention to our comparison with RAT-SPN, the current state of the art in discriminative learning for probabilistic circuits. SPN is another form of circuit representation, with less restrictive structure. Parameter learning in SPN is not convex and generally requires other techniques such as EM or non-convex optimization. The empirical observation that our method achieves significantly better classification accuracy than RAT-SPN demonstrates that in structure learning, imposing more restrictions on the model's structural syntax may be beneficial. The syntactic restriction of logistic circuits requires decomposability and determinism; without them, convex parameter learning does not appear to be possible. 
As structure learning is built on top of parameter learning, a well-behaved parameter learning loss with a unique optimum can provide more informative guidance about how to adapt the structure, leading to a more competitive structure learning algorithm overall.





 §.§ Model Complexity & Data Efficiency

Table <ref> summarizes the size of all compared models when achieving the reported  accuracy. We can conclude that logistic circuits are significantly smaller than the alternatives, despite attaining higher accuracy. 

We design the next set of experiments to specifically investigate how well our structure learning algorithm performs under the setting where the number of training samples is limited.  We have two additional sets of experiments, where only 2% and 10% of the original training data is supplied. 
Table <ref> summarizes the performance in this limited-data setting. 
We mainly compare against a 5-layer MLP and CNN with 3 convolutional layers, whose performance is on par with our method under the full-data setting. As summarized in Table <ref>, except on MNIST with 10% training samples, real-valued logistic circuits achieve the best classification accuracy. Moreover, in both versions of logistic circuits, when the available training samples are reduced from 100% to 2%, the accuracy only drops by around 3% when evaluating on MNIST; around 5% on Fashion. In contrast, a much larger drop occurs for 5-layer MLP and CNN. Specifically, MLP's accuracy drops by 5% (9%) while CNN's accuracy drops by 4% (7%) on MNIST (Fashion). This small magnitude of accuracy decrease illustrates how data efficient our proposed structure learning algorithm is.

Except on MNIST with 10% training samples, real-valued logistic circuits achieve the best classification accuracy. From a top-down perspective, each OR gate of a logistic circuit presents a weighted choice between its wires. Hence, one can view a logistic circuit as a decision diagram.
Under this perspective, splits refine OR gates' branching rules. As each branching rule naturally applies to multiple samples, we hypothesize that the splits selected by our structure learning algorithm reflect the general conditional feature information present in the dataset.





 §.§ Local Explanation


Next, we aim to share some insights about how to explain the learned logistic circuit. Specifically, we investigate the question: “Why does the logistic circuit classify a given sample  as y?” Since any logistic circuit can be reduced to a logistic regression classifier, we can easily find the active global flow feature that contributes most to the given sample's classification probability. That is, the feature that maximizes x·θ. We visualize one such feature for MNIST data and one for Fashion in Figure <ref> by marking the variables used in the their corresponding logical sentences.





§ CONNECTION TO PROBABILISTIC CIRCUITS
 
In recent years, a large number of tractable probabilistic models have been proposed as a target representation for generative learning of a joint probability distribution: arithmetic circuits <cit.>, weighted SDD <cit.>, PSDD <cit.>, cutset networks <cit.> and sum-product networks (SPNs) <cit.>.
These representations have various syntactic properties. Some put probabilities on terminals, others on edges. Some use logical notation (AND, OR), others use arithmetic notation (×,+).
Nevertheless, they are all circuit languages built around the properties of decomposability and/or determinism.

For our purpose, we consider a simple probabilistic circuit language based on the logistic circuit syntax, where now the θ parameters are assumed to be  normalized probabilities.[We also assume smoothness <cit.>.]


A probabilistic circuit node n defines the following joint distribution.


  – If  is a leaf (input) node, then _n() =[ n].


  – If  is an AND gate with children c_1,…,c_m, then

    _n() =  ∏_i=1^m _c_i().



  – If  is an OR gate with (child node, wire parameter) inputs (c_1,θ_1),…, (c_m, θ_m), then

    _n( x) =    ∑_i=1^m  _c_i()·θ_i.




Figure <ref> shows a probabilistic circuit for the joint distribution (Y,A,B,C,D). This tractable circuit language is a relaxation of PSDDs <cit.> and a specific type of SPN <cit.> where determinism holds throughout. It is also a type of arithmetic circuit.

We are now ready to connect logistic and probabilistic circuits. It is well known that logistic regression is the discriminative counterpart of a naive Bayes generative model <cit.>. A similar correspondence holds between our logistic and probabilistic circuits.


Consider a probabilistic circuit whose structure is of the form (Y α)  ( Y β), where sub-circuits α and β are structurally identical.
Then, there exists an equivalent logistic circuit for the conditional probability of Y in the probabilistic circuit. Moreover, this logistic circuit has structure α and its parameters can be computed in closed form as log-ratios of probabilistic circuit probabilities.


We first depict this correspondence intuitively in Figure <ref>. The logistic circuit has the same structure as the two halves of the probabilistic circuit, and its parameters are computed from the probabilistic circuit probabilities. The distributions (Y=1 | A,B,C,D) represented by the circuits in Figures <ref> and <ref> are identical. 



  
Formal Correspondence
Next, we present the formal proof of this correspondence for binary . 
Recall that in our circuits, only the input wires of OR gates are parameterized. Let 𝒲_δ be the set that contains all these wires in circuit δ: 
    𝒲_δ = {(n, c) | c is a gate with parent OR gate  n }.
 
After expanding the equations in Definition <ref> and following the top-down definition of global circuit flow (i.e., following Definition <ref>), one finds that the joint distribution induced by a probabilistic circuit δ can be rewritten as

    _δ() = ∏_(n, c) ∈𝒲_δ f_δ(n,,c) ·θ_(n,c)^δ.

We will exploit this finding in the derivation of the conditional distribution induced by the probabilistic circuit γ = (Y α)  ( Y β).

    _γ(Y=1 |) 
          =_γ(Y=1)_α()/_γ(Y=0)_β() + (Y=1)_α()
          = 1/1+_γ(Y=0)_β()/_γ(Y=1)_α()
          =1/1+_γ(Y=0)∏_(n,c) ∈𝒲_β f_β(n,,c)θ_(n,c)^β/_γ(Y=1)∏_(n,c) ∈𝒲_α f_α(n,,c)θ^α_(n,c)

As stated in Proposition <ref> and shown in Figure <ref>, sub-circuits α and β share the same structure. Therefore, we can further simplify this equation as follows.

    _γ(Y=1 |) 
          = 1/1+_γ(Y=0)/_γ(Y=1)∏_(n,c) ∈𝒲_α f_α(n, , c) θ^β_(n,c)/θ^α_(n,c)
          = 1/1+exp[- g()) ] = _α(Y=1 |)

where

    g()   = log_γ(Y=1)/_γ(Y=0) + ∑_(n,c) ∈𝒲_α  f_α(n,,c) logθ^α_(n,c)/θ^β_(n,c)
       =θ^α_𝑟𝑜𝑜𝑡 + ∑_(n,c) ∈𝒲_αf_α(n,,c) ·θ_(n,c)^α.

The transformation from Equation <ref> to <ref> expresses the logistic circuit parameters as the  log-ratios of probabilistic circuit probabilities. 
For example, the class priors captured in the output wires of α and β are now combined as a log-ratio to form the bias term for α, expressed by the root parameter.

This proof also provides us with a new perspective to understand the semantics of the learned parameters.  
The parameters represent the log-odds ratio of the features given different classes. Note that by Bayes' theorem, a naive Bayes model would derive its induced distribution in a sequence of steps similar to the ones above, resulting in Equation <ref>. Given this correspondence, one can also view our proposed structure learning method as a way to construct meaningful features for a naive Bayes classifier. We know that after training, naive Bayes classifiers are equivalent to logistic regression classifiers (as in Equation <ref>). 
 
 
 
 

§ RELATED WORK

<cit.> proposed the first parameter learning algorithm for discriminative SPNs, using MPE inference as a sub-routine. Without the support of the determinism property, parameter learning of general SPNs is a relatively harder question than its logistic circuit counterpart, since it is non-convex. <cit.> boost the accuracy of SPNs on MNIST to  97.6% by extracting more representative features from raw inputs based on the Hilbert-Schmidt independence measure. 
<cit.> further improved the  classification ability of SPNs by drastically simplifying SPN structure requirements and utilizing a loss objective that hybrids cross-entropy (discriminative learning) with log-likelihood (generative learning).

<cit.> developed a discriminative structure learning algorithm for arithmetic circuits. The method updates the circuit that represents a corresponding conditional random field (CRF) model by adding features conditioned on arbitrary evidence to the model. This work further relaxes decomposability and smoothness properties of ACs for a more compact representation. However, it targets the setting where there are a large number of output variables, not single-variable classification.

All the aforementioned literature conforms to a common trend of abandoning properties of the chosen circuit representations for easier structure learning and better prediction accuracy. They argue that those special syntactic restrictions complicate the learning process. On the contrary, this paper chooses perhaps the most structure-restrictive circuit as the target representation. Instead of relaxing the target representation's syntactical requirements, our proposed method fully leverages the valuable properties that stem from these restrictions, and in particular convexity. 



§ CONCLUSIONS


We have presented logistic circuits, a novel circuit-based classification model with convex parameter learning and a simple structure learning procedure based on local search. Logistic circuits outperform much larger classifiers and perform well in a limited data regime. Compared to other symbolic, circuit-based approaches, logistic circuits present a leap in performance on image classification benchmarks.
Future work includes support for convolution, parameter tying, and structure sharing in the logistic circuits framework.


 
  
           
 
 

§ PROOF OF PROPOSITION <REF>


 Before presenting the proof, we restate the proposition.
 
The features x constructed in the proof of Proposition <ref> are equivalent to global flows f_r(n,,c).
 
In the following, we prove this proposition by induction.
 

  – Base case: the inputs of the root r are either leaf nodes or AND gates whose inputs are leaf nodes. By definition, for the root's input wires, their local circuit flow equals their global circuit flow. According to the decomposition matrix of g_n in the proof of Proposition <ref>, the features associated with the root's input wires are equivalent to their local circuit flow. By transitivity, we prove logistic circuits' features are equivalent to its global circuit flow vector in the base case.

  – Induction step: assume the proposition holds for all OR gates in a given logistic circuit except the root r. Again, the root's inputs can be either leaf nodes or AND gates. It is obvious that for the root's input wires, their associated features are equivalent to their global circuit flow, as this has been proven in the base case.
So we only need to focus on the wires of the sub logistic circuits rooted on those AND gates. The inputs to those AND gates can either be leaf nodes or OR gates. As the wires between AND gates and their leaf children do not have parameters, the correctness of the proposition does not get affected by them. We can narrow our focus again. Now let us consider an OR gate n, which is an input to some of those aforementioned AND gates {e_1,…, e_m}. By our induction assumption, its features are equivalent to the global circuit flows defined with respect to n; in other words, x_n = f_n. After propagating x_n upwards to the root, we get ∑_i=1^m f(r,  x, e_1)·x_n. The sum of the global flow on all output wires of n is F_r(n) = ∑_i=1^m f(r,  x, e_1). Since F_r(n) is propagated throughout the whole sub logistic circuit rooted at n, the global circuit flow in this sub logistic circuit with respect to the root r is F_r(n)· f_n =  ∑_i=1^m f(r,  x, e_1) · f_n. Therefore, the constructed features are equivalent to the global circuit flows.


 

§ CALCULATION OF NODE PROBABILITIES

 
We calculate node probabilities in a bottom-up induction on the structure of the sentence.



  – Base case: n is a leaf (input) node. The node probability is directly defined in : _(n) = (X) if n is X; _(n) = 1 - (X) if n is X (lines 2-6 in Algorithm <ref>).

  – Induction step: given that the node probabilities for all the leaves have been calculated, we move upward to intermediate nodes and the root, where there are two cases.

 
  * n is an AND gate with inputs {c_1,…,c_m }. Since in a logistic circuit every AND gate is decomposable, by independence of the conjuncts, _(n) = ∏_i=1^m _(c_i) (lines 7-10 in Algorithm <ref>).
 
  * n is an OR gate with input nodes {c_1,…,c_m}. Since every OR gate is deterministic, the probabilistic events defined at each child within the same OR parent do not intersect with each other. By mutual exclusivity, _(n) = ∑ _i _(c_i) (lines 11-14 in Algorithm <ref>).
 

        
 

§ CALCULATION OF GLOBAL FLOWS (FEATURES)

 
 Node probabilities _(·) are used in Algorithm <ref> to obtain the final feature vector. 

 We perform a top-down pass starting from the root OR gate. After visiting an OR gate,  the method first calculates its associated global circuit flows from its inputs; see Line 7 in Algorithm <ref>. These newly calculated global flows then get passed down and are accumulated on those child gates for later use on the descendent gates (Line 8). After visiting an AND gate, there is no new global circuit flow to be calculated. Hence, the algorithm directly accumulates the flows passed to those AND gates to their children (Line 10-11).
 
 

Note that instead of inputing one single sample at a time, one can directly supply Algorithm <ref> and <ref> with a vector of samples. Our proposed calculation method is completely compatible with matrix operations, and by doing so, one can expect a large speedup.
	
  

§ INITIAL STRUCTURE

  
  
  All experiments in this paper start with an initial structure where every pixel has two corresponding leaf nodes, one for the pixel being true and the other false. 
  Pixels are paired up by AND gates; an AND gate is created for every joint assignment to the pair.
   AND gates for the same pair share one OR gate parent. After this, OR gates are paired with AND gates and every AND gate is connected to its own OR gate parent until we reach the root. Figure <ref> is an example of the initial structure with 4 pixels. Note that our structure learning algorithm is compatible with other initial structures and one can create ad-hoc ones tailored to different applications.
  


§ DETAILS OF EXISTING CLASSIFICATION MODELS


   The reported kernel logistic regression is based on the pixel n-grams implemented in Vowpal Wabbit <cit.>. The reported random forest has 500 decision trees. The reported SVM with RBF Kernel uses hyper-parameters C=8, γ=0.05 on MNIST and C=4,γ=25 on Fashion. The reported 3-layer MLP has layers of size 784-1000-500-250-10 respectively. The reported 5-layer MLP has layers of size 784-1000-500-250-2000-250-10 respectively. The reported CNN with 3 convolutional layers uses 3-by-3 padded filters in the convolutional layers.
   



§ ACKNOWLEDGEMENTS

This work is partially
supported by
a gift from Intel,
NSF grants #IIS-1657613, #IIS-1633857, #CCF-1837129,
and DARPA XAI grant #N66001-17-2-4032.
aaai

