 conjecture 50
 conjecture 112
2-monotonic Boolean function 16 53
2-monotonic Boolean function, recognition algorithm 53
Accuracy parameter 90
Activation 2
Activation function 3
Affine functions 103
Affinely independent 104
Algorithm for learning see "Learning algorithm"
Algorithm, efficient 49
Algorithm, polynomial-time 50
Algorithm, randomized 111
Algorithm, running time 50
Antichain 66 74
Antichain, size of 66
Asummability 26
Asummability and polynomial threshold functions 32
Augmented vector 32
Big-O notation 50
Boltzmann machine 1 115
Boltzmann machine for maximum cut 117
Boltzmann machine for optimization 117
Boltzmann machine for traveling salesman problem 118
Boltzmann machine, architecture 115
Boltzmann machine, consensus function 115
Boltzmann machine, parallel computation in 116
Boltzmann machine, sequential computation in 116
Boltzmann machine, states 115
Boolean formula 10
Boolean function 9
Boolean function, 2-monotonic 16 53
Boolean function, classes of 14
Boolean function, CNF representation 13 14
Boolean function, degree of 14
Boolean function, depending on a coordinate 73
Boolean function, DNF representation 12
Boolean function, down-projection of 22
Boolean function, dual of 14
Boolean function, false point of 11
Boolean function, implicant of 13
Boolean function, increasing 15
Boolean function, negative example of 11
Boolean function, nested 76
Boolean function, polynomial threshold representation 31
Boolean function, positive example of 11
Boolean function, prime implicant 13
Boolean function, projection of 23 51
Boolean function, regular 15 17 53
Boolean function, representation by network 61
Boolean function, threshold order of 31
Boolean function, true point of 11
Boolean function, unate 15
Boolean function, up-projection of 22
Boolean hypercube 9
Boolean hypercube as a graph 10
Boolean hypercube, geometry 9
Boolean hypercube, partial order on 10
Boolean polynomial threshold function 30
Boolean threshold function see "Threshold function"
Boundary points 72
Chain 66
Chebyshev's inequality 96
Chopping 62
Circuit complexity 61 70
Class of networks 109
Closure under projection of polynomial threshold functions 30
Closure under projection of threshold functions 23
CNF formula 13
CNF representation 13 14
Combinatorial optimization 116
Complexity of determining threshold order 52
Complexity of learning 109
Complexity of membership problem 51
Complexity of threshold synthesis 56
Complexity theory 49
Computation unit 2
Confidence parameter 90
Conjunction 11
Conjunctive normal form 13
Consensus function 115
Consistency problem 110
Consistency problem and learnability 111
Consistent learning algorithm 71 84
Convex combination 25
Convex hull 25
Convex hull, rational 27
Convex set 25
Covering 66
Decision lists 17 45 62
Decision lists and other Boolean functions 18
Decision lists and polynomial threshold functions 31
Decision lists and threshold functions 28
Decision lists, based on threshold functions 63
Decision lists, specification number 79
Decision problem 50
Degree of Boolean function 14
Degree of DNF 14
Degree of polynomial threshold function 30
Degree of polynomial threshold unit 5
Directed graph 115
Disjunction 11
Disjunctive normal form 11
DNF formula 11
DNF formula and network 61
DNF formula, degree of 14
DNF formula, irredundant 15 52
DNF non-tautology 50
DNF representation 12
Down-projection 22 77
Down-set 16 94
Dual 14
Dualization 53 54
Dualization algorithm 53 54 58
Efficiency of perceptron learning 87
Efficient algorithm 49
Efficient learning algorithm 109
Efficient learning algorithm for perceptron 110
Efficient learning algorithm, sufficient condition 110
Error of a function 90
Essential examples 77
Exclusive-or function XOR 3 7
False point 11
Feed-forward network 1 2 6
Fibonacci numbers 45
General position 9
Geometrical interpretation of polynomial threshold function 32
Geometrical interpretation of threshold function 25
Graph colorability 50 112
Group action 97
Growth function 91
Growth function and VC-dimension 93
Growth function of perceptron 103
Harmonic analysis 70
Hidden layer 6
Homogeneous threshold function 22 101
Homogeneous threshold function and shattering 101
Hypercube 9
Hyperface function 72
Hyperplane separation 25
Hypothesis 84
Hypothesis space 90
Implicant 13
Increasing Boolean function 15
Incremental perceptron learning algorithm 85
Inner product 21
Input layer 6
Input unit 5
Instance 50
Integral threshold 43
| Integral weight-vector 43
Irredundant DNF 15 52
Irrelevant attributes 79
Labeled example 83
Layers 6
Learning 83
Learning algorithm 83 84 89
Learning algorithm for class of networks 109
Learning algorithm, efficiency of 109
Learning, complexity of 109
Learning, probabilistic model 89
Lexicographic order 32 53 58
Linear dimension 102
Linear dimension and VC-dimension 102
Linear inequalities and threshold functions 43
Linear programming 53 85
Linear separability 25
Linear threshold function see "Threshold function"
Linear threshold network 1
Linear threshold recognition 52
Linear threshold unit 2 3
Linearly separable functions see "Threshold function"
Literals 10
Lower bound on sample length 98
m-augment 32
Maximal false point see "MFP"
Maximum cut problem 117
Measurability conditions 99
Membership problem 51
Membership problem, complexity of 51
Membership queries 81
MFP 16 53 73
MFP of regular functions 55
Minimal true point see "MTP"
Monomial 14
MTP 16 52 73
MTP and prime implicants 16
MTP of dual function 16 53
Multilayer network 6
Negation 13
Negative example 11
Nested function 76
Network and DNF formula 61
Network, classes of 109
Network, depth 6
Network, feed-forward 1 6
Network, linear threshold 1 61
Network, linear threshold, VC-dimension 106
Network, multilayer 6
Network, representation of Boolean functions 9 61
Network, sigmoid 1 70
Network, sigmoid, VC-dimension 107
Network, state 7
Network, stochastic 115
Network, stratified 6 66
Network, VC-dimension of 92
Neural network see "Network"
neuron 2
NP-complete problem 50
NP-hard problem 50
Number of polynomial threshold functions, lower bound 40
Number of polynomial threshold functions, upper bound 40
Number of threshold functions, asymptotic bound 39
Number of threshold functions, lower bound 38
Number of threshold functions, upper bound 37
Observed error 95
Output function 84
Output layer 6
Output unit 5
PAC learning 89 90
PAC learning and VC-dimension 94 99
PAC learning of finite spaces 91
PAC learning, complexity of 109
PAC learning, extensions of 99
PAC learning, hardness of 112
PAC learning, sample length lower bound 98
PAC learning, sufficient sample length 95
Parameter space 36
Parity function 12
Parity function, network representation of 62 64 66 69
Parity function, threshold order 58
Partial order 10 66 73
Partially ordered set see "Poset"
Perceptron 3 7
Perceptron, growth function of 103
Perceptron, incremental learning algorithm 85
Perceptron, learning algorithm for 84
Perceptron, sets shattered by 103
Perceptron, VC-dimension of 103
Polynomial threshold function 21 29
Polynomial threshold function and asummability 32
Polynomial threshold function and decision lists 31
Polynomial threshold function, Boolean 30
Polynomial threshold function, closure under projection 30
Polynomial threshold function, degree of 30
Polynomial threshold function, geometrical interpretation 32
Polynomial threshold function, lower bound on number 40
Polynomial threshold function, real 29
Polynomial threshold function, representation of Boolean function 31
Polynomial threshold function, threshold order of 31
Polynomial threshold function, upper bound on number 40
Polynomial threshold function, VC-dimension 104
Polynomial threshold unit 4 5
Polynomial threshold unit, degree of 5
Polynomial-time algorithm 50
POSET 66
Poset, antichain in 66
Poset, chain in 66
Poset, covering in 66
Poset, maximal element 66
Poset, minimal element 66
Poset, rank function 66
Positive example 11
Prime implicant 13 52
Probabilistic model of learning 89
Product probability distribution 90
Projection 23 51
Projection of polynomial threshold function 30
Projection of threshold function 23
Projection property 51
Quadratic programming 117
r-out-of-k function 79
Randomized algorithm 111
Rank function 66
Rational convex hull 27
Real polynomial threshold function 29
Real threshold function 22
Recognition algorithm for 2-monotonic functions 53
Regular Boolean function 15 17 53
Running time 50
Sample complexity 101
Sauer's lemma 93
Self-organization 115
Separating Hyperplanes Theorem 26
Shattered sample 92
Sigmoid function 4
Sigmoid network 1 70
Sigmoid unit 2 4
Sign function 3
Signature 77
Simulated annealing 116
Sizes of weights in nonstandard representation 47
Sizes of weights, can be exponential 44
Sizes of weights, can be superexponential 46
Sizes of weights, upper bound 44
Specification number 71
Specification number, average 79 81
Specifying set 71
Sperner's theorem 66 74
State 7
|
|
|
О проекте