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 .
Number of Rows (): The number of independent hash functions used.
Number of Columns (): 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 .
Cosine: In many contexts, Cosine Similarity and Cosine Distance are treated as related, though the distance is often defined as .
Mathematical Norms and KD Trees
Norm Computations: Master the formulas for common lp-norms, including:
Norm: The number of non-zero elements.
Norm: The sum of absolute values (taxicab norm).
Norm: The standard Euclidean distance.
Norm (Infinity Norm): The maximum absolute value among elements.
Manhattan Distance: Understand that the Manhattan distance is directly equivalent to the norm calculation.
KD Trees (K-Dimensional Trees):
Purpose: Recognize the role of KD Trees in optimizing Nearest Neighbor Search (-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., ).
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 to the current nearest point against the perpendicular distance from 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: .
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., ) 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 and an approximate distribution , 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.
and Regularization: Know that (Lasso) promotes sparsity (feature selection) while (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: .
Error Rate: .
Precision: .
Recall: .
F1 Score: Understand the relationship between F1, Precision, and Recall: .
ROC Curve and AUC:
True Positive Rate (TPR): Also known as Sensitivity or Recall.
False Positive Rate (FPR): Equivalent to .
Youden Index: Locate the point on the ROC curve that maximizes the Youden Index (). This point is geographically closest to the top-left corner () 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 .
Least Squares: Unlike MSE, the standard Least Squares formulation may not divide by .
Gradient Descent: Masters the update rule to find the minimum of the cost function: .
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 .
PCA and SVD
Principal Component Analysis (PCA):
Core Concepts: Projection and dot products.
Implementation Steps: From dimensions to top- dimensions.
Unbiased Estimation: In the construction of the covariance matrix , use the unbiased estimator formula involving rather than .
Singular Value Decomposition (SVD):
Data Compression: Understand why SVD is used for compression (e.g., image compression).
Implementation: Perform decomposition on matrix to find , , and .
PCA Connection: PCA can be implemented via SVD, where the right singular vectors (from ) 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.