Cosine Similarity Formula

Plugins k-NN
1

Hi! I need help understanding how the CosineSimilarity is calculated.

For example: I created knn-index with parameters ‘knn’: True, ‘knn.space_type’: ‘cosinesimil’, ‘type’: ‘knn_vector’, ‘dimension’: 3 (as in example how to use knn). Then i added two vectors: [1, 2, 3] and [3, 4, 6]

Now I’m trying to compare [1, 2, 3] with vector [3, 4, 5]:
open-distro result: 0.22400923,
manually cosine = (13+24+3*5)/(sqrt(14)*sqrt(50)) = 0.9827076298239908

compare [3, 4, 6] with vector [3, 4, 5]:
open-distro result: 0.5,
manually cosine = (33+44+6*5)/(sqrt(61)*sqrt(50)) = 0.9958932064677039

how calculation works in open-distro? Maybe you can help me, please.
P.S. Sorry for my English

2 Likes
2

I’ve just signed up to ask similar question!

3

Hi @puzzled and @doc113, the issue is that the result is for the l2 space as opposed to the cosinesimil space for some reason.

Here is a note on scoring: GitHub - opendistro-for-elasticsearch/k-NN: 🆕 A machine learning plugin which supports an approximate k-NN search algorithm for Open Distro.

nmslib returns 1 - cosinesimilarity as the result. This is because, in their library, the lower score corresponds to a closer result. Intuitively, this makes sense because the nearest neighbors should have smallest distances between them. For the l2 space, they just return the l2 distance. In Elasticsearch, the higher the score indicates a better result. So, we return this score: 1/(1 + score_from_nmslib).

So, it appears that the distance function being used is L2 for your examples for some reason:

sqrt((1 - 3)^2 + (2-4)^2 + (3-5)^2) = 3.4641
1/(1 + 3.4641) = 0.224

I am not sure why l2 distance function is being used instead of cosinesimil. We had this issue that caused a similar problem: KNN graphs occasionally are indexed with wrong spaceType · Issue #239 · opendistro-for-elasticsearch/k-NN · GitHub. We backported the fixes to 1.8, 1.9, 1.10 branches, but the patched artifacts were never released. 1.11 artifacts should have the fix. Which version of ODFE are you using?

Jack

4

That’s true - it indeed returns the l2 score!
How can I know ODFE version out of managed elasticsearch service (via API / console) ?

5

These are the exact steps to reproduce, as appeared in the issue:

  1. Run docker
    docker run -p 9200:9200 -p 9600:9600 -e “discovery.type=single-node” amazon/opendistro-for-elasticsearch:1.11.0

  2. Create l2 space (l2 as default, implicit type)

  3. Delete index

  4. Create cosine space (explicit)

  5. Add data

  6. Query for it

==> Score is 1/(1+l2_dist) instead of using cosine

6

This is what I get when the problem reproduces:
Take a look specifically at

The setting “spaceType” was not set for the index. Likely caused by recent version upgrade. Setting the setting to the default value=l2
Caching issue? That’s after all one of the 2 hardest problems in CS :slight_smile:

