Large Margin Nearest Neighbours

Large margin nearest neighbours is a metric learning algorithm. It learns a metric that can be used with the K Nearest neighbours algorithm.

The Mahalanobis distance metric which is an instance of CCustomMahalanobisDistance is obtained as a result.

See [WS09] for a detailed introduction.

Example

Imagine we have files with training and test data. We create CDenseFeatures (here 64 bit floats aka RealFeatures) and CMulticlassLabels as

features_train = RealFeatures(f_feats_train)
features_test = RealFeatures(f_feats_test)
labels_train = MulticlassLabels(f_labels_train)
labels_test = MulticlassLabels(f_labels_test)
features_train = RealFeatures(f_feats_train);
features_test = RealFeatures(f_feats_test);
labels_train = MulticlassLabels(f_labels_train);
labels_test = MulticlassLabels(f_labels_test);
RealFeatures features_train = new RealFeatures(f_feats_train);
RealFeatures features_test = new RealFeatures(f_feats_test);
MulticlassLabels labels_train = new MulticlassLabels(f_labels_train);
MulticlassLabels labels_test = new MulticlassLabels(f_labels_test);
features_train = Modshogun::RealFeatures.new f_feats_train
features_test = Modshogun::RealFeatures.new f_feats_test
labels_train = Modshogun::MulticlassLabels.new f_labels_train
labels_test = Modshogun::MulticlassLabels.new f_labels_test
features_train <- RealFeatures(f_feats_train)
features_test <- RealFeatures(f_feats_test)
labels_train <- MulticlassLabels(f_labels_train)
labels_test <- MulticlassLabels(f_labels_test)
features_train = modshogun.RealFeatures(f_feats_train)
features_test = modshogun.RealFeatures(f_feats_test)
labels_train = modshogun.MulticlassLabels(f_labels_train)
labels_test = modshogun.MulticlassLabels(f_labels_test)
RealFeatures features_train = new RealFeatures(f_feats_train);
RealFeatures features_test = new RealFeatures(f_feats_test);
MulticlassLabels labels_train = new MulticlassLabels(f_labels_train);
MulticlassLabels labels_test = new MulticlassLabels(f_labels_test);
auto features_train = some<CDenseFeatures<float64_t>>(f_feats_train);
auto features_test = some<CDenseFeatures<float64_t>>(f_feats_test);
auto labels_train = some<CMulticlassLabels>(f_labels_train);
auto labels_test = some<CMulticlassLabels>(f_labels_test);

We create an instance of CLMNN and provide number of nearest neighbours as parameters.

k = 3
lmnn = LMNN(features_train, labels_train, k)
k = 3;
lmnn = LMNN(features_train, labels_train, k);
int k = 3;
LMNN lmnn = new LMNN(features_train, labels_train, k);
k = 3
lmnn = Modshogun::LMNN.new features_train, labels_train, k
k <- 3
lmnn <- LMNN(features_train, labels_train, k)
k = 3
lmnn = modshogun.LMNN(features_train, labels_train, k)
int k = 3;
LMNN lmnn = new LMNN(features_train, labels_train, k);
auto k = 3;
auto lmnn = some<CLMNN>(features_train, labels_train, k);

Next we train the LMNN algorithm and get the learned metric.

lmnn.train()
lmnn_distance = lmnn.get_distance()
lmnn.train();
lmnn_distance = lmnn.get_distance();
lmnn.train();
CustomMahalanobisDistance lmnn_distance = lmnn.get_distance();
lmnn.train 
lmnn_distance = lmnn.get_distance 
lmnn$train()
lmnn_distance <- lmnn$get_distance()
lmnn:train()
lmnn_distance = lmnn:get_distance()
lmnn.train();
CustomMahalanobisDistance lmnn_distance = lmnn.get_distance();
lmnn->train();
auto lmnn_distance = lmnn->get_distance();

Then we train the CKNN algorithm using the learned metric and apply it to test data, which here gives CMulticlassLabels.

knn = KNN(k, lmnn_distance, labels_train)
knn.train()
labels_predict = knn.apply_multiclass(features_test)
knn = KNN(k, lmnn_distance, labels_train);
knn.train();
labels_predict = knn.apply_multiclass(features_test);
KNN knn = new KNN(k, lmnn_distance, labels_train);
knn.train();
MulticlassLabels labels_predict = knn.apply_multiclass(features_test);
knn = Modshogun::KNN.new k, lmnn_distance, labels_train
knn.train 
labels_predict = knn.apply_multiclass features_test
knn <- KNN(k, lmnn_distance, labels_train)
knn$train()
labels_predict <- knn$apply_multiclass(features_test)
knn = modshogun.KNN(k, lmnn_distance, labels_train)
knn:train()
labels_predict = knn:apply_multiclass(features_test)
KNN knn = new KNN(k, lmnn_distance, labels_train);
knn.train();
MulticlassLabels labels_predict = knn.apply_multiclass(features_test);
auto knn = some<CKNN>(k, lmnn_distance, labels_train);
knn->train();
auto labels_predict = knn->apply_multiclass(features_test);

We can evaluate test performance via e.g. CMulticlassAccuracy.

acc = MulticlassAccuracy()
accuracy = acc.evaluate(labels_predict, labels_test)
acc = MulticlassAccuracy();
accuracy = acc.evaluate(labels_predict, labels_test);
MulticlassAccuracy acc = new MulticlassAccuracy();
double accuracy = acc.evaluate(labels_predict, labels_test);
acc = Modshogun::MulticlassAccuracy.new 
accuracy = acc.evaluate labels_predict, labels_test
acc <- MulticlassAccuracy()
accuracy <- acc$evaluate(labels_predict, labels_test)
acc = modshogun.MulticlassAccuracy()
accuracy = acc:evaluate(labels_predict, labels_test)
MulticlassAccuracy acc = new MulticlassAccuracy();
double accuracy = acc.evaluate(labels_predict, labels_test);
auto acc = some<CMulticlassAccuracy>();
auto accuracy = acc->evaluate(labels_predict, labels_test);

References

Wikipedia: Large_margin_nearest_neighbor

[WS09]KQ Weinberger and LK Saul. Distance metric learning for large margin nearest neighbor classification. Journal of Machine Learning Research, 10(Feb):207–244, 2009.