A short keynote review of Course at school

---

Statistical Learning

Four Elements in Machine Learning:

• Data
• Model
• Learning Rule
• Optimization Algorithm

Learning Rules:

$|f(x,{\theta }^{\ast })-y|\le ϵ,\forall (x,y)\in X\times Y$

Loss function: $L(y,f(x;\theta ))=1/2(y-f(x;\theta ){)}^2$ (Quadratic loss function)

Expected Risk (期望风险) $R(\theta )=E_{(}x,y)\sim p_r(x,y)[ℒ(y,f(x;\theta ))]$

Empirical Risk:

Expected risk is unknown, approximated by empirical risk

$R_{\mathcal{D}}^{emp}(\theta )=\frac{1}{N}\sum _{n=1}^N\mathcal{L}(y^{(n)},f(x^{(n)},\theta ))$

ML problem is transformed into an optimization problem(Empirical risk minimization)

Gradient Descent

SGD: sampling one samples in each iteration ${\theta }_t+1={\theta }_t-\alpha \partial L(y^n,f(x^n;\theta ))/\partial \theta ,n=1\cdots N$

Mini-Batch SGD -> parallel computing

Generalization error: $R(\theta )-R_{\mathcal{D}}^{emp}(\theta )$

Regularization:

• Add optimization constraints(L1/L2 constraints, Data enhancement)
• Interfere optimization process(Weight attenuation, SGD, Early Stop)

Supervised Learning I

Supervised Learning II

UnSupervised Learning I

The data have no target attribute. We want to explore the data to find some intrinsic structures in them.

• K-means

  • partitional clustering
  • centroid
  • Steps
    • Assign each data point to the closest centroid
    • Re-compute the centroids using the cur
    • re-assignments87
    • centroids
    • SSE -> may lead to local optimum
  • disk version
    • centroids can be computed incrementally
  • Strengths
    • Efficient O(tkn)
    • Simple
  • Weaknesses
    • mean must defined
      • categorical data -> frequence
    • specify k
    • sensitive to outliers
      • over a few iterations than remove some data points
      • random sampling
    • not hyper-ellipsoids (or hyper-spheres)

• Common ways to represent clusters

  • represent by centroid
  • compute radius & standard deviation
  • if not hyper-spherical shape, centroids are not sufficient

DBSCAN/Spectral Clustering for not hyper-ellipsoids better

• Hierarchical Clustering

  • Dendrogram(tree)
  • Methods
    • Agglomerative(bottom up)
    • Divisive (top down)
  • distance of two clusters
    • Single link(closest point) -> find arbitrarily shaped but may chain effect n^2
    • Complete link(furthest point) -> sensitive to outliers n^2log
    • Average link n^2log
    • Centroids

• Distance functions

  • Numeric Attributes (对于点对的差做...)
    • Manhattan(绝对值和)
    • Squared Euclidean(平方和)
    • Euclidean(平方和开根)
    • Weighted Euclidean(加权平方和开根)
    • Chebyshev(最大绝对值)
  • Binary Attributes
    • Symmetric
      • SMC 匹配值的个数/总个数
    • Asymmetric
      • Jaccard coefficient 交/并
  • Nominal Attributes 类似SMC
  • text
    • cosine
  • Standardization
    • Range Normalization (x-min)/(max-min)
    • z-score (x-μ)/σ
  • Ratio-scaled Attributes -> log -> interval-scaled attribuete
  • Ordinal attributes -> like Nominal but values have a numerical ordering(age attribute)

• Cluster Evaluation

  • Ground Truth
  • Entropy
  • Purity
  • Internal information
    • Intra-cluster Cohesion/compactness -> 簇内紧密度 -> SSE
    • Inter-cluster separation /isolation(不同簇之间的相隔程度)

• Graph Clustering

  • Cut Criteria
    • Normalized Cut: $\text{Ncut}(A,B)=\frac{cut(A,B)}{vol(A)}+\frac{cut(A,B)}{vol(B)}$
  • Spectral Graph Partitioning
    • A⋅x=λ⋅x
    • λ Eigenvectors
  • Steps:
    • Pre-processing
    • Decomposition
    • Grouping

UnSupervised Learning II

• Gaussian mixture models
• EM algorithm
• KDE
• Mean-shift algorithm
• Self organizing map