For a given real vector and a threshold , the threshold element is a function f: Z_2^n -> Z_2 defined by the following relations:
f(x_1,\dots,x_n) = 1, \quad \textrm{if} \quad \sum_{i = 1}^{n} w_i x_i \geq T, \quad \textrm{and} \quad f(x_1,\dots,x_n) = 0 \quad \textrm{otherwise},
in which f(x_1,dots,x_n) is the binary output (valued 0 or 1), each variable x_i is the i-th input (valued 0 or 1), and n is the number of inputs.
The vector w is the weight vector, and the x=(x_1, ..., x_n) is the input vector. The vector (w_1, ..., w_n;T) is called the structure vector (or simply the structure) of the threshold element.
‣ ThresholdElement( Weights, Threshold ) | ( function ) |
For the list of rational numbers Weights and the rational Threshold the function ThresholdElement returns a threshold element with the number of inputs equal to the length of the Weights list.
gap> te:=ThresholdElement([1,2],3); < threshold element with weight vector [ 1, 2 ] and threshold 3 > gap> Display(te); Weight vector = [ 1, 2 ], Threshold = 3. Threshold Element realizes the function f : Boolean function of 2 variables. [ 0, 0 ] || 0 [ 0, 1 ] || 0 [ 1, 0 ] || 0 [ 1, 1 ] || 1 Sum of Products:[ 3 ]
The function Display outputs the stucture of the given threshold element ThrEl and the Sum of Products or Product of Sums representation of the function realized by ThrEl. For threshold elements of n ≤ 4 variables it also prints the truth table of the realized Boolean function.
gap> w:=[1,2,4,-4,6,8,10,-25,6,32];; gap> T:=60;; gap> te:=ThresholdElement(w,T); < threshold element with weight vector [ 1, 2, 4, -4, 6, 8, 10, -25, 6, 32 ] and threshold 60 > gap> Display(te); Weight vector = [ 1, 2, 4, -4, 6, 8, 10, -25, 6, 32 ], Threshold = 60. Threshold Element realizes the function f : Sum of Products:[ 59, 155, 185, 187, 251, 315, 379, 411, 427, 441, 443, 507, 5\ 71, 667, 697, 699, 763, 827, 891, 923, 939, 953, 955, 1019 ]
‣ IsThresholdElement( Obj ) | ( function ) |
For the object Obj the function IsThresholdElement returns true if Obj is a threshold element (see ThresholdElement (3.1-1)), and false otherwise.
gap> te:=ThresholdElement([1,2],3); < threshold element with weight vector [ 1, 2 ] and threshold 3 > gap> IsThresholdElement(te); true gap> IsThresholdElement([[1,2],3]); false
‣ OutputOfThresholdElement( ThrEl ) | ( function ) |
For the threshold element ThrEl the function OutputOfThresholdElement returns the Boolean function, realized by ThrEl.
gap> te:=ThresholdElement([1,2],3); < threshold element with weight vector [ 1, 2 ] and threshold 3 > gap> f:=OutputOfThresholdElement(te); < Boolean function of 2 variables > gap> Display(f); Boolean function of 2 variables. [ 0, 0 ] || 0 [ 0, 1 ] || 0 [ 1, 0 ] || 0 [ 1, 1 ] || 1
‣ StructureOfThresholdElement( ThrEl ) | ( function ) |
For the threshold element ThrEl the function StructureOfThresholdElement returns the structure vector [Weights,Threshold] (see ThresholdElement (3.1-1)).
gap> te:=ThresholdElement([1,2],3); < threshold element with weight vector [ 1, 2 ] and threshold 3 > gap> sv:=StructureOfThresholdElement(te); [ [ 1, 2 ], 3 ]
‣ RandomThresholdElement( NumVar, Lo, Hi ) | ( function ) |
For the integers NumVar, Lo, and Hi, the function RandomThresholdElement returns a threshold element of NumVar variables with a pseudo random integer weight vector and an integer threshold, where both the weights and the threshold are chosen from the interval [Lo, Hi].
gap> te:=RandomThresholdElement(4,-10,10); < threshold element with weight vector [ 7, -8, -6, 10 ] and threshold 2 >
‣ Comparison of Threshold Elements( ThrEl1, ThrEl2 ) | ( function ) |
Let ThrEl1 and ThrEl2 be two threshold elements of the same number of variables, which realize the following Boolean functions (see ThresholdElement (3.1-1)) f_1 and f_2, resprectively. By comparison of two threshold elements we mean the comparison of the truth vectors of f_1 and f_2 (see OutputOfThresholdElement (3.1-3)).
gap> te1:=ThresholdElement([1,2],3);; gap> Print(OutputOfThresholdElement(te1),"\n"); [2, 2,[ 0, 0, 0, 1 ]] gap> te2:=ThresholdElement([1,2],0);; gap> Print(OutputOfThresholdElement(te2),"\n"); [2, 2,[ 1, 1, 1, 1 ]] gap> te3:=ThresholdElement([1,1],2);; gap> Print(OutputOfThresholdElement(te3),"\n"); [2, 2,[ 0, 0, 0, 1 ]] gap> te1<te2; true gap> te1>te2; false gap> te1=te3; true
One of the most important questions is whether a Boolean function can be realized by a single threshold element (STE). A Boolean function which is realizable by a STE is called a Threshold Function. This section is dedicated to verification of STE-realizability.
‣ CharacteristicVectorOfFunction( Func ) | ( function ) |
Let f(x_1,...,x_n) be a Boolean function. We can switch from the {0,1}-base to {-1,1}-base using the following transformation:
y_i = 2x_i-1, \quad (i = 1,2,\ldots,n)
g(y_1,\ldots,y_n) = 2f(x_1,\ldots,x_n)-1.
For each i ∈ {1,2,...,n} the i-th column of the truth table of the function g(y_1,...,y_n) (in {-1,1}-base) we denote by Y_i, and the truth vector of g we denote by G.
Define the following vector:
b = \big(\;Y_1 \cdot G,\; \ldots, \; Y_n \cdot G, \; \textstyle \sum_{i=0}^{2^n-1} g(i) \; \big) \in \mathbb{R}^{n+1},
where Y_k ⋅ G is the classical inner (scalar) product for each k ∈ {1,...,n}.
Vector b is called the characteristic vector of the Boolean function f [Der65]. Comparing the characteristic vector of the function f with the lists of characteristic vectors of all STE-realizable functions we obtain the answer wheter f is realizable by STE or not. In Thelma package we have a database of all such vectors for STE-realizable functions of n ≤ 6 variables obtained from [Der65]. For the Boolean function Func the function CharacteristicVectorOfFunction returns a characteristic vector. There are no limitations on the cardinality of Func, but the database of STE-realizable functions is given only for n ≤ 6 variables.
gap> f:=LogicFunction(2,2,[0,0,0,1]); < Boolean function of 2 variables > gap> CharacteristicVectorOfFunction(f); [ 2, 2, 2 ]
‣ IsCharacteristicVectorOfSTE( ChVect ) | ( function ) |
For the characteristic vector ChVect (see CharacteristicVectorOfFunction (3.2-1)) the function IsCharacteristicVectorOfSTE returns true if ChVect is a characteristic vector of some STE-realizable Boolean function, and false otherwise. Note, that this function is implemented only for characteristic vectors of length not bigger than 7.
gap> f:=LogicFunction(2,2,[0,0,0,1]); < Boolean function of 2 variables > gap> c:=CharacteristicVectorOfFunction(f); [ 2, 2, 2 ] gap> IsCharacteristicVectorOfSTE(c); true
‣ IsInverseInKernel( Func ) | ( function ) |
Let f(x_1,...,x_n) be a Boolean function with the kernel K(f). The function IsInverseInKernel returns true if there is a pair of additive inverse vectors in K(f) (this means that f is not STE-realizable, see [GPR83]) or false otherwise. Note that this function also accepts the kernel of the Boolean function Func as an input. A vector b ∈ Z_2^n is called an additive inverse to a ∈ Z_2^n if a ⊕ b = 0.
gap> f:=LogicFunction(3,2,[0,1,0,1,0,1,1,0]);; gap> k:=KernelOfBooleanFunction(f);; gap> Display(k[1]); . . 1 . 1 1 1 . 1 1 1 . gap> IsInverseInKernel(f); true
‣ IsKernelContainingPrecedingVectors( Func ) | ( function ) |
A vector a=(α_1,...,α_n) ∈ Z_2^n precedes a vector b=(β_1,...,β_n) ∈ Z_2^n (we denote it as a ≺ b) if α_i ≤ β_i for each i=1,..., n.
For a given vector c ∈ Z_2^n denote M_c={ a∈ Z_2^n ∣ a ≺ c }.
Let f(x_1,...,x_n) be a Boolean function with reduced kernel T(f)={K(f)_j ∣ j=1,2,..., m }. If f is implemented by a single threshold element (STE), then there exists j ∈ {1,..., m } such that
\forall a \in K(f)_j \qquad \textrm{holds} \qquad M_a \subseteq K(f)_j.
The function IsKernelContainingPrecedingVectors returns false for a given function Func if Func is not realizable by a single threshold element (see [GMB17]). Note that this function also accepts the kernel of the Boolean function Func as an input.
gap> ##Continuation of the previous example gap> IsKernelContainingPrecedingVectors(f); false
‣ IsRKernelBiggerOfCombSum( Func ) | ( function ) |
Let f(x_1,...,x_n) be a Boolean function with reduced kernel T(f). Denote
k_i^* = \max\big\{ \; \|a\| = \textstyle \sum_{j=1}^m a_j \; \mid \; a = (a_1, \ldots, a_m) \in T(f) \; \big\}, \quad (i=1,\ldots,n)
and
k_A^*=\min\big\{\;k_i^* \; \mid \; i=1, 2, \ldots,n \; \big\}.
If f is implemented by a single threshold element (STE), then the following condition holds:
|A| \geq \sum_{i=0}^{k_A^*} {{k_A^*}\choose{i}},
where {k_A^*choosei} is the classical binomial coefficient and |A| is the cardinality of A.
For a given Boolean function Func the function IsRKernelBiggerOfCombSum returns false if this function is not STE-realizable (see [GMB17]). Note that this function also accepts the reduced kernel of the Boolean function Func as an input.
gap> f:=LogicFunction(2,2,[0,1,1,0]); < Boolean function of 2 variables > gap> IsRKernelBiggerOfCombSum(f); false
‣ BooleanFunctionBySTE( Func ) | ( function ) |
For a given Boolean function Func the function BooleanFunctionBySTE determines whether Func is realizable by a single threshold element (STE). The function returns a threshold element with integer weights and integer threshold. If Func is not realizable by STE, it returns an empty list []. The realization of the function BooleanFunctionBySTE is based on algorithms, proposed in [Gec10].
gap> f:=LogicFunction(3,2,[1,1,0,0,1,0,0,0]); < Boolean function of 3 variables > gap> te:=BooleanFunctionBySTE(f); < threshold element with weight vector [ -1, -4, -2 ] and threshold -2 > gap> Display(te); Weight vector = [ -1, -4, -2 ], Threshold = -2. Threshold Element realizes the function f : Boolean function of 3 variables. [ 0, 0, 0 ] || 1 [ 0, 0, 1 ] || 1 [ 0, 1, 0 ] || 0 [ 0, 1, 1 ] || 0 [ 1, 0, 0 ] || 1 [ 1, 0, 1 ] || 0 [ 1, 1, 0 ] || 0 [ 1, 1, 1 ] || 0 Sum of Products:[ 0, 1, 4 ] gap> f:=LogicFunction(2,2,[0,1,1,0]); < Boolean function of 2 variables > gap> te:=BooleanFunctionBySTE(f); [ ]
‣ PDBooleanFunctionBySTE( Func ) | ( function ) |
Let f(x_1,...,x_n) be a partially defined Boolean function. We denote by x the positions in truth vector, where f is undefined. Then f^-1(x) is the set of Boolean vectors of n variables on which the function is undefined. The sets f^-1(0) and f^-1(1) are defined in KernelOfBooleanFunction (2.1-9). The function f is called a threshold function if there is an n-dimensional real vector w=(w_1,...,w_n) and a real threshold T such that
a \in f^{-1}(1) \quad \Longrightarrow \quad a\cdot w^T \geq T,
a \in f^{-1}(0)\quad \Longrightarrow \quad a\cdot w^T < T,
where a⋅ w^T is the classical inner (scalar) product.
For the partially defined Boolean function Func (presented as a string, where x presents the undefined values) the function PDBooleanFunctionBySTE returns a threshold element if Func can be realized by STE and empty list otherwise. The realization of the function PDBooleanFunctionBySTE is based on the algorithm, proposed in [GPR83].
gap> f:="1x001x0x"; "1x001x0x" gap> te:=PDBooleanFunctionBySTE(f); < threshold element with weight vector [ -1, -2, -3 ] and threshold -1 > gap> Display(te); Weight vector = [ -1, -2, -3 ], Threshold = -1. Threshold Element realizes the function f : Boolean function of 3 variables. [ 0, 0, 0 ] || 1 [ 0, 0, 1 ] || 0 [ 0, 1, 0 ] || 0 [ 0, 1, 1 ] || 0 [ 1, 0, 0 ] || 1 [ 1, 0, 1 ] || 0 [ 1, 1, 0 ] || 0 [ 1, 1, 1 ] || 0 Sum of Products:[ 0, 4 ]
Thelma also provides a few iterative methods for threshold element training.
‣ ThresholdElementTraining( ThrEl, Step, Func, Max_Iter ) | ( function ) |
This is a basic iterative method for the perceptron training [Ros58]. For the threshold element ThrEl (which is an arbitrary threshold element for the first iteration), the positive integer Step (the value on which we change parameters while training the threshold element), the Boolean function Func and the positive integer Max_Iter - the maximal number of iterations, the function ThresholdElementTraining returns a threshold element, realizing Func (if such threshold element exists).
gap> f:=LogicFunction(2,2,[0,0,0,1]); < Boolean function of 2 variables > gap> te1:=RandomThresholdElement(2,-2,2); < threshold element with weight vector [ 0, -1 ] and threshold 0 > gap> Display(OutputOfThresholdElement(te1)); Boolean function of 2 variables. [ 0, 0 ] || 1 [ 0, 1 ] || 0 [ 1, 0 ] || 1 [ 1, 1 ] || 0 gap> te2:=ThresholdElementTraining(te1,1,f,100); < threshold element with weight vector [ 2, 1 ] and threshold 3 > gap> Display(OutputOfThresholdElement(te2)); Boolean function of 2 variables. [ 0, 0 ] || 0 [ 0, 1 ] || 0 [ 1, 0 ] || 0 [ 1, 1 ] || 1
‣ ThresholdElementBatchTraining( ThrEl, Step, Func, Max_Iter ) | ( function ) |
For the threshold element ThrEl (which is an arbitrary threshold element for the first iteration), the positive integer Step (the value on which we change parameters while training the threshold element), the Boolean function Func, and the positive integer Max_Iter - the maximal number of iterations, the function ThresholdElementTraining returns a threshold element, realizing Func (if such threshold element exists) via batch training.
gap> f:=LogicFunction(2,2,[0,0,0,1]); < Boolean function of 2 variables > gap> te1:=RandomThresholdElement(2,-2,2); < threshold element with weight vector [ 0, 2 ] and threshold 2 > gap> Display(OutputOfThresholdElement(te1)); Boolean function of 2 variables. [ 0, 0 ] || 0 [ 0, 1 ] || 1 [ 1, 0 ] || 0 [ 1, 1 ] || 1 gap> te2:=ThresholdElementBatchTraining(te1,1,f,100); < threshold element with weight vector [ 2, 2 ] and threshold 3 > gap> Display(OutputOfThresholdElement(te2)); Boolean function of 2 variables. [ 0, 0 ] || 0 [ 0, 1 ] || 0 [ 1, 0 ] || 0 [ 1, 1 ] || 1
‣ WinnowAlgorithm( Func, Step, Max_Iter ) | ( function ) |
A Boolean function f:Z_2^n -> Z_2 which can be presented in the following form:
f(x_1,\ldots,x_n)=x_{i_1} \vee \cdots \vee x_{i_k}, \qquad (k \leq n)
is called a monotone disjunction, i.e. it is a disjunction in which no variable appears negated.
If the given Boolean function f is a monotone disjunction, the Winnow algorithm is more efficient than the classical Perceptron training algorithm [Lit88].
For the Boolean function Func, which is a monotone disjunction, WinnowAlgorithm returns either a threshold element realizing Func or [] if Func is not trainable by WinnowAlgorithm. The positive ingetger Step which is not equal to 1 defines the value on which we change parameters while running the algorithm and the positive integer Max_Iter defines the maximal number of iterations.
gap> x:=Indeterminate(GF(2),"x");; gap> y:=Indeterminate(GF(2),"y");; gap> pol:=x*y+x+y;; gap> f:=PolynomialToBooleanFunction(pol,2); < Boolean function of 2 variables > gap> Display(f); Boolean function of 2 variables. [ 0, 0 ] || 0 [ 0, 1 ] || 1 [ 1, 0 ] || 1 [ 1, 1 ] || 1 gap> te:=WinnowAlgorithm(f,2,100); < threshold element with weight vector [ 1, 1 ] and threshold 1 > gap> Display(OutputOfThresholdElement(te)); Boolean function of 2 variables. [ 0, 0 ] || 0 [ 0, 1 ] || 1 [ 1, 0 ] || 1 [ 1, 1 ] || 1
‣ Winnow2Algorithm( Func, Step, Max_Iter ) | ( function ) |
For any X ⊆ Z_2^n and for any δ satisfying 0 < δ ≤ 1 let F(X,δ) be the class of functions from X to Z_2^n. Assume that F(X,δ) satisfies the following condition:
for each f ∈ F(X,δ) there exist μ_1,...,μ_n ≥ 0 such that for all (x_1,...,x_n) ∈ X
\textstyle \sum_{i=1}^n \mu_i x_i \geq 1, \quad \textrm{if} \quad f(x_1,\ldots,x_n)=1
and
\textstyle \sum_{i=1}^n \mu_i x_i \leq 1, \quad \textrm{if} \quad f(x_1,\ldots,x_n)=0.
In other words, the inverse images of 0 and 1 are linearly separable with a minimum separation that depends on δ. Winnow2 algorithm is designed for training this class of the Boolean functions [Lit88].
For the Boolean function Func from the class of Boolean functions which is described above, the function Winnow2Algorithm returns either a threshold element which realizes Func or [] if Func is not trainable by Winnow2Algorithm. The positive integer Step which is not equal to 1 defines the value on which we change parameters while running the algorithm.
gap> ##Conjunction can not be trained by Winnow algorithm. gap> x:=Indeterminate(GF(2),"x");; gap> y:=Indeterminate(GF(2),"y");; gap> pol:=x*y;; gap> f:=PolynomialToBooleanFunction(pol,2); < Boolean function of 2 variables > gap> te:=WinnowAlgorithm(f,2,100); [ ] gap> ## But in the case of Winnow2 we can obtain the desirable result. gap> te:=Winnow2Algorithm(f,2,100); < threshold element with weight vector [ 1/2, 1/2 ] and threshold 1 > gap> Display(te); Weight vector = [ 1/2, 1/2 ], Threshold = 1. Threshold Element realizes the function f : Boolean function of 2 variables. [ 0, 0 ] || 0 [ 0, 1 ] || 0 [ 1, 0 ] || 0 [ 1, 1 ] || 1 Sum of Products:[ 3 ]
‣ STESynthesis( Func ) | ( function ) |
The function STESynthesis is based on the algorithm proposed in [Der65]. In each iteration we perturb an n+1-dimensional weight-threshold vector in such manner that the distance between the given vector and a desired weight-threshold vector, if such vector exists, is reduced. So if the Boolean function Func is STE-realizable, then this procedure will eventually yield an acceptable weight-threshold vector. Otherwise iteration process will eventually enter a limit cycle and the execution of STE_Synthesis will be stopped.
For the Boolean function Func the function STESynthesis returns a threshold element if Func is STE-realizable or an empty list otherwise.
gap> f:=x*y+x+y;; gap> x:=Indeterminate(GF(2),"x");; gap> y:=Indeterminate(GF(2),"y");; gap> pol:=x*y+x+y;; gap> f:=PolynomialToBooleanFunction(pol,2);; gap> te:=STESynthesis(f); < threshold element with weight vector [ 2, 2 ] and threshold 1 > gap> Display(te); Weight vector = [ 2, 2 ], Threshold = 1. Threshold Element realizes the function f : Boolean function of 2 variables. [ 0, 0 ] || 0 [ 0, 1 ] || 1 [ 1, 0 ] || 1 [ 1, 1 ] || 1 Product of Sums:[ 0 ]
generated by GAPDoc2HTML