The setting “M” was not set for the index. Likely caused by recent version upgrade. Setting the setting to the default value=16
The setting “efConstruction” was not set for the index. Likely caused by recent version upgrade. Setting the setting to the default value=512
creating index, cause [api], templates , shards [1]/[1]
The setting “M” was not set for the index. Likely caused by recent version upgrade. Setting the setting to the default value=16
The setting “efConstruction” was not set for the index. Likely caused by recent version upgrade. Setting the setting to the default value=512
deleting index
Cache evicted. Key /usr/share/elasticsearch/data/nodes/0/indices/o4xUzMUQRgeKh9KF9OmdXw/0/index/_0_206_my_vector1.hnswc, Reason: EXPLICIT
The setting “spaceType” was not set for the index. Likely caused by recent version upgrade. Setting the setting to the default value=l2
The setting “M” was not set for the index. Likely caused by recent version upgrade. Setting the setting to the default value=16
The setting “efConstruction” was not set for the index. Likely caused by recent version upgrade. Setting the setting to the default value=512
creating index, cause [api], templates , shards [1]/[1]
The setting “spaceType” was not set for the index. Likely caused by recent version upgrade. Setting the setting to the default value=l2
The setting “M” was not set for the index. Likely caused by recent version upgrade. Setting the setting to the default value=16
The setting “efConstruction” was not set for the index. Likely caused by recent version upgrade. Setting the setting to the default value=512
deleting index
The setting “M” was not set for the index. Likely caused by recent version upgrade. Setting the setting to the default value=16
The setting “efConstruction” was not set for the index. Likely caused by recent version upgrade. Setting the setting to the default value=512
creating index, cause [api], templates , shards [1]/[1]
The setting “M” was not set for the index. Likely caused by recent version upgrade. Setting the setting to the default value=16
The setting “efConstruction” was not set for the index. Likely caused by recent version upgrade. Setting the setting to the default value=512

7

THANKS!!! I installed 1.10.1 and it works!!

8

Hey, are you looking into the issue?
It’s sometimes reproducible in my side, sometimes not. I don’t think there’s a need to create l2 space for reproducing the error.
I’ve cycled thru the steps couple of time to reproduce (incl. restarting the 1.11 docker build and starting fresh)

9

Hi @puzzled, thanks for providing all of that information. We are looking into it. We will update this thread once we find out anything.

Jack

10

Hi @puzzled,

I am trying to reproduce the issue with the ODFE 1.11.0.0 Docker image. It appears some kind of race condition is causing the failure. I haven’t been able to reproduce yet after several attempts.

I wanted to check if our workflows for reproduction differed at all. I am using the Docker image amazon/opendistro-for-elasticsearch:1.11.0.

  1. Create cosine index
curl -X PUT "localhost:9200/cosine_1" -H 'Content-Type: application/json' -d'
{
  "settings" : {
    "number_of_shards" :   1,
    "number_of_replicas" : 0,
    "index": {
      "knn": true,
      "knn.space_type": "cosinesimil"
    }
  },
  "mappings": {
      "properties": {
        "my_vector": {
          "type": "knn_vector",
          "dimension": 3
        }
      }
  }
}
'
  1. Index a document
curl -X POST "localhost:9200/cosine_1/_doc" -H 'Content-Type: application/json' -d'
{
"my_vector":  [1, 2, 3]
}
'
  1. Run search
curl -X POST "localhost:9200/cosine_1/_search" -H 'Content-Type: application/json' -d'
{
  "size" : 1,
  "query": {
    "knn": {
      "my_vector": {
        "vector": [3, 4, 5],
        "k": 1
      }
    }
  }
}
'

Each time I run, I get 0.9830015:

{"took":45,"timed_out":false,"_shards":{"total":1,"successful":1,"skipped":0,"failed":0},"hits":{"total":{"value":1,"relation":"eq"},"max_score":0.9830015,"hits":[{"_index":"cosine_1","_type":"_doc","_id":"3V9tbHYBLuKlid1SXins","_score":0.9830015,"_source":
{
"my_vector":  [1, 2, 3]
}
}]}}

Is this how you are reproducing the issue?

11

Exactly!
At first I thought there’s a need for creating euclidean space first, but then was also able to reproduce without this step.

The loop that I’m doing for trying to reproduce includes restarting docker - and I think it’s an important step.

12

@puzzled Oh okay, thanks. So, your process is something like the following?

  1. Start ODFE 1.11 Docker container
  2. Create cosine index
  3. Index vector into index
  4. Search index
  5. Stop container
  6. Start container
  7. Delete cosine index
  8. Create cosine index
  9. Index vector into index
  10. Search index
    …
    If not, could you list the steps you are using to reproduce the issue? I am still unable to reproduce it.

