KNN comparer

[turowicz]

@takuya-takeuchi I see that you are comparing with O(N^2) complexity, which is fine for 1-2 known people, but when you run into 1000s of known identities that will be way too slow. In python face_recognition it is recommended to use KNN classifier in order to find the best match. It's got way better performance for bigger datasets.

[turowicz]

Example: https://github.com/ageitgey/face_recognition/blob/master/examples/face_recognition_knn.py

[turowicz]

Looks like DlibDotNet needs this:

http://dlib.net/dlib/graph_utils/edge_list_graphs_abstract.h.html#find_k_nearest_neighbors http://dlib.net/dlib/graph_utils/find_k_nearest_neighbors_lsh.h.html

[turowicz]

@takuya-takeuchi do you think this is something that could be done easily? I might try myself but my need guidance from you. It's very important to get a GPU-backed KNN.

[takuya-takeuchi]

@turowicz It is very interesting. If using KNN on FaceRecognition, we must add find_k_nearest_neighbors to DlibDotNet. Or convert https://github.com/ageitgey/face_recognition/blob/master/examples/face_recognition_knn.py to C#. But it depends on sklearn and too difficult.

[takuya-takeuchi]

How to use find_k_nearest_neighbors http://dlib.net/dlib/test/linear_manifold_regularizer.cpp.html

[turowicz]

Yeah sklearn is impossible in C#. I'm talking to ML.NET guys but they also have no way of doing it. I think Dlib extern is the only way.

[takuya-takeuchi]

WIP But it requires time to implement.

[takuya-takeuchi]

NOTE1

How to train known encodings data? If there are 1 encoding data per pesson, need not to use knn. https://github.com/davisking/dlib/issues/1096

davisking said we should use knn or linear svm, but knn does not train method rather than linear svm.

NOTE2

Finished implementing find_k_nearest_neighbors. It could work fine. I must check it by using unit test like dlib\test\linear_manifold_regularizer.cpp

[turowicz]

@takuya-takeuchi thank you I will test at earliest convenience.

[turowicz]

@takuya-takeuchi can you point me to the class+method I should be calling?

[takuya-takeuchi]

Sorry. implement is done knn method on dlibdotnet. but test is not done and it should be enhanced to proper code for FaceRecognitionDotNet.

[turowicz]

Can you point me to the dlibdotnet class then? I can't find where you added the KNN....

[turowicz]

@takuya-takeuchi

[takuya-takeuchi]

I pushd classical Knn implementation. https://github.com/takuya-takeuchi/FaceRecognitionDotNet/tree/feature/knn

Does it satisfy your requirements?

I see that you are comparing with O(N^2) complexity Why? I think 1:N matching should consume O(N).

[turowicz]

Hey @takuya-takeuchi

Unfortunately it's not as good as: https://github.com/ageitgey/face_recognition/blob/master/examples/face_recognition_knn.py

The main difference is that they are using KNN model that has been trained and is able to produce results in less than O(N^2). It's possible they even accelerate it with GPU, but I'm not sure.

Your KNN implementation calculates distances for each element on each search, which is still O(N^2).

I will try to look for a better alternative.

[takuya-takeuchi]

using KNN model

Exactly. dlib function also looks like to not be able to output model data.

I will try to look for a better alternative.

I guess there is no way to achieve it except for porting sci-learn. It could difficult to port but not impossible. Fortunately, KNearestNeighbor class loos like to depend on only few classes. Needless to say, numpy is one of barrier for porting.

But Accord.NET looks goot to me. http://accord-framework.net/docs/html/T_Accord_MachineLearning_KNearestNeighbors_1.htm

It supports save and load model.

But I'm unwilling to depends on other library. The concept of FRDN is thin wrapper of face_recognition.

[turowicz]

No problem, thanks for your help!