Comprehensive Final Exam Study Guide: Data Analysis and Machine Learning

Count-Min Sketch and Data Structures

  • Count-Min (CM) Sketch Purpose: It is essential to understand the fundamental purpose of the Count-Min sketch. Specifically, one should be able to differentiate it from a Bloom Filter. While both are probabilistic data structures, their use cases in frequency estimation versus set membership differ.

  • Error Bounds and Parameters: In the context of the Count-Min sketch, if an upper bound on the total error is provided, students must understand the mathematical relationship between the following parameters:

    • Confidence Probability: Expressed as 1−δ1 - \delta.

    • Number of Rows (dd): The number of independent hash functions used.

    • Number of Columns (ww): Also referred to as the width of the two-dimensional array used to map and store data.

Similarity Measures and Text Analysis

  • Jaccard Similarity and Cosine Similarity:

    • Computation Methods: Students must master the calculation of both Jaccard and Cosine similarity when comparing sets, vectors, or text data.

    • Bag of Words (BoW) Model: Understand how this model represents text as a frequency distribution of words to facilitate Cosine similarity calculations.

    • Term Frequency: Cosine similarity involves calculating word frequencies rather than simple binary presence.

  • Similarity vs. Distance:

    • Jaccard: There is a distinct difference between Jaccard Similarity and Jaccard Distance. Jaccard Distance is defined as 1−Jaccard Similarity1 - \text{Jaccard Similarity}.

    • Cosine: In many contexts, Cosine Similarity and Cosine Distance are treated as related, though the distance is often defined as 1−Cosine Similarity1 - \text{Cosine Similarity}.

Mathematical Norms and KD Trees

  • Norm Computations: Master the formulas for common lp-norms, including:

    • L0L_0 Norm: The number of non-zero elements.

    • L1L_1 Norm: The sum of absolute values (taxicab norm).

    • L2L_2 Norm: The standard Euclidean distance.

    • L∞L_\infty Norm (Infinity Norm): The maximum absolute value among elements.

  • Manhattan Distance: Understand that the Manhattan distance is directly equivalent to the L1L_1 norm calculation.

  • KD Trees (K-Dimensional Trees):

    • Purpose: Recognize the role of KD Trees in optimizing Nearest Neighbor Search (kk-NN).

    • Construction Process:

      • Partition Axis: The selection of the first splitting axis is determined by the coordinate axis with the largest variance.

      • Round-Robin Update: Subsequent partitions must follow a round-robin manner (e.g., x-axis→y-axis→z-axis→x-axis\text{x-axis} \rightarrow \text{y-axis} \rightarrow \text{z-axis} \rightarrow \text{x-axis}).

      • Binary Tree Representation: Be able to draw the resulting binary tree based on the data points and the construction logic.

    • Retrieval and Backtracking:

      • Understand the significance of calculating the distance from a target coordinate to the splitting axis (hyperplane).

      • Compare the distance from the target point xx to the current nearest point against the perpendicular distance from xx to the parent node's division line.

      • This comparison determines if the algorithm must backtrack to check the other side of the partition.

Curse of Dimensionality and MinHash

  • Overfitting and Dimensionality: Define the "Curse of Dimensionality" and explain how high-dimensional features can lead to overfitting during model training.

  • Dimensionality Reduction Techniques:

    • Feature Selection: Choosing a subset of existing features.

    • Feature Transformation: Creating new, lower-dimensional features (e.g., PCA).

  • MinHash:

    • Relationship to Jaccard Similarity: Understand the foundational principle that the probability that the MinHash values of two sets are equal is exactly their Jaccard Similarity: P(h(A)=h(B))=J(A,B)P(h(A) = h(B)) = J(A, B).

    • Computation: Master the process for sentences, texts, or sets.

    • Simulation of Permutations: Use random hash functions to simulate row permutations. If required in an exam, the specific hash functions used (e.g., h1,h2h_1, h_2) must be explicitly listed.

