Bird
Raised Fist0

K-Nearest Neighbors - Curse of Dimensionality, Approximate NN

THEORYbeginnerInterview freq: high
Choose your preparation mode6 modes available
LearnTraceDebugTrade-offChallenge
🐛
The Dimensionality Dilemma
Started immediately after the last feature update, ongoing for 3 days.

A recommendation system using K-Nearest Neighbors for suggesting products to users based on their browsing history, handling 500K requests per day.

Symptom
Model accuracy is stable, but recall has dropped to 0.0 after adding new features.
📡
Signals
metric
Recall on the test set
Recall dropped from 0.75 to 0.0 after adding 10 new features.
metric
Accuracy on the test set
Accuracy remains stable at 0.85.
distribution
Distance distribution of nearest neighbors
Distances have increased significantly, with most neighbors now at a similar distance.
feature_importance
Feature importance analysis
New features have low importance, but older features' importance has decreased.
log
Model inference logs
Inference time has increased by 30% after adding new features.
🔬
Hypotheses
The curse of dimensionality is affecting the KNN model.
Supporting Signals
Recall dropped to 0.0Distances have increased significantly
Verify: Check if the distance between points has become uniform.
import numpy as np
from scipy.spatial import distance_matrix
X = np.random.rand(100, 20)  # Example data
D = distance_matrix(X, X)
std_dev = np.std(D)
print('Standard deviation of distances:', std_dev)
New features are irrelevant and causing noise.
Supporting Signals
New features have low importanceOlder features' importance has decreased
Verify: Evaluate model performance without the new features.
from sklearn.neighbors import KNeighborsClassifier
from sklearn.metrics import recall_score
knn = KNeighborsClassifier()
X_train_reduced = X_train[:, :10]  # Use only original features
knn.fit(X_train_reduced, y_train)
recall = recall_score(y_test, knn.predict(X_test[:, :10]))
print('Recall without new features:', recall)
🎯
Root Cause
The curse of dimensionality caused by adding irrelevant features.
Why It Happened

Adding high-dimensional features without assessing their relevance increased the distance between points, making neighbors indistinguishable.

🔧
Fix Strategy
ImmediateRollback to the previous model version without the new features.
Short-termRemove the new features and retrain the model.
Long-termImplement feature selection techniques to evaluate feature relevance before adding them.
🐍
Python Fix
Python
from sklearn.feature_selection import SelectKBest, f_classif
selector = SelectKBest(f_classif, k=10)
X_new = selector.fit_transform(X_train, y_train)
knn.fit(X_new, y_train)
✗
Common Wrong Diagnoses
▼ Show
The model is overfitting due to too many features.
Why candidates think this: Adding features can lead to overfitting, especially if they are not relevant.
Why wrong: Overfitting would typically increase recall on the training set, not drop it to 0.0.
The model's hyperparameters are not optimized for the new feature set.
Why candidates think this: Hyperparameter tuning is crucial when feature sets change.
Why wrong: Hyperparameter issues would affect both accuracy and recall, not just recall.
📊
Monitoring to Add
  • Monitor recall and precision metrics separately for early detection of class imbalance issues.
  • Track feature importance changes after each deployment.
  • Set alerts for significant increases in inference time.
📋
Process Change

Introduce a mandatory feature relevance assessment phase before integrating new features.

🏗️
Architectural Change

Adopt dimensionality reduction techniques like PCA as a preprocessing step for high-dimensional data.

💡
Key Insight
The curse of dimensionality can render KNN ineffective by making all points equidistant, especially when irrelevant features are added.

Practice

(1/5)
1. In the context of Graph Neural Networks, which component is primarily responsible for aggregating information from neighboring nodes?
easy
A. Dropout layer
B. Activation function
C. Message passing mechanism
D. Batch normalization

Solution

  1. Step 1: Identify the role of each component

    The message passing mechanism is designed to aggregate information from neighboring nodes in a graph.

  2. Step 2: Eliminate wrong options

    Activation functions, dropout layers, and batch normalization do not specifically aggregate information from neighboring nodes.

  3. Final Answer:

    Option C -> Option C

  4. Quick Check:

    Message passing aggregates neighbor info in GNNs. [check]