Additionally, did you mention that you were also able to reproduce this issue with Amazon Elasticsearch Service? If so, which version were you using?

13

Yes, and I have a specific cluster in production where the problem replicates constantly.
I’m actually in a screen share with AWS support - want to join us?

ES version is 7.9.1

14

HI @puzzled,

So, I think I found potentially what is causing the error. I am still unable to create a cosine index that creates l2 graphs, but I was able to produce the following log message when cosine is set:

The setting “spaceType” was not set for the index. Likely caused by recent version upgrade. Setting the setting to the default value=l2

I noticed that in Elasticsearch <= 7.10, in the merge operation in ParametrizedFieldMapper, it passes empty index settings to the builder. When we are building the mapper, we try to read these settings.

Because the settings being passed in during merge are empty, this will lead to falling back to defaults.

The right solution in the long term is to switch these algorithm parameters to mapping parameters instead of index settings. We will fix that in an upcoming release. However, in the short term, I made a change to fix the problem without changing the index configuration.

Because I am still unable to reproduce the problem you are facing, I was wondering if you could test this code change with the Docker image you were able to produce the issue with. To do this, could you do the following steps?

# Build plugin with fix from source
git clone https://github.com/jmazanec15/k-NN.git
cd k-NN
git fetch
git checkout mapper-bug-fix-1.11
./gradlew build

# Create Docker image with fixed plugin
cat <<EOF >> Dockerfile
FROM amazon/opendistro-for-elasticsearch:1.11.0
RUN /usr/share/elasticsearch/bin/elasticsearch-plugin remove opendistro-knn -p
COPY --chown=elasticsearch:elasticsearch ./build/distributions/opendistro-knn-1.11.0.0.zip /tmp/
RUN /usr/share/elasticsearch/bin/elasticsearch-plugin install file:///tmp/opendistro-knn-1.11.0.0.zip --batch
EOF

docker build --tag=odfe-custom-plugin .

# Run container
docker run -p 9200:9200 -p 9600:9600 -e "discovery.type=single-node" odfe-custom-plugin

Please let me know if there is a problem with that workflow.

Note – before executing those steps, you will need to set JAVA_HOME, and have cmake, make, g++, git installed.

15

After handling few error in self compiling I stopped at a linking error between different java versions.
It happens although I run with

JAVA_HOME=/usr/lib/jvm/adoptopenjdk-11-hotspot-amd64 ./gradlew build

This is the error I get:

Error: LinkageError occurred while loading main class org.elasticsearch.gradle.reaper.Reaper
java.lang.UnsupportedClassVersionError: org/elasticsearch/gradle/reaper/Reaper has been compiled by a more recent version of the Java Runtime (class file version 58.0), this version of the Java Runtime only recognizes class file versions up to 55.0

I was trying to reproduce the problem locally, and couldn’t get to the same problem exactly, but was able to replicate a similar problem which seems to originate from same issue:

  • I was able to get “spaceType” not set in a cosine index
  • It happens on data insert time, and not on index creation
  • what happens is that I get no result at all, even though it should return at least one
16

@puzzled

Ah okay I think you need to use JDK 14. You can get this from here: Archived OpenJDK GA Releases.

Which version of software were you using when you were trying to reproduce locally?

17

Yes I realized I’m on wrong version but had to be off my computer for few hours.

I was using docker opendistro 1.11.0 …
One thing that may help reproduce the problem is drastically limiting CPU shares with

docker run --cpu-shares 256 -p 9200:9200 -p 9600:9600 -e “discovery.type=single-node” amazon/opendistro-for-elasticsearch:1.11.0

Or even lower values

I’m available now, pinged you thru the ticket at AWS support

18

Tracking here: KNNVectorFieldMapper unable to get algorithm params from settings when built from merge · Issue #288 · opendistro-for-elasticsearch/k-NN · GitHub