Generalization, Regularization, and Information Theory

  • Key Concepts:

    • Generalization: The ability of a model to perform on unseen data.

    • Fitting Types: Underfitting, Overfitting, and Non-convergence.

    • Bias-Variance Trade-off: Understand the concepts of Error, Bias, and Variance and provide examples of their relationships.

  • KL Divergence (Kullback-Leibler Divergence):

    • Definition: A measure of how one probability distribution is different from a second, reference probability distribution.

    • Calculation: Given a true distribution PP and an approximate distribution QQ, be able to compute the value using the formula.

  • Regularization:

    • Empirical vs. Structured Risk: Understand the difference between Empirical Risk Minimization (ERM) and Structured Risk Minimization (SRM), where regularization is used to penalize model complexity.

    • L1L_1 and L2L_2 Regularization: Know that L1L_1 (Lasso) promotes sparsity (feature selection) while L2L_2 (Ridge) penalizes large weights.

Model Evaluation Metrics

  • Confusion Matrix: Master the calculation of metrics from the matrix:

    • TP (True Positive), FP (False Positive), FN (False Negative), TN (True Negative).

    • Accuracy: TP+TNTP+TN+FP+FN\frac{TP + TN}{TP + TN + FP + FN}.

    • Error Rate: 1−Accuracy1 - \text{Accuracy}.

    • Precision: TPTP+FP\frac{TP}{TP + FP}.

    • Recall: TPTP+FN\frac{TP}{TP + FN}.

  • F1 Score: Understand the relationship between F1, Precision, and Recall: F1=2×Precision×RecallPrecision+RecallF1 = \frac{2 \times \text{Precision} \times \text{Recall}}{\text{Precision} + \text{Recall}}.

  • ROC Curve and AUC:

    • True Positive Rate (TPR): Also known as Sensitivity or Recall.

    • False Positive Rate (FPR): Equivalent to 1−Specificity1 - \text{Specificity}.

    • Youden Index: Locate the point on the ROC curve that maximizes the Youden Index (J=Sensitivity+Specificity−1J = \text{Sensitivity} + \text{Specificity} - 1). This point is geographically closest to the top-left corner (0,10, 1) of the plot when measured via Euclidean distance and represents the optimal threshold for classification accuracy.

    • AUC (Area Under the Curve): Used to compare the performance of distinct classifiers; a higher AUC indicates better overall performance.

Linear and Logistic Regression

  • Linear Regression:

    • Matrix Form: Construct linear models in vector form including independent and dependent variables.

    • Cost/Loss Functions:

      • Mean Squared Error (MSE): Generally divided by the number of samples mm.

      • Least Squares: Unlike MSE, the standard Least Squares formulation may not divide by mm.

    • Gradient Descent: Masters the update rule to find the minimum of the cost function: wnew=wold−α∂J∂ww_{new} = w_{old} - \alpha \frac{\partial J}{\partial w}.

  • Logistic Regression:

    • Optimization: Use Maximum Likelihood Estimation (MLE) to derive the optimization objective.

    • Negative Log-Likelihood: Understand how to write the loss function for the entire dataset and derive the gradient with respect to the parameter vector ww.

PCA and SVD

  • Principal Component Analysis (PCA):

    • Core Concepts: Projection and dot products.

    • Implementation Steps: From mm dimensions to top-kk dimensions.

    • Unbiased Estimation: In the construction of the covariance matrix CC, use the unbiased estimator formula involving 1n−1\frac{1}{n-1} rather than 1n\frac{1}{n}.

  • Singular Value Decomposition (SVD):

    • Data Compression: Understand why SVD is used for compression (e.g., image compression).

    • Implementation: Perform decomposition on matrix AA to find UU, Σ\Sigma, and VTV^T.

    • PCA Connection: PCA can be implemented via SVD, where the right singular vectors (from VTV^T) of the centered data matrix correspond to the principal components.

Questions & Discussion

  • PAC Learning: The instructor clarified that PAC (Probably Approximately Correct) learning will not appear in the final exam, although students were encouraged to study it for general knowledge.


To include the Chinese sections in the transcript, you should inform the transcription service or tool you're using to ensure that it captures both English and Chinese audio. You can specify that the transcription should be bilingual or add a note indicating that Chinese spoken sections should not be filtered out. If available, check if there's an option to select multiple languages for transcription. Additionally, you can request a re-analysis of the video, explicitly stating the need for complete accuracy in both languages.