Hint: Message passing aggregates neighbor info in GNNs. [check]
Common Mistakes:
2. 
from sklearn.ensemble import RandomForestClassifier
import numpy as np

X = np.array([[1, 2], [3, 4], [5, 6], [7, 8]])
y = np.array([0, 1, 0, 1])

model = RandomForestClassifier(n_estimators=1, max_features=1, bootstrap=False)
model.fit(X, y)

print(model.estimators_[0].tree_.feature)
What does this code output?
easy
A. [0, 1]
B. [1, 0]
C. [0]
D. [1]

Solution

  1. Step 1: Analyze the code

    The RandomForestClassifier is set with max_features=1, meaning each tree considers only one feature for splitting.

  2. Step 2: Determine the output

    Since bootstrap=False, the entire dataset is used, and the tree will choose one feature. The output shows the feature index used for splitting.

  3. Final Answer:

    Option C -> Option C

  4. Quick Check:

    max_features=1 limits to one feature. [OK]
Hint: max_features=1 limits to one feature. [OK]
Common Mistakes:
3. When should you prefer using LightGBM over XGBoost for a gradient boosting task?
medium
A. When you have a very large dataset with high dimensionality.
B. When you need better accuracy on small datasets.
C. When interpretability of the model is the primary concern.
D. When you require a model that handles categorical features natively.

Solution

  1. Step 1: Identify LightGBM's strengths

    LightGBM is optimized for speed and performance on large datasets with high dimensionality.

  2. Step 2: Eliminate wrong options

    When you need better accuracy on small datasets. is incorrect because XGBoost often performs better on small datasets. When interpretability of the model is the primary concern. is incorrect because neither LightGBM nor XGBoost is particularly interpretable. When you require a model that handles categorical features natively. is incorrect because both can handle categorical features, but LightGBM is faster on large datasets.

  3. Final Answer:

    Option A -> Option A

  4. Quick Check:

    LightGBM = Large, high-dimensional data [OK]
Hint: LightGBM = Large, high-dimensional data [OK]
Common Mistakes:
4. A fine-tuned model is underperforming on a specific task despite using a well-known pretrained model. What is a likely cause?
medium
A. The pretrained model's architecture is incompatible with the task.
B. The learning rate during fine-tuning was too high, causing overfitting.
C. The pretrained model was not trained on a large enough dataset.
D. The task-specific dataset is too small, leading to poor fine-tuning.

Solution

  1. Step 1: Identify common issues in fine-tuning.

    Small task-specific datasets can lead to poor adaptation of pretrained models.

  2. Step 2: Eliminate wrong options.

    The pretrained model was not trained on a large enough dataset. is incorrect because the pretrained model's dataset size is not the issue. The learning rate during fine-tuning was too high, causing overfitting. is incorrect because a high learning rate typically causes instability, not overfitting. The pretrained model's architecture is incompatible with the task. is incorrect because architecture incompatibility would prevent fine-tuning altogether.

  3. Final Answer:

    Option D -> Option D

  4. Quick Check:

    Small dataset? Poor fine-tuning. [check]
Hint: Small dataset? Poor fine-tuning. [check]
Common Mistakes:
5. In a real-time prediction system, how should you handle data splits to ensure both model performance and system efficiency?
hard
A. Use a single train-test split to minimize latency.
B. Use a static validation set to simplify the system.
C. Use a large test set to ensure model robustness.
D. Use a rolling window validation approach to adapt to new data.

Solution

  1. Step 1: Consider real-time constraints

    Real-time systems need to adapt to new data while maintaining performance.

  2. Step 2: Evaluate options for adaptability and efficiency

    Use a single train-test split to minimize latency. risks overfitting. Use a large test set to ensure model robustness. misallocates resources. Use a static validation set to simplify the system. lacks adaptability to new data.

  3. Final Answer:

    Option D -> Option D

  4. Quick Check:

    Rolling window adapts to new data efficiently. [OK]
Hint: Rolling window adapts to new data efficiently. [OK]
Common Mistakes:
Recommended

Ready to prove it?

Pass the test and this pattern moves unknown strong while earning +1 Grip toward your certificate.

10 questions~5 mineasy hard