Max-Margin Invariant Features from Transformed Unlabeled Data
The study of representations invariant to common transformations of the data is important to learning. Most techniques have focused on local approximate invariance implemented within expensive optimization frameworks lacking explicit theoretical guarantees. In this paper, we study kernels that are invariant to a unitary group while having theoretical guarantees in addressing the important practical issue of unavailability of transformed versions of labelled data. A problem we call the Unlabeled Transformation Problem which is a special form of semisupervised learning and one-shot learning. We present a theoretically motivated alternate approach to the invariant kernel SVM based on which we propose MaxMargin Invariant Features (MMIF) to solve this problem. As an illustration, we design an framework for face recognition and demonstrate the efficacy of our approach on a large scale semi-synthetic dataset with 153,000 images and a new challenging protocol on Labelled Faces in the Wild (LFW) while out-performing strong baselines.
#### Paper summary
This paper considers the problem of learning invariant features for
classification under a special setting of the more general semi-supervised
learning; focusing on the face recognition problem. Given a set of unlabeled
points (faces), and a set of labeled points, the goal is to learn to construct
a feature map which is invariant to nuisance transformations (as observed
through the unlabeled set i.e., minor pose variations of the same unlabeled
subjects), while being discriminative to the inter-class transformations (as
observed through the labeled sample). The challenge in constructing such an
invariant feature map is that each face in the labeled set is not associated
with an explicit set of possible facial variations. Rather, these minor facial
variations (to be invariant to) are in the unlabeled set.
The paper addresses the problem by appealing to tools from group theory. Each
nuisance transformation is represented as a unitary transformation, and the
set of all nuisance transformations is treated as a unitary group (i.e., set of
orthogonal matrices). Key in constructing invariant features is the so called
"group integration" i.e., integral of all the orthogonal matrices in the group,
resulting in a symmetric projection matrix. This matrix is used to project
points to the invariant space. The paper gives a number of theoretical results
regarding this matrix, and extends it to reproducing kernel Hilbert spaces
(RKHSs). The invariant features, termed *max-margin invariant features* (MMIF),
of a point x are given by taking invariant inner products (induced by the
matrix) in an RKHS between x and a set of unlabeled points.
##### Review summary
The paper contributes a number of theorems regarding the group integration, as
well as invariance in the RKHS. While parts of these can be derived easily, the
end result of MMIFs which are provably invariant to nuisance transformations
is theoretically interesting. Some of these results appear to be new. Notations used
and writing in the paper are unfortunately unclear in many parts. The use of
overloaded notation severely hinders understanding (more comments below). A few
important aspects have not been addressed, including why the MMIFs are
constructed the way they are, and the assumption that "all" unitary
transformations need to be observed (more details below). Computational
complexity of the new approach is not given.
##### Major comments/questions
I find the MMIFs and the presented theoretical results very interesting.
However, there are still some unclear parts which I hope the authors can
address. In order of priority,
1. What is the relationship of the new invariant features to the mean embedding
features of Raj et al., 2017?
Local Group Invariant Representations via Orbit Embeddings
Raj et al., 2017
AISTATS 2017
2. The central part of the proposal is the group integration, integrating over
"all" orthogonal matrices. There is no mentioning at all how this is computed
until the very end on the last page (line 329), from which I infer that the
integration is replaced by an empirical average over all observed unlabeled
points. When the integration is not over all orthogonal matrices in the group,
all the given theorems do not hold. What can we say in this case? Also, how do
we know that the observed unlabeled samples are results of some orthogonal
transform? Line 160 does mention that "small changes in pose can be modeled as
unitary transformations" according to reference [8]. Could you please point out
where in [8]?
3. I understand how the proposed approach creates invariance to nuisance
transformations. What is unclear to me is the motivation of doing the
operations in Eq. (2) and line 284 to create features which are discriminative
for classification. Why are features constructed in this way a good choice for
being discriminative to between-class transformations? Related, at line 274,
the paper mentions about generating random binary label assignments for
training. Why random? There is not enough explanation in the text. Could
you please explain?
4. The size of the invariant feature map in the end is the same as the number
of classes (line 284). However, before obtaining this, an intermediate step in
Eq. (2) requires computing a feature vector of size M for each x (input point),
where M = number of distinct subjects in the unlabeled set. Presumably M must
be very large in practice. What is the runtime complexity of the full
algorithm?
5. In Theorem 2.4, the paper claims that the newly constructed transformation
g_H is a unitary transformation (preserving inner product) in the RKHS H.
However, it appears that only the range of feature map is considered in the
proof i.e., the set R := {x | \phi(x) for x in domain of X} and \phi is the
feature map associated with the kernel. In general, R is a subset (or equal) of
H. The proof of this theorem in the appendix is not complete unless it mentions
how to extend the results of the group transformation on R to H. 
6. I think Lemma 2.1 requires the group \mathcal{G} to have linear operation.
So, not "any" group as stated?
##### Suggestions on writing/notations
* \mathcal{X}, \mathcal{X}_\mathcal{G} are overloaded each with 2-3
definitions. See for example lines 119-125. This is very confusing.
* Line 280: K appears out of nowhere. I feel that it should be the number of
classes, which is denoted by N at line 269. But in the beginning N is used to
denote the cardinality of the labeled set...
* The paper should state from the beginning that the Haar measure in Lemma 2.1
will be replaced with an empirical measure as observed through the unlabeled
sample. It will help the reader.
* Line 155: I suggest that the term "generalization" be changed to something
else. As mentioned in the paper itself, the term does not have the usual
meaning.
* There are a few paragraphs that seem to appear out of context. These include
line 85, line 274, line 280 and line 284. Why should the paragraph at line 284
be there? I find it confusing. I feel that lines 311-323 should be in the
introduction.
------- after rebuttal ------
I read the authors' response. The authors partially addressed the issues that 
I raised. I have updated the score accordingly.