Universal Sentence Encoder

이 동 훈

​

• https://www.math.snu.ac.kr/~hichoi/machinelearning
• https://scikit-learn.org/stable/modules/ensemble.html?highlight=gradient+boost
• https://towardsdatascience.com/understanding-adaboost-2f94f22d5bfe
• https://towardsdatascience.com/an-introduction-to-random-forest-with-python-and-scikit-learn-acf44e514034

​

References

​

• Node: Root, Internal and Leaf(terminal) nodes
• Edge: ramify from a node to child nodes according to a condition
• Tree: A partition of dataset region into sub-regions

​

• Can overfit perfectly
• When and how to split?

​

Decision Tree

​

• Make a partition of the dataset region.
• Majority vote at leaf nodes

Classification Tree

​

• Partition into sub-regions
• Take the average value in the sub-region

Regression Tree

​

• Split a node if labels are impure enough
• Categorical impurity function
• Entropy

​

• Gini

​

• Numerical impurity function
• Divergence

Impurity & Splitting

​

• If impurity decrease is small
• If the number of samples in the leaf node is small
• If the level of node is too high

​

Stop Splitting

​

• Penalize the tree with too many leaf nodes
• Misclassification cost

​

​

​

• An optimally-pruned tree is obtained by pruning sequentially the weakest link violating

Pruning

​

• Ensemble of trees
• Bootstrap resample for each tree
• Use OOB(out-of-bag) samples to evaluate
• Randomly select features for each tree, level and nodes
• Stop splitting at a predetermined level
• Do not prune
• Average trees to make the final predictor

Random Forests

​

• OOB error estimate
• Feature importance
• Impurity importance
• decrease of impurity by the feature
• Gini importance, Entropy importance
• Permutation importance
• Increase of error when values of a feature are permuted
• By OOB set, By test set
• Proximity
• Two data points are close if they are in the same leaf node
• Derived metric
• Discover outliers
• A data point which is far from the other data points with the same label
• Missing value imputation
• Rough fill: mean/mode replacement
• Proximity-based(weighted) imputation

Information from Ensemble

​

• A sequence of weak learners
• Fit the next learner so that the whole sequence minimizes the error

Forward Stagewise Additive Model

​

• A sequence of weak learners on dataset with modified weights to each training samples

​

​

​

​

• As forward stagewise additive model with exponential loss (classification)

Adaboost

​

• Residual for L2 loss can be expressed as gradient

​

​

• Gradient of any differentiable loss can be used for targets ( as gradient-descent)

​

​

​

​

​

• For classification as well as regression

Residual as Gradient

​

• Initialize a learner

​

​

• Repeat:
1. From the gradient of loss function, define new labels and dataset

​

​

• Compute (if line-search used)

​

​

• Define a new model as

Gradient Boosting Machine