A Fast Optimization Method for General Binary Code Learning | JoVE Visualize

Area of Science:

Computer Science
Machine Learning
Information Retrieval

Background:

Hashing and binary code learning are crucial for efficient near neighbor search in retrieval, vision, and machine learning.
A key challenge in learning to hash is optimizing discrete variables, where continuous relaxation methods often suffer from quantization errors.
Existing methods using continuous relaxation for binary code optimization can lead to suboptimal performance due to accumulated quantization errors.

Purpose of the Study:

To propose a novel binary code optimization method, discrete proximal linearized minimization (DPLM), that directly addresses discrete constraints.
To develop an efficient algorithm for solving the nonsmooth nonconvex optimization problem arising in discrete hashing.
To demonstrate the flexibility of DPLM by supporting various loss functions and constraints, including supervised and unsupervised hashing.

Main Methods:

Reformulated the discrete optimization problem as minimizing the sum of a smooth loss and a nonsmooth indicator function.
Developed an iterative procedure that yields an analytical discrete solution at each step, ensuring fast convergence.
Instantiated the method with supervised and unsupervised hashing losses, incorporating bit uncorrelation and balance constraints.

Main Results:

The proposed DPLM method converges rapidly due to its iterative analytical discrete solutions.
DPLM successfully encoded the entire NUS-WIDE database into 64-bit binary codes in under 10 seconds on a standard computer.
Extensive evaluations on large-scale datasets show that DPLM-generated binary codes achieve highly competitive results in retrieval and classification tasks.

Conclusions:

DPLM offers an effective and efficient approach for binary code optimization in hashing by directly handling discrete variables.
The method's ability to minimize quantization error leads to superior performance in near neighbor search applications.
DPLM provides a versatile framework applicable to various hashing scenarios, demonstrating significant improvements in large-scale real-world datasets.