Nearest Neighbor

A method we worked on for useful purpose from very early on.     In our applications we never needed optimal,  just good, because there was too much else in the context that made measures inaccurate.

Good Algorithms Make Good Neighbors   By Erica Klarreich 
Communications of the ACM, July 2019, Vol. 62 No. 7, Pages 11-13    10.1145/3329712

A host of different tasks—such as identifying the song in a database most similar to your favorite song, or the drug most likely to interact with a given molecule—have the same basic problem at their core: finding the point in a dataset that is closest to a given point. This "nearest neighbor" problem shows up all over the place in machine learning, pattern recognition, and data analysis, as well as many other fields.

Yet the nearest neighbor problem is not really a single problem. Instead, it has as many different manifestations as there are different notions of what it means for data points to be similar. In recent decades, computer scientists have devised efficient nearest neighbor algorithms for a handful of different definitions of similarity: the ordinary Euclidean distance between points, and a few other distance measures.

However, "every time you needed to work with a new space or distance measure, you would kind of have to start from scratch" in designing a nearest neighbor algorithm, said Rasmus Pagh, a computer scientist at the IT University of Copenhagen. "Each space required some kind of craftsmanship."

Because distance measures are so varied, many computer scientists doubted these ad hoc methods would ever give way to a more general approach that could cover many different distance measures at once. Now, however, a team of five computer scientists has proven the doubters—who originally included themselves—were wrong.

In a pair of papers published last year (in the Proceedings of the ACM Symposium on Theory of Computing and the IEEE Annual Symposium on Foundations of Computer Science, respectively), the researchers set forth an efficient approximation algorithm for nearest neighbor search that covers a wide class of distance functions. Their algorithm finds, if not the very closest neighbor, then one that's almost as close, which is good enough for many applications.

The distance functions covered by the new algorithm, called norms, "encompass the majority of interesting distance functions," said Piotr Indyk, a computer scientist at the Massachusetts Institute of Technology.

The new algorithm is a big leap forward, Pagh said, who added, "I wouldn't have guessed such a general result was possible."   ..... " 

(Links to technical issues below)

Whats Best?

I like the pieces from Think with Google, good to follow.

We often addressed the problem when dealing with the term 'Optimal', which often followed with the question:  In what context?  under what Constraints?    When we use 'best' there are often many implied constraints in our search or request.  Its also common to include in conversation.  Search, Google's language of interaction, is a conversation, and includes common sense interpretations of 'Best'.

Ask a researcher: What does ‘best’ really mean?
Ken Wheaton August 2018 Mobile, Search, Consumer Insights

It seems fairly straightforward. When people set out to shop for an item or service, they hope to end up with the best possible outcome. But it turns out that “the best” isn’t an objective absolute. In fact, finding “the best” isn’t necessarily about finding the best thing that exists, it’s about finding the best thing for your needs.

It was pretty clear to us from consumer search data that people’s quest for the best is still on the rise. Mobile searches for “best” have grown over 80% over the past two years.1 And they’re searching for “best” for even the smallest stuff: We’ve seen strong growth in things like “best toothbrush” over the past couple years. ....  "

Considering the Correctness of AI

More from Cambridge University and the newly formed Leverhulme Centre for the Future of Intelligence (CFI):    Artificial intelligence: computer says YES (but is it right?)

My comments:

As long as we measure business results, and statistically measure results that are significantly better, we will be OK.   This is similar to the argument of better vs best.    Best, also called optimal,  almost always exists under some context that can be difficult to repeat, but assuring you get better can still provide real value.   All my experiences have dealt with this.

True there are scenarios where we want perfection,  correctness, optimal or best solutions.   But humans cannot always achieve that, and neither can AI.  So we add layers of checking, constraints, regulation and even ethics to both humans and machines to protect ourselves from this ultimate liability.   Which is why we further add risk understanding and analysis.  The integration with the use of smarter machines is no different.

(update)  And related, in Nature:  http://www.nature.com/news/there-is-a-blind-spot-in-ai-research-1.20805