Quellcodebibliothek Statistik Leitseite products/sources/formale Sprachen/GAP/pkg/thelma/doc/   (Algebra von RWTH Aachen Version 4.15.1©)  Datei vom 3.2.2022 mit Größe 41 kB image not shown  

SSL chap3.html   Sprache: HTML

 
 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">‣ 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">‣ 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">‣ 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">‣ 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">‣ 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">‣ 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">‣ 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">‣ 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">‣ 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">‣ 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">‣ 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">‣ 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">‣ 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">‣ 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">‣ 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">‣ 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">‣ 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">‣ 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>

100%


¤ Dauer der Verarbeitung: 0.24 Sekunden  (vorverarbeitet)  ¤

*© Formatika GbR, Deutschland




Wurzel

Suchen

Beweissystem der NASA

Beweissystem Isabelle

NIST Cobol Testsuite

Cephes Mathematical Library

Wiener Entwicklungsmethode

Haftungshinweis

Die Informationen auf dieser Webseite wurden nach bestem Wissen sorgfältig zusammengestellt. Es wird jedoch weder Vollständigkeit, noch Richtigkeit, noch Qualität der bereit gestellten Informationen zugesichert.

Bemerkung:

Die farbliche Syntaxdarstellung ist noch experimentell.