Multiview Hessian Regularization for Image Annotation

Weifeng Liu; Dacheng Tao

Source-linked AI summary

Multiview Hessian Regularization for Image Annotation

Weifeng Liu, Dacheng Tao

arXiv:1904.10100v1Apr 23, 2019cs.LGcs.CVstat.ML

TL;DR

The paper addresses limited extrapolation in Laplacian regularization and the inability of conventional methods to handle multiview image features. It proposes mHR, which combines view-specific Hessian regularizations and applies them to kernel least squares and support vector machines. Experiments on PASCAL VOC’07 report that mHR outperforms other multiview methods and is especially effective with few labeled images.

Problem
Laplacian regularization can bias classification toward a constant function, while conventional methods often handle only single-view features despite images having multiple views.
Method
mHR optimally combines Hessian regularizations obtained from different views and steers the classification function to vary linearly along the data manifold.
Results
mHR outperforms other multiview methods on PASCAL VOC’07 and significantly boosts performance, especially when labeled images are scarce.
Takeaways & Limitations
mHR combines complementary multiview information with Hessian regularization for image annotation in kernel least squares and support vector machines.

Abstract

from arXiv · show

The rapid development of computer hardware and Internet technology makes large scale data dependent models computationally tractable, and opens a bright avenue for annotating images through innovative machine learning algorithms. Semi-supervised learning (SSL) has consequently received intensive attention in recent years and has been successfully deployed in image annotation. One representative work in SSL is Laplacian regularization (LR), which smoothes the conditional distribution for classification along the manifold encoded in the graph Laplacian, however, it has been observed that LR biases the classification function towards a constant function which possibly results in poor generalization. In addition, LR is developed to handle uniformly distributed data (or single view data), although instances or objects, such as images and videos, are usually represented by multiview features, such as color, shape and texture. In this paper, we present multiview Hessian regularization (mHR) to address the above two problems in LR-based image annotation. In particular, mHR optimally combines multiple Hessian regularizations, each of which is obtained from a particular view of instances, and steers the classification function which varies linearly along the data manifold. We apply mHR to kernel least squares and support vector machines as two examples for image annotation. Extensive experiments on the PASCAL VOC'07 dataset validate the effectiveness of mHR by comparing it with baseline algorithms, including LR and HR.

I. INTRODUCTION

The paper motivates image annotation with semi-supervised learning while identifying limitations in Laplacian regularization and single-view methods. It proposes mHR to combine multiview information with Hessian regularization for improved annotation.

Large-scale image annotation is important because millions or billions of images are accessible, while obtaining enough labels is expensive.
Laplacian regularization biases classification toward a constant function, limiting extrapolation beyond training outputs, especially with few labeled examples.
Hessian regularization drives functions that vary linearly along the manifold and can predict points beyond the training-domain boundary.
Image annotation naturally uses complementary color, shape, and texture views, but feature concatenation can mishandle their physical differences and overfit.
mHR combines Hessian regularizations from multiple views and is implemented with kernel least squares and support vector machines.

III. MHR: MULTIVIEW HESSIAN REGULARIZATION

mHR constructs a Hessian regularization for each feature view and uses it to encode local manifold geometry. Its multiview formulation combines complementary views while favoring classification functions that vary linearly along the manifold.

MHR: MULTIVIEW HESSIAN REGULARIZATION: mSSL assumes examples lie on a compact manifold whose conditional label distribution varies smoothly along intrinsic geodesics.
MHR: MULTIVIEW HESSIAN REGULARIZATION: mHR contains one Hessian regularization H_k(f) per view, computed from second-order derivatives with respect to that view’s features.
MHR: MULTIVIEW HESSIAN REGULARIZATION: The method uses the Frobenius norm of each view’s Hessian as a manifold-invariant regularizer related to thin-plate splines.
MHR: MULTIVIEW HESSIAN REGULARIZATION: For each view, the construction finds nearest neighbors, estimates tangent coordinates by singular value decomposition, and orthonormalizes linear and quadratic terms.
MHR: MULTIVIEW HESSIAN REGULARIZATION: Summed local matrices produce H_k(f), with regularization f^T H_k f for view k and f containing predictions on labeled and unlabeled examples.
MHR: MULTIVIEW HESSIAN REGULARIZATION: Compared with LR, mHR uses richer Hessian nullspaces and complementary multiview features to better exploit the marginal-distribution geometry.

