| products/Sources/formale Sprachen/GAP/pkg/thelma/doc/chap3_mj.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>
< script type= "text/javascript"
src= "https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.0/MathJax.js?config=TeX-AMS-MML_HTMLorMML">
</ script>
< 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_mj.html">Top< /a> <a href="chap1_mj.html">1</a> <a href="chap2_mj.html">2</a> <a href="chap3_mj.html">3</a> <a href="chap4_mj.html">4</a> <a href="chap5_mj.html">5</a> <a href="chapBib_mj.html">Bib</a> <a href="chapInd_mj.html">Ind</a> </div>
<div class="chlinkprevnexttop"> <a href="chap0_mj.html">[Top of Book]</a> <a href="chap0_mj.html#contents">[Contents]</a> <a href="chap2_mj.html">[Previous Chapter]</a> <a href="chap4_mj.html">[Next Chapter]</a> </div>
<p id="mathjaxlink" class="pcenter"><a href="chap3.html">[MathJax off]</a></p>
<p><a id="X83DFEF607CDA3594" name="X83DFEF607CDA3594"></a></p>
<div class="ChapSects"><a href="chap3_mj.html#X83DFEF607CDA3594">3 <span class="Heading">Threshold Elements</span></a>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap3_mj.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_mj.html#X853FF8AC85E5C4CE">3.1-1 ThresholdElement</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap3_mj.html#X7E7F95D57EB87BB4">3.1-2 IsThresholdElement</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap3_mj.html#X7F293D2D810ADBBB">3.1-3 OutputOfThresholdElement</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap3_mj.html#X8116985278C60D33">3.1-4 StructureOfThresholdElement</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap3_mj.html#X800C6898856CD0E9">3.1-5 RandomThresholdElement</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap3_mj.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_mj.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_mj.html#X8351E15B7CCDEB62">3.2-1 CharacteristicVectorOfFunction</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap3_mj.html#X8502A0827ECF1FFE">3.2-2 IsCharacteristicVectorOfSTE</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap3_mj.html#X7B0855E28717AF12">3.2-3 IsInverseInKernel</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap3_mj.html#X83B234DB7F260879">3.2-4 IsKernelContainingPrecedingVectors</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap3_mj.html#X7877118A7A9C51CB">3.2-5 IsRKernelBiggerOfCombSum</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap3_mj.html#X83D3B18486C5D0B7">3.2-6 BooleanFunctionBySTE</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap3_mj.html#X8451E4EA7F06222F">3.2-7 PDBooleanFunctionBySTE</a></span>
</div></div>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap3_mj.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_mj.html#X83567B7D79958EBF">3.3-1 ThresholdElementTraining</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap3_mj.html#X83CD889E8125E949">3.3-2 ThresholdElementBatchTraining</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap3_mj.html#X81FEA8AF80573A12">3.3-3 WinnowAlgorithm</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap3_mj.html#X85162EF17EE09E50">3.3-4 Winnow2Algorithm</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap3_mj.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: \mathbb{Z}_2^n \to \mathbb{Z}_2\)</span> defined by the following relations:</p>
<p class="center">\[
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, \ldots, x_n)\)</span> is the <var class="Arg">input</var> vector. The vector <span class="SimpleMath">\((w_1, \ldots, 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 \leq 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_mj.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_mj.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_mj.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_mj.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,\ldots,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="center">\[
y_i = 2x_i-1, \quad (i = 1,2,\ldots,n)
\]</p>
<p class="center">\[
g(y_1,\ldots,y_n) = 2f(x_1,\ldots,x_n)-1.
\]</p>
<p>For each <span class="SimpleMath">\(i \in \{1,2,\ldots,n\}\)</span> the <span class="SimpleMath">\(i\)</span>-th column of the truth table of the function <span class="SimpleMath">\(g(y_1,\ldots,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="center">\[
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 \cdot G\)</span> is the classical inner (scalar) product for each <span class="SimpleMath">\(k \in \{1,\ldots,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_mj.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 \leq 6\)</span> variables obtained from <a href="chapBib_mj.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 \leq 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_mj.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,\ldots,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_mj.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 \in \mathbb{Z}_2^n\)</span> is called an additive inverse to <span class="SimpleMath">\(a \in \mathbb{Z}_2^n\)</span> if <span class="SimpleMath">\(a \oplus 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=(\alpha_1,\ldots,\alpha_n) \in \mathbb{Z}_2^n\)</span> precedes a vector <span class="SimpleMath">\(b=(\beta_1,\ldots,\beta_n) \in \mathbb{Z}_2^n\)</span> (we denote it as <span class="SimpleMath">\(a \prec b\)</span>) if <span class="SimpleMath">\(\alpha_i \leq \beta_i \textrm{ for each } i=1,\ldots, n\)</span>.</p>
<p>For a given vector <span class="SimpleMath">\(c \in \mathbb{Z}_2^n\)</span> denote <span class="SimpleMath">\(M_c=\{\;a\in \mathbb{Z}_2^n \;\mid\; a \prec c \;\}\)</span>.</p>
<p>Let <span class="SimpleMath">\(f(x_1,\ldots,x_n)\)</span> be a Boolean function with reduced kernel <span class="SimpleMath">\(T(f)=\{K(f)_j \mid j=1,2,\ldots, m \}\)</span>. If <span class="SimpleMath">\(f\)</span> is implemented by a single threshold element (STE), then there exists <span class="SimpleMath">\(j \in \{1,\ldots, m \}\)</span> such that</p>
<p class="center">\[
\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_mj.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,\ldots,x_n)\)</span> be a Boolean function with reduced kernel <span class="SimpleMath">\(T(f)\)</span>. Denote</p>
<p class="center">\[
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="center">\[
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="center">\[
|A| \geq \sum_{i=0}^{k_A^*} {{k_A^*}\choose{i}},
\]</p>
<p>where <span class="SimpleMath">\({{k_A^*}\choose{i}}\)</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_mj.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_mj.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,\ldots,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_mj.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,\ldots,w_n)\)</span> and a real threshold <span class="SimpleMath">\(T\)</span> such that</p>
<p class="center">\[
a \in f^{-1}(1) \quad \Longrightarrow \quad a\cdot w^T \geq T,
\]</p>
<p class="center">\[
a \in f^{-1}(0)\quad \Longrightarrow \quad a\cdot w^T < T,
\]</p>
<p>where <span class="SimpleMath">\(a\cdot 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_mj.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_mj.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:\mathbb{Z}_2^n \to \mathbb{Z}_2\)</span> which can be presented in the following form:</p>
<p class="center">\[
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_mj.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 \subseteq \mathbb{Z}_2^n\)</span> and for any <span class="SimpleMath">\(\delta\)</span> satisfying <span class="SimpleMath">\(0 < \delta \leq 1\)</span> let <span class="SimpleMath">\(F(X,\delta)\)</span> be the class of functions from <span class="SimpleMath">\(X\)</span> to <span class="SimpleMath">\(\mathbb{Z}_2^n\)</span>. Assume that <span class="SimpleMath">\(F(X,\delta)\)</span> satisfies the following condition:</p>
<p>for each <span class="SimpleMath">\(f \in F(X,\delta)\)</span> there exist <span class="SimpleMath">\(\mu_1,\ldots,\mu_n \geq 0\)</span> such that for all <span class="SimpleMath">\((x_1,\ldots,x_n) \in X\)</span></p>
<p class="center">\[
\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="center">\[
\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">\(\delta\)</span>. <code class="code">Winnow2</code> algorithm is designed for training this class of the Boolean functions <a href="chapBib_mj.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_mj.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_mj.html">[Top of Book]</a> <a href="chap0_mj.html#contents">[Contents]</a> <a href="chap2_mj.html">[Previous Chapter]</a> <a href="chap4_mj.html">[Next Chapter]</a> </div>
<div class="chlinkbot"><span class="chlink1">Goto Chapter: </span><a href="chap0_mj.html">Top</a> <a href="chap1_mj.html">1</a> <a href="chap2_mj.html">2</a> <a href="chap3_mj.html">3</a> <a href="chap4_mj.html">4</a> <a href="chap5_mj.html">5</a> <a href="chapBib_mj.html">Bib</a> <a href="chapInd_mj.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.26 Sekunden
¤
*© Formatika GbR, Deutschland
|
|