| products/Sources/formale Sprachen/GAP/pkg/thelma/doc/chap3.html |
 |
<?xml version= "1.0" encoding= "UTF-8"?>
<! DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Strict//EN"
"http://www.w3.org/TR/xhtml1/DTD/xhtml1-strict.dtd">
< html xmlns= "http://www.w3.org/1999/xhtml" xml:lang= "en">
< head>
< title>GAP (Thelma) - Chapter 3: Threshold Elements</ title>
< meta http-equiv= "content-type" content= "text/html; charset=UTF-8" />
< meta name= "generator" content= "GAPDoc2HTML" />
< link rel= "stylesheet" type= "text/css" href= "manual.css" />
< script src= "manual.js" type= "text/javascript"></ script>
< script type= "text/javascript">overwriteStyle();</ script>
</ head>
< body class= "chap3" onload= "jscontent()">
< div class= "chlinktop">< span class= "chlink1">Goto Chapter: </ span>< a href= "chap0.html">Top</ a> < a href="chap1.html">1</a> <a href="chap2.html">2</a> <a href="chap3.html">3</a> <a href="chap4.html">4</a> <a href="chap5.html">5</a> <a href="chapBib.html">Bib</a> <a href="chapInd.html">Ind</a> </div>
<div class="chlinkprevnexttop"> <a href="chap0.html">[Top of Book]</a> <a href="chap0.html#contents">[Contents]</a> <a href="chap2.html">[Previous Chapter]</a> <a href="chap4.html">[Next Chapter]</a> </div>
<p id="mathjaxlink" class="pcenter"><a href="chap3_mj.html">[MathJax on]</a></p>
<p><a id="X83DFEF607CDA3594" name="X83DFEF607CDA3594"></a></p>
<div class="ChapSects"><a href="chap3.html#X83DFEF607CDA3594">3 <span class="Heading">Threshold Elements</span></a>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap3.html#X82EB5BE77F9F686A">3.1 <span class="Heading">Basic Operations</span></a>
</span>
<div class="ContSSBlock">
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap3.html#X853FF8AC85E5C4CE">3.1-1 ThresholdElement</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap3.html#X7E7F95D57EB87BB4">3.1-2 IsThresholdElement</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap3.html#X7F293D2D810ADBBB">3.1-3 OutputOfThresholdElement</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap3.html#X8116985278C60D33">3.1-4 StructureOfThresholdElement</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap3.html#X800C6898856CD0E9">3.1-5 RandomThresholdElement</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap3.html#X7C9E64E17B07DF58">3.1-6 Comparison of Threshold Elements</a></span>
</div></div>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap3.html#X7DB8E3E87D8AD820">3.2 <span class="Heading">Single Threshold Element Realizability</span></a>
</span>
<div class="ContSSBlock">
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap3.html#X8351E15B7CCDEB62">3.2-1 CharacteristicVectorOfFunction</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap3.html#X8502A0827ECF1FFE">3.2-2 IsCharacteristicVectorOfSTE</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap3.html#X7B0855E28717AF12">3.2-3 IsInverseInKernel</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap3.html#X83B234DB7F260879">3.2-4 IsKernelContainingPrecedingVectors</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap3.html#X7877118A7A9C51CB">3.2-5 IsRKernelBiggerOfCombSum</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap3.html#X83D3B18486C5D0B7">3.2-6 BooleanFunctionBySTE</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap3.html#X8451E4EA7F06222F">3.2-7 PDBooleanFunctionBySTE</a></span>
</div></div>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap3.html#X7D0584857E0D2265">3.3 <span class="Heading">Iterative Training Methods</span></a>
</span>
<div class="ContSSBlock">
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap3.html#X83567B7D79958EBF">3.3-1 ThresholdElementTraining</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap3.html#X83CD889E8125E949">3.3-2 ThresholdElementBatchTraining</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap3.html#X81FEA8AF80573A12">3.3-3 WinnowAlgorithm</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap3.html#X85162EF17EE09E50">3.3-4 Winnow2Algorithm</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap3.html#X7C4B705884A78907">3.3-5 STESynthesis</a></span>
</div></div>
</div>
<h3>3 <span class="Heading">Threshold Elements</span></h3>
<p><a id="X82EB5BE77F9F686A" name="X82EB5BE77F9F686A"></a></p>
<h4>3.1 <span class="Heading">Basic Operations</span></h4>
<p>For a given real vector and a threshold , the <var class="Arg">threshold element</var> is a function <span class="SimpleMath">f: Z_2^n -> Z_2</span> defined by the following relations:</p>
<p class="pcenter">
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},
</p>
<p>in which <span class="SimpleMath">f(x_1,dots,x_n)</span> is the binary output (valued 0 or 1), each variable <span class="SimpleMath">x_i</span> is the i-th input (valued 0 or 1), and <span class="SimpleMath">n</span> is the number of inputs.</p>
<p>The vector <span class="SimpleMath">w</span> is the <var class="Arg">weight</var> vector, and the <span class="SimpleMath">x=(x_1, ..., x_n)</span> is the <var class="Arg">input</var> vector. The vector <span class="SimpleMath">(w_1, ..., w_n;T)</span> is called the <var class="Arg">structure vector</var> (or simply the <var class="Arg">structure</var>) of the threshold element.</p>
<p><a id="X853FF8AC85E5C4CE" name="X853FF8AC85E5C4CE"></a></p>
<h5>3.1-1 ThresholdElement</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">an style='color: green'>8227; ThresholdElement</code>( <var class="Arg">Weights</var>, <var class="Arg">Threshold</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>For the list of rational numbers <code class="code">Weights</code> and the rational <code class="code">Threshold</code> the function <code class="code">ThresholdElement</code> returns a threshold element with the number of inputs equal to the length of the <code class="code">Weights</code> list.</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">te:=ThresholdElement([1,2],3);</span>
< threshold element with weight vector [ 1, 2 ] and threshold 3 >
<span class="GAPprompt">gap></span> <span class="GAPinput">Display(te);</span>
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 ]
</pre></div>
<p>The function <code class="code">Display</code> outputs the stucture of the given threshold element <code class="code">ThrEl</code> and the Sum of Products or Product of Sums representation of the function realized by <code class="code">ThrEl</code>. For threshold elements of <span class="SimpleMath">n ≤ 4</span> variables it also prints the truth table of the realized Boolean function.</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">w:=[1,2,4,-4,6,8,10,-25,6,32];;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">T:=60;;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">te:=ThresholdElement(w,T);</span>
< threshold element with weight vector [ 1, 2, 4, -4, 6, 8, 10, -25, 6, 32
] and threshold 60 >
<span class="GAPprompt">gap></span> <span class="GAPinput">Display(te);</span>
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 ]
</pre></div>
<p><a id="X7E7F95D57EB87BB4" name="X7E7F95D57EB87BB4"></a></p>
<h5>3.1-2 IsThresholdElement</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">an style='color: green'>8227; IsThresholdElement</code>( <var class="Arg">Obj</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>For the object <code class="code">Obj</code> the function <code class="code">IsThresholdElement</code> returns <code class="code">true</code> if <code class="code">Obj</code> is a threshold element (see <code class="func">ThresholdElement</code> (<a href="chap3.html#X853FF8AC85E5C4CE"><span class="RefLink">3.1-1</span></a>)), and <code class="code">false</code> otherwise.</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">te:=ThresholdElement([1,2],3);</span>
< threshold element with weight vector [ 1, 2 ] and threshold 3 >
<span class="GAPprompt">gap></span> <span class="GAPinput">IsThresholdElement(te);</span>
true
<span class="GAPprompt">gap></span> <span class="GAPinput">IsThresholdElement([[1,2],3]);</span>
false
</pre></div>
<p><a id="X7F293D2D810ADBBB" name="X7F293D2D810ADBBB"></a></p>
<h5>3.1-3 OutputOfThresholdElement</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">an style='color: green'>8227; OutputOfThresholdElement</code>( <var class="Arg">ThrEl</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>For the threshold element <code class="code">ThrEl</code> the function <code class="code">OutputOfThresholdElement</code> returns the Boolean function, realized by <code class="code">ThrEl</code>.</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">te:=ThresholdElement([1,2],3);</span>
< threshold element with weight vector [ 1, 2 ] and threshold 3 >
<span class="GAPprompt">gap></span> <span class="GAPinput">f:=OutputOfThresholdElement(te);</span>
< Boolean function of 2 variables >
<span class="GAPprompt">gap></span> <span class="GAPinput">Display(f);</span>
Boolean function of 2 variables.
[ 0, 0 ] || 0
[ 0, 1 ] || 0
[ 1, 0 ] || 0
[ 1, 1 ] || 1
</pre></div>
<p><a id="X8116985278C60D33" name="X8116985278C60D33"></a></p>
<h5>3.1-4 StructureOfThresholdElement</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">an style='color: green'>8227; StructureOfThresholdElement</code>( <var class="Arg">ThrEl</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>For the threshold element <code class="code">ThrEl</code> the function <code class="code">StructureOfThresholdElement</code> returns the structure vector [<code class="code">Weights</code>,<code class="code">Threshold</code>] (see <code class="func">ThresholdElement</code> (<a href="chap3.html#X853FF8AC85E5C4CE"><span class="RefLink">3.1-1</span></a>)).</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">te:=ThresholdElement([1,2],3);</span>
< threshold element with weight vector [ 1, 2 ] and threshold 3 >
<span class="GAPprompt">gap></span> <span class="GAPinput">sv:=StructureOfThresholdElement(te);</span>
[ [ 1, 2 ], 3 ]
</pre></div>
<p><a id="X800C6898856CD0E9" name="X800C6898856CD0E9"></a></p>
<h5>3.1-5 RandomThresholdElement</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">an style='color: green'>8227; RandomThresholdElement</code>( <var class="Arg">NumVar</var>, <var class="Arg">Lo</var>, <var class="Arg">Hi</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>For the integers <code class="code">NumVar</code>, <code class="code">Lo</code>, and <code class="code">Hi</code>, the function <code class="code">RandomThresholdElement</code> returns a threshold element of <code class="code">NumVar</code> variables with a pseudo random integer weight vector and an integer threshold, where both the weights and the threshold are chosen from the interval [<code class="code">Lo</code>, <code class="code">Hi</code>].</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">te:=RandomThresholdElement(4,-10,10);</span>
< threshold element with weight vector [ 7, -8, -6, 10 ] and threshold 2 >
</pre></div>
<p><a id="X7C9E64E17B07DF58" name="X7C9E64E17B07DF58"></a></p>
<h5>3.1-6 Comparison of Threshold Elements</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">an style='color: green'>8227; Comparison of Threshold Elements</code>( <var class="Arg">ThrEl1</var>, <var class="Arg">ThrEl2</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>Let <code class="code">ThrEl1</code> and <code class="code">ThrEl2</code> be two threshold elements of the same number of variables, which realize the following Boolean functions (see <code class="func">ThresholdElement</code> (<a href="chap3.html#X853FF8AC85E5C4CE"><span class="RefLink">3.1-1</span></a>)) <span class="SimpleMath">f_1</span> and <span class="SimpleMath">f_2</span>, resprectively. By comparison of two threshold elements we mean the comparison of the truth vectors of <span class="SimpleMath">f_1</span> and <span class="SimpleMath">f_2</span> (see <code class="func">OutputOfThresholdElement</code> (<a href="chap3.html#X7F293D2D810ADBBB"><span class="RefLink">3.1-3</span></a>)).</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">te1:=ThresholdElement([1,2],3);;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">Print(OutputOfThresholdElement(te1),"\n");</span>
[2, 2,[ 0, 0, 0, 1 ]]
<span class="GAPprompt">gap></span> <span class="GAPinput">te2:=ThresholdElement([1,2],0);;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">Print(OutputOfThresholdElement(te2),"\n");</span>
[2, 2,[ 1, 1, 1, 1 ]]
<span class="GAPprompt">gap></span> <span class="GAPinput">te3:=ThresholdElement([1,1],2);;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">Print(OutputOfThresholdElement(te3),"\n");</span>
[2, 2,[ 0, 0, 0, 1 ]]
<span class="GAPprompt">gap></span> <span class="GAPinput">te1<te2;</span>
true
<span class="GAPprompt">gap></span> <span class="GAPinput">te1>te2;</span>
false
<span class="GAPprompt">gap></span> <span class="GAPinput">te1=te3;</span>
true
</pre></div>
<p><a id="X7DB8E3E87D8AD820" name="X7DB8E3E87D8AD820"></a></p>
<h4>3.2 <span class="Heading">Single Threshold Element Realizability</span></h4>
<p>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 <code class="code">Threshold Function</code>. This section is dedicated to verification of STE-realizability.</p>
<p><a id="X8351E15B7CCDEB62" name="X8351E15B7CCDEB62"></a></p>
<h5>3.2-1 CharacteristicVectorOfFunction</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">an style='color: green'>8227; CharacteristicVectorOfFunction</code>( <var class="Arg">Func</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>Let <span class="SimpleMath">f(x_1,...,x_n)</span> be a Boolean function. We can switch from the {0,1}-base to {-1,1}-base using the following transformation:</p>
<p class="pcenter">
y_i = 2x_i-1, \quad (i = 1,2,\ldots,n)
</p>
<p class="pcenter">
g(y_1,\ldots,y_n) = 2f(x_1,\ldots,x_n)-1.
</p>
<p>For each <span class="SimpleMath">i ∈ {1,2,...,n}</span> the <span class="SimpleMath">i</span>-th column of the truth table of the function <span class="SimpleMath">g(y_1,...,y_n)</span> (in {-1,1}-base) we denote by <span class="SimpleMath">Y_i</span>, and the truth vector of <span class="SimpleMath">g</span> we denote by <span class="SimpleMath">G</span>.</p>
<p>Define the following vector:</p>
<p class="pcenter">
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},
</p>
<p>where <span class="SimpleMath">Y_k ⋅ G</span> is the classical inner (scalar) product for each <span class="SimpleMath">k ∈ {1,...,n}</span>.</p>
<p>Vector <span class="SimpleMath">b</span> is called the <var class="Arg">characteristic vector</var> of the Boolean function <span class="SimpleMath">f</span> <a href="chapBib.html#biBDertouzos65">[Der65]</a>. Comparing the characteristic vector of the function <span class="SimpleMath">f</span> with the lists of characteristic vectors of all STE-realizable functions we obtain the answer wheter <span class="SimpleMath">f</span> is realizable by STE or not. In <strong class="pkg">Thelma</strong> package we have a database of all such vectors for STE-realizable functions of <span class="SimpleMath">n ≤ 6</span> variables obtained from <a href="chapBib.html#biBDertouzos65">[Der65]</a>. For the Boolean function <code class="code">Func</code> the function <code class="code">CharacteristicVectorOfFunction</code> returns a characteristic vector. There are no limitations on the cardinality of <code class="code">Func</code>, but the database of STE-realizable functions is given only for <span class="SimpleMath">n ≤ 6</span> variables.</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">f:=LogicFunction(2,2,[0,0,0,1]);</span>
< Boolean function of 2 variables >
<span class="GAPprompt">gap></span> <span class="GAPinput">CharacteristicVectorOfFunction(f);</span>
[ 2, 2, 2 ]
</pre></div>
<p><a id="X8502A0827ECF1FFE" name="X8502A0827ECF1FFE"></a></p>
<h5>3.2-2 IsCharacteristicVectorOfSTE</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">an style='color: green'>8227; IsCharacteristicVectorOfSTE</code>( <var class="Arg">ChVect</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>For the characteristic vector <code class="code">ChVect</code> (see <code class="func">CharacteristicVectorOfFunction</code> (<a href="chap3.html#X8351E15B7CCDEB62"><span class="RefLink">3.2-1</span></a>)) the function <code class="code">IsCharacteristicVectorOfSTE</code> returns <code class="code">true</code> if <code class="code">ChVect</code> is a characteristic vector of some STE-realizable Boolean function, and <code class="code">false</code> otherwise. Note, that this function is implemented only for characteristic vectors of length not bigger than 7.</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">f:=LogicFunction(2,2,[0,0,0,1]);</span>
< Boolean function of 2 variables >
<span class="GAPprompt">gap></span> <span class="GAPinput">c:=CharacteristicVectorOfFunction(f);</span>
[ 2, 2, 2 ]
<span class="GAPprompt">gap></span> <span class="GAPinput">IsCharacteristicVectorOfSTE(c);</span>
true
</pre></div>
<p><a id="X7B0855E28717AF12" name="X7B0855E28717AF12"></a></p>
<h5>3.2-3 IsInverseInKernel</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">an style='color: green'>8227; IsInverseInKernel</code>( <var class="Arg">Func</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>Let <span class="SimpleMath">f(x_1,...,x_n)</span> be a Boolean function with the kernel <span class="SimpleMath">K(f)</span>. The function <code class="code">IsInverseInKernel</code> returns <code class="code">true</code> if there is a pair of additive inverse vectors in <span class="SimpleMath">K(f)</span> (this means that <span class="SimpleMath">f</span> is not STE-realizable, see <a href="chapBib.html#biBGecheRobotyshyn83">[GPR83]</a>) or <code class="code">false</code> otherwise. Note that this function also accepts the kernel of the Boolean function <code class="code">Func</code> as an input. A vector <span class="SimpleMath">b ∈ Z_2^n</span> is called an additive inverse to <span class="SimpleMath">a ∈ Z_2^n</span> if <span class="SimpleMath">a ⊕ b = 0</span>.</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">f:=LogicFunction(3,2,[0,1,0,1,0,1,1,0]);;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">k:=KernelOfBooleanFunction(f);;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">Display(k[1]);</span>
. . 1
. 1 1
1 . 1
1 1 .
<span class="GAPprompt">gap></span> <span class="GAPinput">IsInverseInKernel(f);</span>
true
</pre></div>
<p><a id="X83B234DB7F260879" name="X83B234DB7F260879"></a></p>
<h5>3.2-4 IsKernelContainingPrecedingVectors</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">an style='color: green'>8227; IsKernelContainingPrecedingVectors</code>( <var class="Arg">Func</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>A vector <span class="SimpleMath">a=(α_1,...,α_n) ∈ Z_2^n</span> precedes a vector <span class="SimpleMath">b=(β_1,...,β_n) ∈ Z_2^n</span> (we denote it as <span class="SimpleMath">a ≺ b</span>) if <span class="SimpleMath">α_i ≤ β_i for each i=1,..., n</span>.</p>
<p>For a given vector <span class="SimpleMath">c ∈ Z_2^n</span> denote <span class="SimpleMath">M_c={ a∈ Z_2^n ∣ a ≺ c }</span>.</p>
<p>Let <span class="SimpleMath">f(x_1,...,x_n)</span> be a Boolean function with reduced kernel <span class="SimpleMath">T(f)={K(f)_j ∣ j=1,2,..., m }</span>. If <span class="SimpleMath">f</span> is implemented by a single threshold element (STE), then there exists <span class="SimpleMath">j ∈ {1,..., m }</span> such that</p>
<p class="pcenter">
\forall a \in K(f)_j \qquad \textrm{holds} \qquad M_a \subseteq K(f)_j.
</p>
<p>The function <code class="code">IsKernelContainingPrecedingVectors</code> returns <code class="code">false</code> for a given function <code class="code">Func</code> if <span class="SimpleMath">Func</span> is not realizable by a single threshold element (see <a href="chapBib.html#biBGecheMulesa2017">[GMB17]</a>). Note that this function also accepts the kernel of the Boolean function <code class="code">Func</code> as an input.</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">##Continuation of the previous example</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">IsKernelContainingPrecedingVectors(f);</span>
false
</pre></div>
<p><a id="X7877118A7A9C51CB" name="X7877118A7A9C51CB"></a></p>
<h5>3.2-5 IsRKernelBiggerOfCombSum</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">an style='color: green'>8227; IsRKernelBiggerOfCombSum</code>( <var class="Arg">Func</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>Let <span class="SimpleMath">f(x_1,...,x_n)</span> be a Boolean function with reduced kernel <span class="SimpleMath">T(f)</span>. Denote</p>
<p class="pcenter">
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)
</p>
<p>and</p>
<p class="pcenter">
k_A^*=\min\big\{\;k_i^* \; \mid \; i=1, 2, \ldots,n \; \big\}.
</p>
<p>If <span class="SimpleMath">f</span> is implemented by a single threshold element (STE), then the following condition holds:</p>
<p class="pcenter">
|A| \geq \sum_{i=0}^{k_A^*} {{k_A^*}\choose{i}},
</p>
<p>where <span class="SimpleMath">{k_A^*choosei}</span> is the classical binomial coefficient and <span class="SimpleMath">|A|</span> is the cardinality of <span class="SimpleMath">A</span>.</p>
<p>For a given Boolean function <code class="code">Func</code> the function <code class="code">IsRKernelBiggerOfCombSum</code> returns <code class="code">false</code> if this function is not STE-realizable (see <a href="chapBib.html#biBGecheMulesa2017">[GMB17]</a>). Note that this function also accepts the reduced kernel of the Boolean function <code class="code">Func</code> as an input.</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">f:=LogicFunction(2,2,[0,1,1,0]);</span>
< Boolean function of 2 variables >
<span class="GAPprompt">gap></span> <span class="GAPinput">IsRKernelBiggerOfCombSum(f);</span>
false
</pre></div>
<p><a id="X83D3B18486C5D0B7" name="X83D3B18486C5D0B7"></a></p>
<h5>3.2-6 BooleanFunctionBySTE</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">an style='color: green'>8227; BooleanFunctionBySTE</code>( <var class="Arg">Func</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>For a given Boolean function <code class="code">Func</code> the function <code class="code">BooleanFunctionBySTE</code> determines whether <code class="code">Func</code> is realizable by a single threshold element (STE). The function returns a threshold element with integer weights and integer threshold. If <code class="code">Func</code> is not realizable by STE, it returns an empty list []. The realization of the function <code class="code">BooleanFunctionBySTE</code> is based on algorithms, proposed in <a href="chapBib.html#biBGeche2010">[Gec10]</a>.</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">f:=LogicFunction(3,2,[1,1,0,0,1,0,0,0]);</span>
< Boolean function of 3 variables >
<span class="GAPprompt">gap></span> <span class="GAPinput">te:=BooleanFunctionBySTE(f);</span>
< threshold element with weight vector [ -1, -4, -2 ] and threshold -2 >
<span class="GAPprompt">gap></span> <span class="GAPinput">Display(te);</span>
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 ]
<span class="GAPprompt">gap></span> <span class="GAPinput">f:=LogicFunction(2,2,[0,1,1,0]);</span>
< Boolean function of 2 variables >
<span class="GAPprompt">gap></span> <span class="GAPinput">te:=BooleanFunctionBySTE(f);</span>
[ ]
</pre></div>
<p><a id="X8451E4EA7F06222F" name="X8451E4EA7F06222F"></a></p>
<h5>3.2-7 PDBooleanFunctionBySTE</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">an style='color: green'>8227; PDBooleanFunctionBySTE</code>( <var class="Arg">Func</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>Let <span class="SimpleMath">f(x_1,...,x_n)</span> be a partially defined Boolean function. We denote by <code class="code">x</code> the positions in truth vector, where <span class="SimpleMath">f</span> is undefined. Then <span class="SimpleMath">f^-1</span><code class="code">(x)</code> is the set of Boolean vectors of <span class="SimpleMath">n</span> variables on which the function is undefined. The sets <span class="SimpleMath">f^-1(0)</span> and <span class="SimpleMath">f^-1(1)</span> are defined in <code class="func">KernelOfBooleanFunction</code> (<a href="chap2.html#X8108DE5280908841"><span class="RefLink">2.1-9</span></a>). The function <span class="SimpleMath">f</span> is called a <var class="Arg">threshold function</var> if there is an <span class="SimpleMath">n</span>-dimensional real vector <span class="SimpleMath">w=(w_1,...,w_n)</span> and a real threshold <span class="SimpleMath">T</span> such that</p>
<p class="pcenter">
a \in f^{-1}(1) \quad \Longrightarrow \quad a\cdot w^T \geq T,
</p>
<p class="pcenter">
a \in f^{-1}(0)\quad \Longrightarrow \quad a\cdot w^T < T,
</p>
<p>where <span class="SimpleMath">a⋅ w^T</span> is the classical inner (scalar) product.</p>
<p>For the partially defined Boolean function <code class="code">Func</code> (presented as a string, where <code class="code">x</code> presents the undefined values) the function <code class="code">PDBooleanFunctionBySTE</code> returns a threshold element if <code class="code">Func</code> can be realized by STE and empty list otherwise. The realization of the function <code class="code">PDBooleanFunctionBySTE</code> is based on the algorithm, proposed in <a href="chapBib.html#biBGecheRobotyshyn83">[GPR83]</a>.</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">f:="1x001x0x";</span>
"1x001x0x"
<span class="GAPprompt">gap></span> <span class="GAPinput">te:=PDBooleanFunctionBySTE(f);</span>
< threshold element with weight vector [ -1, -2, -3 ] and threshold -1 >
<span class="GAPprompt">gap></span> <span class="GAPinput">Display(te);</span>
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 ]
</pre></div>
<p><a id="X7D0584857E0D2265" name="X7D0584857E0D2265"></a></p>
<h4>3.3 <span class="Heading">Iterative Training Methods</span></h4>
<p><strong class="pkg">Thelma</strong> also provides a few iterative methods for threshold element training.</p>
<p><a id="X83567B7D79958EBF" name="X83567B7D79958EBF"></a></p>
<h5>3.3-1 ThresholdElementTraining</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">an style='color: green'>8227; ThresholdElementTraining</code>( <var class="Arg">ThrEl</var>, <var class="Arg">Step</var>, <var class="Arg">Func</var>, <var class="Arg">Max_Iter</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>This is a basic iterative method for the perceptron training <a href="chapBib.html#biBRosenblatt58">[Ros58]</a>. For the threshold element <code class="code">ThrEl</code> (which is an arbitrary threshold element for the first iteration), the positive integer <code class="code">Step</code> (the value on which we change parameters while training the threshold element), the Boolean function <code class="code">Func</code> and the positive integer <code class="code">Max_Iter</code> - the maximal number of iterations, the function <code class="code">ThresholdElementTraining</code> returns a threshold element, realizing <code class="code">Func</code> (if such threshold element exists).</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">f:=LogicFunction(2,2,[0,0,0,1]);</span>
< Boolean function of 2 variables >
<span class="GAPprompt">gap></span> <span class="GAPinput">te1:=RandomThresholdElement(2,-2,2);</span>
< threshold element with weight vector [ 0, -1 ] and threshold 0 >
<span class="GAPprompt">gap></span> <span class="GAPinput">Display(OutputOfThresholdElement(te1));</span>
Boolean function of 2 variables.
[ 0, 0 ] || 1
[ 0, 1 ] || 0
[ 1, 0 ] || 1
[ 1, 1 ] || 0
<span class="GAPprompt">gap></span> <span class="GAPinput">te2:=ThresholdElementTraining(te1,1,f,100);</span>
< threshold element with weight vector [ 2, 1 ] and threshold 3 >
<span class="GAPprompt">gap></span> <span class="GAPinput">Display(OutputOfThresholdElement(te2));</span>
Boolean function of 2 variables.
[ 0, 0 ] || 0
[ 0, 1 ] || 0
[ 1, 0 ] || 0
[ 1, 1 ] || 1
</pre></div>
<p><a id="X83CD889E8125E949" name="X83CD889E8125E949"></a></p>
<h5>3.3-2 ThresholdElementBatchTraining</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">an style='color: green'>8227; ThresholdElementBatchTraining</code>( <var class="Arg">ThrEl</var>, <var class="Arg">Step</var>, <var class="Arg">Func</var>, <var class="Arg">Max_Iter</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>For the threshold element <code class="code">ThrEl</code> (which is an arbitrary threshold element for the first iteration), the positive integer <code class="code">Step</code> (the value on which we change parameters while training the threshold element), the Boolean function <code class="code">Func</code>, and the positive integer <code class="code">Max_Iter</code> - the maximal number of iterations, the function <code class="code">ThresholdElementTraining</code> returns a threshold element, realizing <code class="code">Func</code> (if such threshold element exists) via batch training.</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">f:=LogicFunction(2,2,[0,0,0,1]);</span>
< Boolean function of 2 variables >
<span class="GAPprompt">gap></span> <span class="GAPinput">te1:=RandomThresholdElement(2,-2,2);</span>
< threshold element with weight vector [ 0, 2 ] and threshold 2 >
<span class="GAPprompt">gap></span> <span class="GAPinput">Display(OutputOfThresholdElement(te1));</span>
Boolean function of 2 variables.
[ 0, 0 ] || 0
[ 0, 1 ] || 1
[ 1, 0 ] || 0
[ 1, 1 ] || 1
<span class="GAPprompt">gap></span> <span class="GAPinput">te2:=ThresholdElementBatchTraining(te1,1,f,100);</span>
< threshold element with weight vector [ 2, 2 ] and threshold 3 >
<span class="GAPprompt">gap></span> <span class="GAPinput">Display(OutputOfThresholdElement(te2));</span>
Boolean function of 2 variables.
[ 0, 0 ] || 0
[ 0, 1 ] || 0
[ 1, 0 ] || 0
[ 1, 1 ] || 1
</pre></div>
<p><a id="X81FEA8AF80573A12" name="X81FEA8AF80573A12"></a></p>
<h5>3.3-3 WinnowAlgorithm</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">an style='color: green'>8227; WinnowAlgorithm</code>( <var class="Arg">Func</var>, <var class="Arg">Step</var>, <var class="Arg">Max_Iter</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>A Boolean function <span class="SimpleMath">f:Z_2^n -> Z_2</span> which can be presented in the following form:</p>
<p class="pcenter">
f(x_1,\ldots,x_n)=x_{i_1} \vee \cdots \vee x_{i_k}, \qquad (k \leq n)
</p>
<p>is called a <var class="Arg">monotone disjunction</var>, i.e. it is a disjunction in which no variable appears negated.</p>
<p>If the given Boolean function <span class="SimpleMath">f</span> is a monotone disjunction, the <var class="Arg">Winnow algorithm</var> is more efficient than the classical Perceptron training algorithm <a href="chapBib.html#biBLittlestone88">[Lit88]</a>.</p>
<p>For the Boolean function <code class="code">Func</code>, which is a monotone disjunction, <code class="code">WinnowAlgorithm</code> returns either a threshold element realizing <code class="code">Func</code> or [] if <code class="code">Func</code> is not trainable by <code class="code">WinnowAlgorithm</code>. The positive ingetger <code class="code">Step</code> which is not equal to 1 defines the value on which we change parameters while running the algorithm and the positive integer <code class="code">Max_Iter</code> defines the maximal number of iterations.</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">x:=Indeterminate(GF(2),"x");;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">y:=Indeterminate(GF(2),"y");;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">pol:=x*y+x+y;;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">f:=PolynomialToBooleanFunction(pol,2);</span>
< Boolean function of 2 variables >
<span class="GAPprompt">gap></span> <span class="GAPinput">Display(f);</span>
Boolean function of 2 variables.
[ 0, 0 ] || 0
[ 0, 1 ] || 1
[ 1, 0 ] || 1
[ 1, 1 ] || 1
<span class="GAPprompt">gap></span> <span class="GAPinput">te:=WinnowAlgorithm(f,2,100);</span>
< threshold element with weight vector [ 1, 1 ] and threshold 1 >
<span class="GAPprompt">gap></span> <span class="GAPinput">Display(OutputOfThresholdElement(te));</span>
Boolean function of 2 variables.
[ 0, 0 ] || 0
[ 0, 1 ] || 1
[ 1, 0 ] || 1
[ 1, 1 ] || 1
</pre></div>
<p><a id="X85162EF17EE09E50" name="X85162EF17EE09E50"></a></p>
<h5>3.3-4 Winnow2Algorithm</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">an style='color: green'>8227; Winnow2Algorithm</code>( <var class="Arg">Func</var>, <var class="Arg">Step</var>, <var class="Arg">Max_Iter</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>For any <span class="SimpleMath">X ⊆ Z_2^n</span> and for any <span class="SimpleMath">δ</span> satisfying <span class="SimpleMath">0 < δ ≤ 1</span> let <span class="SimpleMath">F(X,δ)</span> be the class of functions from <span class="SimpleMath">X</span> to <span class="SimpleMath">Z_2^n</span>. Assume that <span class="SimpleMath">F(X,δ)</span> satisfies the following condition:</p>
<p>for each <span class="SimpleMath">f ∈ F(X,δ)</span> there exist <span class="SimpleMath">μ_1,...,μ_n ≥ 0</span> such that for all <span class="SimpleMath">(x_1,...,x_n) ∈ X</span></p>
<p class="pcenter">
\textstyle \sum_{i=1}^n \mu_i x_i \geq 1, \quad \textrm{if} \quad f(x_1,\ldots,x_n)=1
</p>
<p>and</p>
<p class="pcenter">
\textstyle \sum_{i=1}^n \mu_i x_i \leq 1, \quad \textrm{if} \quad f(x_1,\ldots,x_n)=0.
</p>
<p>In other words, the inverse images of 0 and 1 are linearly separable with a minimum separation that depends on <span class="SimpleMath">δ</span>. <code class="code">Winnow2</code> algorithm is designed for training this class of the Boolean functions <a href="chapBib.html#biBLittlestone88">[Lit88]</a>.</p>
<p>For the Boolean function <code class="code">Func</code> from the class of Boolean functions which is described above, the function <code class="code">Winnow2Algorithm</code> returns either a threshold element which realizes <code class="code">Func</code> or [] if <code class="code">Func</code> is not trainable by <code class="code">Winnow2Algorithm</code>. The positive integer <code class="code">Step</code> which is not equal to 1 defines the value on which we change parameters while running the algorithm.</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">##Conjunction can not be trained by Winnow algorithm.</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">x:=Indeterminate(GF(2),"x");;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">y:=Indeterminate(GF(2),"y");;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">pol:=x*y;;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">f:=PolynomialToBooleanFunction(pol,2);</span>
< Boolean function of 2 variables >
<span class="GAPprompt">gap></span> <span class="GAPinput">te:=WinnowAlgorithm(f,2,100);</span>
[ ]
<span class="GAPprompt">gap></span> <span class="GAPinput">## But in the case of Winnow2 we can obtain the desirable result.</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">te:=Winnow2Algorithm(f,2,100);</span>
< threshold element with weight vector [ 1/2, 1/2 ] and threshold 1 >
<span class="GAPprompt">gap></span> <span class="GAPinput">Display(te);</span>
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 ]
</pre></div>
<p><a id="X7C4B705884A78907" name="X7C4B705884A78907"></a></p>
<h5>3.3-5 STESynthesis</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">an style='color: green'>8227; STESynthesis</code>( <var class="Arg">Func</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>The function <code class="code">STESynthesis</code> is based on the algorithm proposed in <a href="chapBib.html#biBDertouzos65">[Der65]</a>. In each iteration we perturb an <span class="SimpleMath">n+1</span>-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 <code class="code">Func</code> 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 <code class="code">STE_Synthesis</code> will be stopped.</p>
<p>For the Boolean function <code class="code">Func</code> the function <code class="code">STESynthesis</code> returns a threshold element if <code class="code">Func</code> is STE-realizable or an empty list otherwise.</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">f:=x*y+x+y;;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">x:=Indeterminate(GF(2),"x");;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">y:=Indeterminate(GF(2),"y");;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">pol:=x*y+x+y;;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">f:=PolynomialToBooleanFunction(pol,2);;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">te:=STESynthesis(f);</span>
< threshold element with weight vector [ 2, 2 ] and threshold 1 >
<span class="GAPprompt">gap></span> <span class="GAPinput">Display(te);</span>
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 ]
</pre></div>
<div class="chlinkprevnextbot"> <a href="chap0.html">[Top of Book]</a> <a href="chap0.html#contents">[Contents]</a> <a href="chap2.html">[Previous Chapter]</a> <a href="chap4.html">[Next Chapter]</a> </div>
<div class="chlinkbot"><span class="chlink1">Goto Chapter: </span><a href="chap0.html">Top</a> <a href="chap1.html">1</a> <a href="chap2.html">2</a> <a href="chap3.html">3</a> <a href="chap4.html">4</a> <a href="chap5.html">5</a> <a href="chapBib.html">Bib</a> <a href="chapInd.html">Ind</a> </div>
<hr />
<p class="foot">generated by <a href="http://www.math.rwth-aachen.de/~Frank.Luebeck/GAPDoc">GAPDoc2HTML</a></p>
</body>
</html>
¤ Dauer der Verarbeitung: 0.36 Sekunden
¤
*© Formatika GbR, Deutschland
|
|