A. The General Framework

The general framework integrates multiple kernel learning and Hessian regularization across views. It learns combination coefficients that determine how view-specific kernels and Hessians contribute to the model.

The General Framework: The multiview framework integrates multiple kernel learning with ensemble graph learning.
The General Framework: It constructs a new valid kernel from valid kernels defined on individual views.
The General Framework: The framework approximates manifold geometry using a convex hull of Hessians from different views and defines mHR from that combination.
The General Framework: The coefficient penalties discourage overfitting to only one view kernel or manifold, while γ_θ and γ_β control regularization contributions.
The General Framework: For fixed θ and β, the objective reduces to the single-kernel formulation with K equal to a weighted sum of view-specific Hessians.
The General Framework: The optimization alternates between learning the classifier and the kernel and Hessian combination coefficients.

B. Representer Theorem and Convergence Analysis

The paper establishes a representer form for the mHR solution and analyzes an alternating optimization procedure. For convex loss, the procedure converges to a local minimum through a monotonically decreasing objective sequence.

B. Representer Theorem and Convergence Analysis: The representer theorem section establishes lemmas for the mHR solution and its alternating optimization convergence.
B. Representer Theorem and Convergence Analysis: The minimizer of the base optimization problem admits an expansion in terms of labeled and unlabeled examples.
B. Representer Theorem and Convergence Analysis: The combined kernel is valid, and the combined Hessian is positive semidefinite.
B. Representer Theorem and Convergence Analysis: With fixed β and θ, the mHR solution has a representer expansion, while the algorithm alternates updates for α, θ, and β until convergence.
B. Representer Theorem and Convergence Analysis: A convex loss yields a monotonically decreasing sequence under alternating optimization that converges to a local minimum.
B. Representer Theorem and Convergence Analysis: The objective is not jointly convex in f, θ, and β, so uniform coefficient initialization empirically produces a satisfactory solution.

IV. EXAMPLE ALGORITHMS

The paper instantiates mHR in kernel least squares and SVM by combining view-specific Hessian regularizations with task-specific loss functions and optimization procedures.

mHR supports general loss functions and is demonstrated through kernel least squares and support vector machines.
mHR support vector machines (mHR-SVM): mHR-SVM uses hinge loss and incorporates Hessian-based regularization into the SVM objective.
mHR support vector machines (mHR-SVM): The mHR-SVM hinge-loss objective is solved by smoothing the loss and applying Nesterov’s optimal gradient method.
mHR support vector machines (mHR-SVM): For fixed coefficients, the method alternates optimization over view weights and regularization variables.

B. mHR kernel least squares (mHR-KLS)

The mHR-KLS formulation uses squared loss and combines view-specific Hessian matrices through weighted regularization, with alternating optimization for the model parameters.

Regularized kernel least squares uses squared loss, and introducing mHR yields the mHR-KLS formulation.
The combined Hessian regularizer is formed from view-specific matrices H_j weighted by β_j.
The KLS solution is obtained by setting derivatives with respect to α to zero and solving the resulting system.
The method alternates updates of θ and β, initialized uniformly and optimized with coordinate descent toward a local optimum.

V. EXPERIMENTS

Experiments evaluate mHR-based annotation on PASCAL VOC’07 using multiple visual features, varying labeled-data proportions, and AP/mAP-based comparisons with several baselines.

PASCAL VOC’07 contains 9,963 images across 20 visual object classes, with 5,011 training images and 4,952 test images.
The experiments use 15 visual features spanning GIST, color, SIFT, Harris, and combined Harris+SIFT representations.
The study compares mHR-SVM and mHR-KLS with SVM, LapSVM, KLS, LapKLS, Hessian-regularized methods, feature concatenation, and average-kernel methods.
Performance is measured using per-class average precision and mean average precision computed with the PASCAL VOC method.

