Concrete ML
WebsiteLibrariesProducts & ServicesDevelopersSupport
1.5
1.5
  • Welcome
  • Getting Started
    • What is Concrete ML?
    • Installation
    • Key concepts
    • Inference in the cloud
  • Built-in Models
    • Linear models
    • Tree-based models
    • Neural networks
    • Nearest neighbors
    • Encrypted dataframe
    • Encrypted training
  • Deep Learning
    • Using Torch
    • Using ONNX
    • Step-by-step guide
    • Debugging models
    • Optimizing inference
  • Guides
    • Prediction with FHE
    • Production deployment
    • Hybrid models
    • Serialization
  • Tutorials
    • See all tutorials
    • Built-in model examples
    • Deep learning examples
  • References
    • API
    • Pandas support
  • Explanations
    • Quantization
    • Pruning
    • Compilation
    • Advanced features
    • Project architecture
      • Importing ONNX
      • Quantization tools
      • FHE Op-graph design
      • External libraries
  • Developers
    • Set up the project
    • Set up Docker
    • Documentation
    • Support and issues
    • Contributing
    • Support new ONNX node
    • Release note
    • Feature request
    • Bug report
Powered by GitBook

Libraries

  • TFHE-rs
  • Concrete
  • Concrete ML
  • fhEVM

Developers

  • Blog
  • Documentation
  • Github
  • FHE resources

Company

  • About
  • Introduction to FHE
  • Media
  • Careers
On this page
  • Example usage
  • Inference time considerations

Was this helpful?

Export as PDF
  1. Built-in Models

Nearest neighbors

PreviousNeural networksNextEncrypted dataframe

Last updated 1 year ago

Was this helpful?

Concrete ML offers nearest neighbors non-parametric classification models with a scikit-learn interface through the KNeighborsClassifier class.

Concrete ML
scikit-learn

Example usage

from concrete.ml.sklearn import KNeighborsClassifier

concrete_classifier = KNeighborsClassifier(n_bits=2, n_neighbors=3)

The KNeighborsClassifier class quantizes the training data-set that is given to .fit with the specified number of bits, n_bits. As this value must be kept low to comply with the accuracy of the model will depend heavily a well-chosen value n_bits and the dimensionality of the data.

The predict method of the KNeighborsClassifier performs the following steps:

  • quantization of the test vectors, performed in the clear

  • computation of the top-k class indices of the closest training set vector, on encrypted data

  • majority vote of the top-k class labels to find the class for each test vector, performed in the clear

Inference time considerations

The FHE inference latency of this model is heavily influenced by the n_bits, the dimensionality of the data. Furthermore, the size of the data-set has a linear impact on the complexity of the data and the number of nearest neighbors, n_neighbors, also plays a role.

The KNN computation executes in FHE in O(Nlog2k)O(Nlog^2k)O(Nlog2k) steps, where NNN is the training data-set size and kkk is n_neighbors. Each step requires several PBS, but the run-time of each of these PBS is influenced by the factors listed above. These factors combine to give the precision required to represent the distances between test vectors and the training data-set vectors. The PBS input precision required by the circuit is related to the one of the distance values.

KNeighborsClassifier
KNeighborsClassifier
accumulator size constraints