Equality constraint fails within `kmeans` #2

erhant · 2023-09-26T15:29:24Z

The culprit line is https://github.com/erhant/halo2-vectordb/blob/main/src/gadget/vectordb.rs#L246

If you comment that out and simply take distances as [one; K] it does not give an error.

The said error looks something like:

Equality constraint not satisfied by cell (Column('Advice', 0 - ), outside any region, on row 799)

Equality constraint not satisfied by cell (Column('Advice', 0 - ), outside any region, on row 801)

Equality constraint not satisfied by cell (Column('Advice', 0 - ), outside any region, on row 5753)

Equality constraint not satisfied by cell (Column('Advice', 0 - ), outside any region, on row 5756)

Equality constraint not satisfied by cell (Column('Advice', 8 - ), outside any region, on row 8152)

Equality constraint not satisfied by cell (Column('Advice', 8 - ), outside any region, on row 8154)

Equality constraint not satisfied by cell (Column('Advice', 9 - ), outside any region, on row 4924)

Equality constraint not satisfied by cell (Column('Advice', 9 - ), outside any region, on row 4927)

when you run the example code that uses kmeans,

The text was updated successfully, but these errors were encountered:

erhant · 2023-09-26T16:20:10Z

Within the vectordb gadget in kmeans function, we have the following statement:

            // assign each vector to closest centroid
            //
            // instead of assigning a cluster id to each vector,
            // we will store an indicator (one-hot encoding) for that cluster
            // suppose K = 4 and vectors A and B belong to 1, 3 respectively
            // we would have [1, 0, 0, 0] and [0, 0, 1, 0] as the indicators
            cluster_indicators = vectors
                .clone()
                .iter()
                .map(|v| {
                    // compute distance to centroids
                    let distances: [AssignedValue<F>; K] =
                        centroids.clone().map(|c| distance(ctx, &c, v));
                    // it works when i assign `[one; K];` instead

                    // find the minimum
                    let min: AssignedValue<F> = distances
                        .clone()
                        .into_iter()
                        .reduce(|min, d| self.fixed_point_gate.qmin(ctx, min, d))
                        .unwrap();

                    // return indicator
                    let indicators: [AssignedValue<F>; K] = distances.map(|d| {
                        // check if distance is the minimum
                        let eq = self.fixed_point_gate.gate().is_equal(ctx, min, d);

                        // return 1 if so, 0 otherwise
                        self.fixed_point_gate.gate().select(ctx, one, zero, eq)
                    });

                    indicators
                })
                .collect();

here, at the let distance = ... part if we simply do let distance = [one; K] where:

let one: AssignedValue<F> = ctx.load_constant(self.fixed_point_gate.quantization(1.0));

then we dont have the constraint error for some reason!

erhant · 2023-09-26T17:00:56Z

The bug is inside distance_chip.euclidean_distance; other distance functions work correctly.

erhant added the bug Something isn't working label Sep 26, 2023

erhant self-assigned this Sep 26, 2023

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

Uh oh!

Equality constraint fails within `kmeans` #2

Equality constraint fails within `kmeans` #2

Uh oh!

Uh oh!

Equality constraint fails within kmeans #2

Equality constraint fails within kmeans #2

Comments

Uh oh!

Uh oh!

Uh oh!

Equality constraint fails within `kmeans` #2

Equality constraint fails within `kmeans` #2