Difference between revisions of "Perceptron"
m |
m (→Properties) |
||
| (3 intermediate revisions by the same user not shown) | |||
| Line 2: | Line 2: | ||
Let <math>n</math> be a positive integer and let <math>t, \{w_i\}_{i=1}^n</math> be real numbers. The '''perceptron''' function, or '''linear threshold''' function <math>f:\{-1,1\}^n \to \{-1,1\}</math> with weights <math>w_i</math> and threshold <math>t</math> is defined as | Let <math>n</math> be a positive integer and let <math>t, \{w_i\}_{i=1}^n</math> be real numbers. The '''perceptron''' function, or '''linear threshold''' function <math>f:\{-1,1\}^n \to \{-1,1\}</math> with weights <math>w_i</math> and threshold <math>t</math> is defined as | ||
| − | <math> f(x) = \begin{cases} 1, & \text{if} ~ \sum_i w_i x_i \geq t \\ | + | :::{| class="wikitable" |
| + | |- | ||
| + | |<math> f(x) = \begin{cases} 1, & \text{if} ~ \sum_i w_i x_i \geq t \\ | ||
-1 & \text{otherwise} \end{cases}</math> | -1 & \text{otherwise} \end{cases}</math> | ||
| + | |} | ||
| − | The [[majority]] function is a special case of the perceptron, with threshold <math>t=0</math> and all weights <math>w_i</math> equal to each other. | + | The [[majority]] function is a special case of the perceptron, with threshold <math>t=0</math> and all weights <math>w_i</math> equal to each other. |
== Properties == | == Properties == | ||
| Line 11: | Line 14: | ||
* If all weights are non-negative, or all weights are non-positive, the function is [[:Category:monotone function | monotone]]. | * If all weights are non-negative, or all weights are non-positive, the function is [[:Category:monotone function | monotone]]. | ||
* The weights and threshold may be chosen so that the function is [[:Category:balanced function | balanced]]. | * The weights and threshold may be chosen so that the function is [[:Category:balanced function | balanced]]. | ||
| − | * | + | * The perceptron is a special case of the [[polynomial threshold]] function. |
| + | * A perceptron has [[nearest neighbor representation|nearest neighbor]] complexity equal to <math>NN(f) = 2</math>. However, the Boolean nearest-neighbor complexity <math>BNN(f)</math> can be high, e.g for the perceptron with all weights equal and <math>t = n/3</math>, then <math>2^{\Omega(n)}</math> markers are required. <ref>Péter Hajnal, Zhihao Liu, György Turán, [https://arxiv.org/pdf/2004.01741.pdf Nearest neighbor representations of Boolean functions], Theorem 4</ref> | ||
== References == | == References == | ||
Latest revision as of 14:05, 5 April 2021
Definition
Let [math]n[/math] be a positive integer and let [math]t, \{w_i\}_{i=1}^n[/math] be real numbers. The perceptron function, or linear threshold function [math]f:\{-1,1\}^n \to \{-1,1\}[/math] with weights [math]w_i[/math] and threshold [math]t[/math] is defined as
[math] f(x) = \begin{cases} 1, & \text{if} ~ \sum_i w_i x_i \geq t \\ -1 & \text{otherwise} \end{cases}[/math]
The majority function is a special case of the perceptron, with threshold [math]t=0[/math] and all weights [math]w_i[/math] equal to each other.
Properties
- If all weights are equal to each other, the function is symmetric.
- If all weights are non-negative, or all weights are non-positive, the function is monotone.
- The weights and threshold may be chosen so that the function is balanced.
- The perceptron is a special case of the polynomial threshold function.
- A perceptron has nearest neighbor complexity equal to [math]NN(f) = 2[/math]. However, the Boolean nearest-neighbor complexity [math]BNN(f)[/math] can be high, e.g for the perceptron with all weights equal and [math]t = n/3[/math], then [math]2^{\Omega(n)}[/math] markers are required. [1]
References
- ↑ Péter Hajnal, Zhihao Liu, György Turán, Nearest neighbor representations of Boolean functions, Theorem 4
