### What
Stop showing search results once the vector distance dramatically incr…eases or decreases.
### Why
Avoid showing users search results that are unlikely to still be relevant. For example, if we ask a question like: “What is the capital of New York?” and we only have 2 articles about New York in our dataset -- and say several articles about other places -- it doesn’t provide any benefit to show these other articles.
Thus, autoCut provides a cleaner search experience for the user.
Further, as we introduce Cross Encoders and other inference-based re-ranking pipelines, saving these unneeded inferences will save costs by focusing computation where it’s needed.
### How
Implement autoCut as a post processing filter on the results of a nearText, nearVector, or nearObject search.
An added “autoCut” argument is set to be True or False depending on if the user wants to do this and can be accessed like this:
```graphql
{
Get {
Paragraph(
nearText: {
concepts: ["Italian food"]
}
autoCut: True
limit: 50
)
}
}
```
We envision 2 ways of implementing this in Weaviate, 1 of which is significantly more sophisticated than the other.
### Option 1 (easier way)
Simply set a maximum distance to stop showing results in the moduleConfig.
```python
"moduleConfig": {
"autoCut": "manual",
"threshold": 0.05
}
```
This can be implemented with a for loop that uses the index to look at the difference of i and i+1 in the distance result list.
### Option 2 (more sophisticated way)
```python
"moduleConfig": {
"autoCut": "auto",
}
```
Unfortunately, a simple distance threshold doesn’t capture the nuance of vector search. For example, we could have 3 results with vector distances 0.95, 0.85, 0.75 and then the 4th result at vector distance 0.2. Such a steep decrease may indicate that even the result with distance 0.75 is relevant to the query. Luckily, we have found a maximum curvature detection algorithm that can find “knee” points like the 0.2 distance presented above.
### Kneed Python Library Demo
This is inspired by the Kneed python library - https://pypi.org/project/kneed/. Here is a demonstration of it in action!
<img width="777" alt="Kneed Python demo" src="https://user-images.githubusercontent.com/25864937/197195841-e64909c5-4459-428f-9293-77bec23bc36f.png">
[More examples like this can be found here](https://github.com/semi-technologies/research/blob/main/auto-cut-off/Kneed_Demonstration_with_Real_Example.ipynb)
### Real Example - "What state is Providence located in?"
_The following example illustrates autoCut in action by asking “What state is Providence located in?” with a corpora of 3 Providence articles and 1 article about Kobe Bryant (which we do not want to show) – vectorized with SentenceTransformers all-miniLM-L6-v2:_
**Document 1** - Providence is the capital and most populous city of the U.S. state of Rhode Island. One of the oldest cities in New England, it was founded in 1636 by Roger Williams, a Reformed Baptist theologian and religious exile from the Massachusetts Bay Colony. He named the area in honor of "God's merciful Providence" which he believed was responsible for revealing such a haven for him and his followers. The city is situated at the mouth of the Providence River at the head of Narragansett Bay.
**Document 2** - As of the 2020 U.S. census, Providence has a population of 190,934, making it the third-most-populous city in New England after Boston and Worcester, Massachusetts.
**Document 3** - Around 1830, Providence had manufacturing industries in metals, machinery, textiles, jewelry, and silverware. Manufacturing has declined since, but the city is still one of the largest centers for jewelry and silverware design and manufacturing. Services also make up a large portion of the city's economy, in particular education, healthcare, and finance. Providence also is the site of a sectional center facility (SCF), a regional hub for the U.S. Postal Service.As the capital of Rhode Island, the city's economy additionally consists of government services, with approximately 70,000 jobs.
**Document 4** - Widely regarded as one of the greatest basketball players of all time,Bryant won five NBA championships, was an 18-time All-Star, a 15-time member of the All-NBA Team, a 12-time member of the All-Defensive Team, the 2008 NBA Most Valuable Player (MVP), and a two-time NBA Finals MVP. Bryant also led the NBA in scoring twice, and ranks fourth in league all-time regular season and postseason scoring. He was posthumously voted into the Naismith Memorial Basketball Hall of Fame in 2020 and named to the NBA 75th Anniversary Team in 2021.
Distances to the query **“What state is Providence located in?”** (dot products)
**Document 1** = 0.76
**Document 2** = 0.67
**Document 3** = 0.55
**Document 4** = -0.06
<img width="482" alt="Knee query demo" src="https://user-images.githubusercontent.com/25864937/197196303-3eea6620-ba65-442a-bbbc-e48f6a915e06.png">
### Kneed Implementation in Weaviate (Translation to Golang)
The complete python implementation can be found here - https://github.com/arvkevi/kneed/blob/master/kneed/knee_locator.py. All of the work happens in the constructor – calling helper methods also in this class. It works in 7 steps:
1. Fit a smooth line
The idea is to fit a line / function from the vector distances, i.e. the line that models [0.99, 0.98, 0.95, 0.89, 0.77, 0.76, …]. I think this is the hardest part of adding this to Weaviate because the library uses scipy.interp1d to form this line and I wasn’t able to quickly find an equivalent in golang. I suspect gonum can achieve this, but I’m not sure exactly how. Here is the documentation for scipy.interp1d – I think it uses Spline interpolation, but I do not yet understand exactly how that works: https://docs.scipy.org/doc/scipy/reference/generated/scipy.interpolate.interp1d.html.
2. Normalize values
```python
return (a - min(a)) / (max(a) - min(a))
```
3. Calculate the Difference Curve
This is another tricky part – we want to transform y to concave, increasing based on given direction and curve.
So first, we need to detect if the vector distance curve is convex or concave. These images show the distinction (the general idea is -- if you draw a line between any two points are there points above that line? (concave) or not (convex):
<img width="242" alt="Concave Convex 1D plots" src="https://user-images.githubusercontent.com/25864937/197196629-8e32263e-d0fe-4955-8b1f-410074d5f2fd.png">
We can determine if a function is concave or convex with the following equation:
<img width="819" alt="Concave Convex equation" src="https://user-images.githubusercontent.com/25864937/197196711-85c9cca4-838e-480d-8047-fdc0fdc606f2.png">
So I think we can use the interpolated function from earlier to apply this function to, I am also not exactly sure of this detail.
So depending on the curve, we transform it:
```python
def transform_y(y: Iterable[float], direction: str, curve: str) -> float:
"""transform y to concave, increasing based on given direction and curve"""
# convert elbows to knees
if direction == "decreasing":
if curve == "concave":
y = np.flip(y)
elif curve == "convex":
y = y.max() - y
elif direction == "increasing" and curve == "convex":
y = np.flip(y.max() - y)
return y
```
Numpy.flip - Reverse the order of elements in an array align the given axis: https://numpy.org/doc/stable/reference/generated/numpy.flip.html.
4. Identify local maxima/minima
The library uses scipy.signal.argrelextrema for this – I haven’t yet figured out exactly what this is doing either: https://docs.scipy.org/doc/scipy/reference/generated/scipy.signal.argrelextrema.html.
5. Calculate thresholds
This is where this S parameter comes into play – S: Sensitivity, original paper suggests default of 1.0 -- more from the paper "The sensitivity parameter allows us to adjust how aggressive we want Kneedle to be when detecting knees. Smaller values for S detect knees quicker, while larger values are more conservative. Put simply, S is a measure of how many “flat” points we expect to see in the unmodified data curve before declaring a knee."
6. Find Knee
7. Extract data about Knee
### Acknowledgements
Thank you to Laura Ham, Bob van Luijt, Etienne Dilocker, and Marcin Antas for help in developing this proposal!
- thanks