# How can one quickly look up people from a large database?

## Vocabulary

• Face detection: Finding all faces in an image.
• Face representation: The simplest way to represent a face is as an image (pixels / color values). This is not very space efficient and likely makes follow-up tasks hard. Face embeddings are one other representation. In this case a face is a point on the unit-sphere in $$\mathbb{R}^{128}$$, IIRC.
• Face verification: Given two face representations, deciding if they are the same

## Question

I was just wondering how identifying a person with many potential people can work. So finding a face in an image works quite well and fast enough for most applications. Face verification as well. But I'm not sure how to scale this if you don't compare 1 face against 1 other face, but 1 against millions / billions of faces.

Suppose you have a lot of examples of faces with the identity of the person. Think of Facebook, where many people tagged friends. Or of countries with biometric passports.

In the real applications, the face verification task is easy because you can just brute-force compare against all candidates:

• Facebook: Only candidates are your friends, so ~200 candidates.
• Airport EU fast entry: Your face is compared against the passport. So only one candidate.

But then think about some dystopian books / movies, where cameras identify anybody. While tracking helps to reduce that problem, finding a match from millions / billions of examples is computationally super heavy. Assuming a single face verification takes ~200ms, for a million candidates it would already take 60h. For a billion users it would already be 6 years. For all people on earth who currently live it is 48 years.

So with that many candidates, you don't want to compare against all candidates.

When you use the face-embedding, it becomes a nearest neighbor search in $$\mathbb{R}^{128}$$.

Calculating the euclidean distance of two vectors in $$\mathbb{R}^{128}$$ takes roughly 15μs (see "timing" below). This means a single check over $$7.5 \cdot 10^9$$ people would take 31h. Way better, but still pretty long.

While the face-embedding approach pre-computes a good face representation, going over all examples is still a pretty dumb approach. If it was only $$\mathbb{R}^1$$, one could make a simple binary tree. For few dimensions, I think something like a k-d-tree might work. But what about 128 dimensions?

Is there another approach to get the person quicker?

## Timing

import numpy as np
durations = timeit.repeat('np.linalg.norm(a-b)',
setup='import numpy as np;a=np.random.random(128);b=np.random.random(128)',
repeat=1000,
number=3)
print('min: {min:5.1f}μs, mean: {mean:5.1f}μs, max: {max:6.1f}μs'
.format(min=min(durations) * 10**6,
mean=np.mean(durations) * 10**6,
max=max(durations) * 10**6,
))
• Have you ever employed Siamese Network and triplet loss? There are already many models which are trained for large scale different faces. – Media Apr 19 '19 at 10:34
• I think you might have overlooked the link where I mention Face Embeddings. With 10^9 candidate identities, this is still pretty slow. – Martin Thoma Apr 19 '19 at 10:52
• Well, let's say that in another way. In such context where you need a quick look up, there should be a kind of trade-off between accuracy and speed. A possible solution can be using grouped convolutions and distributing the calculations to different computing units in order to increase the throughput. It can have good accuracy. I don't know whether you are familiar with distributed Tensorflow, but it is possible though the architecture would be changed drastically. – Media Apr 19 '19 at 11:04
• Are you suggesting to build a neural network with 10^9 classes? If not, please elaborate why you think grouped convolutions / Tensorflow would be of any help. – Martin Thoma Apr 19 '19 at 11:07
• Yes exactly, but in such cases that you are sure you have a lot of parameters, you can distribute your calculations in order to increase the number of calculations in a specified period of time. If you have enough computational power, say 10 GPUs, instead of stacking those one after another, you can simply do a subset of calculations on each and then gather them together. The insparation is exactly like AlexNet. It's a common approach for increasing throughput. – Media Apr 19 '19 at 11:14

## 1 Answer

You could do this progressively. For example, you could cluster embedding and try to classify ethnicity, gender and age.

Then you only need to search for people in that ethnicity, gender and age.

Similar procedures to reduce the search region. Just by gender, you already reduce your number of comparisons by half, age can help you separate it in (say you use 10 years) about 11 parts (which will be of different size, but still a nice improvement), you can reduce it further by separating by ethnicity.

### Demographics of the world (Wikipedia)

Age: According to the 2006 CIA World Factbook, around 27% of the world's population is below 15 years of age.

• 0–14 years: 26.3% (male 944,987,919/female 884,268,378)1
• 15–64 years: 65.9% (male 2,234,860,865/female 2,187,838,153)1
• 65 years and over: 7.9% (male 227,164,176/female 289,048,221) (2011 est.)1

Gender: This can be approximated by half/half distribution

Ethnicity: The largest ethnicity is Han (Sino-Tibetan -> Chinese) with 1.3 billions of members

So, for the worst case, with a 15-64 years world person, male or female, from Han ethnic group you have

$$1.3 \times 10^9 \times 0.5 \times 65.9\% = 428.35 \times 10^6 \text{ people}$$

Using your time estimate of $$15 \mu s$$ we have:

$$15 \times 10^{-6} \times 428.35 \times 10^6 = 1.78 \text{ hours}$$

The second worst case would be Arabs of the same age, which would take about $$37 \text{ minutes}$$ and for UK it would take about $$18 \text{ minutes}$$

This is still a slow procedure, but you can probably find clusters inside this large groups to reduce the search time even further.

I suppose it is viable to separate age 15-64 into at least 3 groups. If this can be done

• I appreciate the idea to cluster and discard some clusters completely. The problem with the discarding part is that you can't be sure about the cluster membership. A 64-year old can easily look like a 65 year old and some might look like 40 year olds. The problem is not that some people look older/younger, but that you can't clearly decide at the borders of the clusters. And once you make fuzzy clusters the computational advantage vanishes. – Martin Thoma Apr 19 '19 at 18:25
• That is true, that might give you a bit of accuracy tradeoff. The ideal approach would be to ignore our knowledge of humans and let a clustering algorithm divide human population into clusters. – Pedro Henrique Monforte Apr 19 '19 at 18:29
• Other thing that can be done, is to limit by known location, for example if someone is known to be highly likely to be in Asia you don't need to compare to someone in America, that could give us a nice reduction. Something else you need to put in mind is that this is a algorithm that is capable of recognizing humans better than humans itself, we are a race that is known for a face-processing capabilities and to overcome us in this cognitive ability by so much as to know every human in a country or in the world is just ... don't have a word for it hahaha – Pedro Henrique Monforte Apr 19 '19 at 18:34
• Also, by age division someone that looks like 40 and is 65 would be on the 40 cluster since his embedding must have 40-years-old-like-features, and age would only be update by recent photos. – Pedro Henrique Monforte Apr 19 '19 at 18:37