A. Effectiveness of HR

The effectiveness study compares Hessian- and Laplacian-regularized SVM variants across visual features and finds advantages for Hessian and multiview regularization.

HR performs better than LR in most cases on the mAP comparison using 2,250 labeled images.
Multiview methods are significantly better than single-view methods, while mHR outperforms the other multiview methods.

B. Performance of mHR

The experiments evaluate mHR against feature concatenation, average kernels, LR-based methods, and other multiview approaches using AP and mAP. Across selected classes and labeled-sample settings, mHR performs especially well with few labels and outperforms other multiview methods in both implementations.

B. Performance of mHR: The evaluation compares AP across selected visual object classes and mAP across all classes for different multiview methods.Figure 3 covers boat, bottle, car, cow, dog, horse, person, and potted plant; Figure 4 summarizes different labeled-image counts.
B. Performance of mHR: mHR significantly boosts performance on selected classes, especially when the number of labeled images is small.The AP plots use the number of labeled images as the x-coordinate.
B. Performance of mHR: In the mAP comparison, mHR outperforms the other multiview methods in both SVM and kernel least squares implementations.The comparison includes feature concatenation and average kernel methods.
B. Performance of mHR: Average kernels outperform feature concatenation in SVM, whereas feature concatenation outperforms average kernels in kernel least squares.These relationships differ by implementation.
B. Performance of mHR: The paper concludes that mHR significantly outperforms LR-based and other related algorithms on PASCAL VOC’07.The method is applied to kernel least squares and support vector machines.

APPENDIX A PROOF OF LEMMA 1

The proof of Lemma 1 shows that an optimization minimizer can be represented in the finite-dimensional span of kernel evaluations on labeled and unlabeled examples. The multiview kernel and Hessian constructions preserve valid-kernel and positive-semidefinite properties.

APPENDIX A PROOF OF LEMMA 1: Any function in the reproducing-kernel Hilbert space decomposes into components in the kernel span and its orthogonal complement.The span is generated by kernels evaluated at the labeled and unlabeled examples.
APPENDIX A PROOF OF LEMMA 1: The orthogonal component increases the norm without changing function values on the training examples, so the minimizer lies in the kernel span.The loss depends only on the function values at the examples, while the norm penalty is monotonically increasing.
APPENDIX A PROOF OF LEMMA 1: A weighted combination of valid view-specific kernels remains a valid kernel because it can be represented as an inner product.The construction uses nonnegative view weights.
APPENDIX A PROOF OF LEMMA 1: The combined Hessian matrix is a convex combination of view-specific Hessian energies.For nonnegative weights, the resulting Hessian matrix is positive semidefinite.
APPENDIX A PROOF OF LEMMA 1: The view-specific Hessian energy is based on the Frobenius norm of the Hessian of the learned function at each example.This connects the matrix construction to local curvature of the function.

APPENDIX D PROOF OF THEOREM 1

Theorem 1’s proof analyzes mHR by alternating optimization over the learned function, kernel weights, and Hessian weights. Each block update does not increase the objective, so the objective consistently decreases across iterations.

APPENDIX D PROOF OF THEOREM 1: At each iteration, optimizing the learned function reduces the objective because the loss function is convex.With the other variables fixed, the subproblem degenerates to the earlier convex optimization problem.
APPENDIX D PROOF OF THEOREM 1: The objective function consistently decreases over the alternating updates.This monotonic decrease completes the proof of Theorem 2 as stated in the supplied passage.
APPENDIX D PROOF OF THEOREM 1: Optimizing the kernel weights through the quadratic program also cannot increase the objective when the relevant matrix is positive semidefinite.The proof compares the objective before and after the kernel-weight update.
APPENDIX D PROOF OF THEOREM 1: The proof relies on the positive-semidefinite condition for the matrix used in the kernel-weight subproblem.Under that condition, the subproblem is a quadratic program.
APPENDIX D PROOF OF THEOREM 1: The Hessian-weight update is obtained by minimizing the objective with respect to the Hessian weights while the other variables remain fixed.This is the third block in the alternating optimization procedure.