Representation of CNF and DNF by a neural netConsider neural nets with thresholds (and not sigmoids) at each node. These can easily com-pute CNF and DNF Boolean functions. A Boolean function of n Boolean variables is a functionf(x1, . . . xn) that produces as output either 0 or 1. Special cases are CNF and DNF.A DNF is a Boolean function of the form:f = t1∨ t2∨ . . . ∨ tmEach tjis of the form q1∧ q2∧ . . . ∧ qnj, and each qiis either a variable or a negation of a variable.For example, the following is a DNF:(x1∧ x2∧ x3) ∨ (x1∧ x2∧ x3) ∨ (x1∧ x2)A CNF is a Boolean function of the form:f = c1∧ c2∧ . . . ∧ cmEach cjis of the form q1∨ q2∨ . . . ∨ qnj, and each qiis either a variable or a negation of a variable.For example, the following is a DNF:(x1∨ x2∨ x3) ∧ (x1∨ x2∨ x3) ∧ (x1∨ x2)It is known (and very easy to show) that any Boolean function can be expressed as CNF and asDNF. In the worst case a Boolean function may require 2nDNF terms, or 2nCNF clauses.PerceptronsTheorem 1: A perceptron with inputs x1, . . . , xnand bias can compute any 1-term of a DNF.Constructive procedure: Let t = q1∧. . .∧qrbe a DNF term. The following algorithm convertsit into a single linear inequality that can be implemented by a single threshold unit.Step 1. Write the the inequalityX1+ . . . + Xr≥ r − 0.5, Xi=(xiif qi= xi1 − xiif qi= xiStep 2. Simplify the above inequality to the form:w0+ w1x1+ . . . + wrxr≥ 0Example: x1∧ x2∧ x3x1+ x2+ (1 − x3) ≥ 3 − 0.5−1.5 + x1+ x2− x3≥ 0Theorem 2: A perceptron with inputs x1, . . . , xnand bias cannot compute all 2-DNF.Proof: Observe that the xor function can be written as a 2-DNF: (x1∧ x2) ∨ (x1∧ x2).Theorem 3: A perceptron with inputs x1, . . . , xnand bias can compute any 1-clause of a CNF.1Constructive procedure: Let c = q1∨ . . . ∨ qrbe a CNF clause. The following algorithmconverts it into a single linear inequality that can be implemented by a single threshold unit.Step 1. Write the the inequalityX1+ . . . + Xr≥ 0.5, Xi=(xiif qi= xi1 − xiif qi= xiStep 2. Simplify the above inequality to the form:w0+ w1x1+ . . . + wrxr≥ 0Example: x1∨ x2∨ x3x1+ x2+ (1 − x3) ≥ 0.50.5 + x1+ x2− x3≥ 0Theorem 4: A perceptron with inputs x1, . . . , xnand bias cannot compute all 2-CNF.Proof: Observe that the xor function can be written as a 2-CNF: (x1∨ x2) ∧ (x1∨ x2)Neural Nets (multi layer perceptrons)Theorem 5: A neural-net with one hidden layer, given inputs x1, . . . , xnand bias can computeany DNF. An r-term DNF requires no more than r nodes in the hidden layer.Constructive pro cedure: Suppose f = t1∨ t2∨ . . . ∨ tm. The neural net has the hidden layernodes V1, . . . , Vm. The node Vjis connected to the inputs following the procedure in Theorem 1.The nodes V1, . . . , Vmare connected to the output node using the procedure of Theorem 3.Theorem 6: A neural-net with one hidden layer, given inputs x1, . . . , xnand bias can computeany CNF. An r-clause CNF requires no more than r nodes in the hidden layer.Constructive procedure: Suppose f = c1∧ c2∧ . . . ∧ cm. The neural net has the hidden layernodes V1, . . . , Vm. The node Vjis connected to the inputs following the procedure in Theorem 3.The nodes V1, . . . , Vmare connected to the output node using the procedure of Theorem 1.What if network vaiables are −1/1?x1∨ x2∨ . . . ∨ xn⇔nXi=1xi> −n + 0.5x1∧ x2∧ . . . ∧ xn⇔nXi=1xi> n − 0.5¬x ⇔
View Full Document
Unlocking...