Машинско учење
Perceptron (najarno od prez)
• Linear Classifiers:
Inputs are feature values, each feature has a weight
Sum is the activation = Positive, output +1 ▪ Negative, output –1
• Weights
Binary case: compare features to a weight vector
Learning: figure out the weight vector from examples
• BInary Decision Rule
In the space of feature vectors
- Examples are points
- Any weight vector is a hyperplane
- One side corresponds to Y=+1
- Other corresponds to Y=-1
• Learning: Binary Perceptron (CITAJ OD PREZ!!!!!)
Start with weights = 0
For each training instance:
- Classify with current weights
- If correct (i.e., y=y*), no change!
- If wrong: adjust the weight vector
• Multiclass Decision Rule
If we have multiple classes:
- A weight vector for each class 𝑤𝑦
- Score (activation) of a class y 𝑤𝑦 ⋅ 𝑓(𝑥)
- Prediction highest score wins 𝑦 = arg 𝑦 max 𝑤𝑦 ⋅ 𝑓 (𝑥 )
- Multiclass Perceptron
o Start with all weights = 0
o Pick up training examples one by one
o Predict with current weights 𝑦 = arg 𝑦 max 𝑤𝑦 ⋅ 𝑓(𝑥)
o If correct, no change!
o If wrong: lower score of wrong answer, raise score of right answer
𝑤𝑦 = 𝑤𝑦 − 𝑓(𝑥)
𝑤𝑦∗ = 𝑤𝑦∗ + 𝑓(𝑥)
Properties of perceptrons
- Separability: true if some parameters get the training set perfectly correct.
- Convergence: if the training is separable, perceptron will eventually converge
(binary case)
- Mistake Bound (only for separable cases): the maximum number of mistakes
𝑘
(binary case) related to the margin or degree of separability 𝑚𝑖𝑠𝑡𝑎𝑘𝑒 < 𝛿2
Problems with the Perceptron
- Noise: if the data isn’t separable, weights might thrash - Averaging weight
vectors over time can help (averaged perceptron)
- Mediocre generalization: finds a “barely” separating solution
- Overtraining: test / held-out accuracy usually rises, then falls (Overtraining is a
kind of overfitting)
Comparison
Naïve Bayes
- Builds a model training data, Gives prediction probabilities, Strong assumptions
about feature independence , One pass through data (counting)
Perceptrons
- Makes less assumptions about data, Mistake-driven learning, Multiple passes
through data (prediction), Often more accurate
Decision trees
Decision trees classify instances by sorting them down the tree from the root to some leaf
node, which provides the classification of the instance.
Each inner node in the tree specifies a test of some attribute of the instance, each branch
descending from a node corresponds to one of the possible values for the attribute, each
leaf node assigns a classification. Test conditions involve using only a single attribute at a
time.
Advantages: Inexpensive to construct, Extremely fast at classifying unknown records,
Easy to interpret for small-sized trees, Robust to noise, Can easily handle redundant or
irrelevant attributes
Disadvantages: Space of possible decision trees is exponentially large, Greedy
approaches are often unable to find the best tree, Does not take into account interactions
between attributes, Each decision boundary involves only a single attribute
→ Design Issues of Decision Tree Induction
How should training examples be split?
- Method for specifying test condition (Splitting Criterion) - depending on attribute
types
Depends on attribute types: Binary, Nominal, Ordinal, Continuous
Depends or number of ways to split: Binary (two not empty subsets) or Multi-way split
(many subsets ex. Marital status: single, divorced, married)
Nominal is just 2 subsets of whatever split, while ordinal must preserve some order (ex.
When we have sizes, we cant split them into {S,L} and {M,XL} because L>M). For
continuous we find a cut-off spot and split there (ex. Annual income > 80k? --> yes/no)
- Measure for evaluating the goodness of a test condition (Selecting Best Attribute) -
information gain, gain ratio, Gini index, misclassification error, statistical test, …
→ Attribute Selection Measures
An attribute selection measure is a heuristic for selecting the splitting criterion that best
separates a given data set D of class-labeled training tuples into individual classes.
The attribute having the best score for the measure is chosen as the splitting attribute for
the given tuples.
Three popular attribute selection measures:
- Information gain: biased towards multivalued attributes.
- Gain ratio: tends to prefer unbalanced splits in which one partition is much smaller
than the others.
- Gini index: tends to favor tests that result in equal-sized partitions and purity in
both partitions.
→ Model Overfitting
(GI IMA NA PROBEN TEST)
*Training error: Train a model on the training dataset, then test the model on the same
training set. The error rate is called “training error,” which evaluates how well the model
fits the training data.
*Test error: Test the model on a test dataset that is different from the training set. The error
rate is called “test error,” which evaluates how well the model generalizes to unseen data.
Overfitting means a model fits the training data very well but generalizes to unseen data
poorly. (due to noise and insufficent examples) . To avoid: Halt tree construction early ( do
not split a node unnecessarily) or remove branches from a fully grown tree)
Underfitting: when model is too simple, both training and test errors are large
→ Classification in Large Databases
Classification: a classical problem extensively studied by statisticians and machine
learning researchers.
Scalability: Classifying data sets with millions of examples and hundreds of attributes
with reasonable speed.
Why is decision tree induction popular? - faster learning speed, convertible to simple and
easy to understand classification rules, can use SQL queries for accessing databases,
comparable classification accuracy with other methods.