s2fieldsofstudy:
Computer Science
Philosophy

text:
Logical Inference on Dependency-based Compositional Semantics

Dependency-based Compositional Semantics (DCS) is a framework of natural language semantics with easy-to-process structures as well as strict semantics. In this paper, we equip the DCS framework with logical inference, by defining abstract denotations as an abstraction of the computing process of denotations in original DCS. An inference engine is built to achieve inference on abstract denotations. Furthermore, we propose a way to generate on-the-fly knowledge in logical inference, by combining our framework with the idea of tree transformation. Experiments on FraCaS and PASCAL RTE datasets show promising results.

Introduction
Dependency-based Compositional Semantics (DCS) provides an intuitive way to model semantics of questions, by using simple dependency-like trees (Liang et al., 2011). It is expressive enough to represent complex natural language queries on a relational database, yet simple enough to be latently learned from question-answer pairs. In this paper, we equip DCS with logical inference, which, in one point of view, is "the best way of testing an NLP system's semantic capacity" (Cooper et al., 1996).
It should be noted that, however, a framework primarily designed for question answering is not readily suited for logical inference. Because, answers returned by a query depend on the specific database, but implication is independent of any databases. For example, answers to the question "What books are read by students?", should always be a subset of answers to "What books are ever read by anyone?", no matter how we store the data of students and how many records of books are there in our database.
Thus, our first step is to fix a notation which abstracts the calculation process of DCS trees, so as to clarify its meaning without the aid of any existing database. The idea is to borrow a minimal set of operators from relational algebra (Codd, 1970), which is already able to formulate the calculation in DCS and define abstract denotation, which is an abstraction of the computation of denotations guided by DCS trees. Meanings of sentences then can be represented by primary relations among abstract denotations. This formulation keeps the simpleness and computability of DCS trees mostly unaffected; for example, our semantic calculation for DCS trees is parallel to the denotation computation in original DCS.
An inference engine is built to handle inference on abstract denotations. Moreover, to compensate the lack of background knowledge in practical inference, we combine our framework with the idea of tree transformation (Bar-Haim et al., 2007), to propose a way of generating knowledge in logical representation from entailment rules (Szpektor et al., 2007), which are by now typically considered as syntactic rewriting rules. We test our system on FraCaS (Cooper et al., 1996) and PASCAL RTE datasets (Dagan et al., 2006). The experiments show: (i) a competitive performance on FraCaS dataset; (ii) a big impact of our automatically generated on-the-fly knowledge in achieving high recall for a logicbased RTE system; and (iii) a result that outperforms state-of-the-art RTE system on RTE5 data. Our whole system is publicly released and can be downloaded from http://kmcs.nii.ac. jp/tianran/tifmo/.

The Idea
In this section we describe the idea of representing natural language semantics by DCS trees, and achieving inference by computing logical relations among the corresponding abstract denotations.  DCS trees has been proposed to represent natural language semantics with a structure similar to dependency trees (Liang et al., 2011) (Figure 1). For the sentence "students read books", imagine a database consists of three tables, namely, a set of students, a set of books, and a set of "reading" events ( Table 1). The DCS tree in Figure 1 is interpreted as a command for querying these tables, obtaining "reading" entries whose "SUBJ" field is student and whose "OBJ" field is book. The result is a set {John reads Ulysses, . . .}, which is called a denotation. DCS trees can be extended to represent linguistic phenomena such as quantification and coreference, with additional markers introducing additional operations on tables. Figure 2 shows an example with a quantifier "every", which is marked as "⊂" on the edge (love)OBJ-ARG(dog) and interpreted as a division operator q OBJ ⊂ ( §2.2). Optimistically, we believe DCS can provide a framework of semantic representation with sufficiently wide coverage for real-world texts.
The strict semantics of DCS trees brings us the idea of applying DCS to logical inference. This is not trivial, however, because DCS works under the assumption that databases are explicitly available. Obviously this is unrealistic for logical inference on unrestricted texts, because we cannot prepare a database for everything in the world. This fact fairly restricts the applicable tasks of DCS.
Our solution is to redefine DCS trees without the aid of any databases, by considering each node of a DCS tree as a content word in a sentence (but may no longer be a table in a specific database), while each edge represents semantic relations between two words. The labels on both ends of an edge, such as SUBJ (subject) and OBJ (object), are considered as semantic roles of the cor-  Figure 2: DCS trees of "Mary loves every dog" (Left-Up), "Tom has a dog" (Left-Down), and "Tom has an animal that Mary loves" (Right).
responding words 1 . To formulate the database querying process defined by a DCS tree, we provide formal semantics to DCS trees by employing relational algebra (Codd, 1970) for representing the query. As described below, we represent meanings of sentences with abstract denotations, and logical relations among sentences are computed as relations among their abstract denotations. In this way, we can perform inference over formulas of relational algebra, without computing database entries explicitly.

Abstract denotations
Abstract denotations are formulas constructed from a minimal set of relational algebra (Codd, 1970) operators, which is already able to formulate the database queries defined by DCS trees. For example, the semantics of "students read books" is given by the abstract denotation: where read, student and book denote sets represented by these words respectively, and w r represents the set w considered as the domain of the semantic role r (e.g. book OBJ is the set of books considered as objects). The operators ∩ and × represent intersection and Cartesian product respectively, both borrowed from relational algebra. It is not hard to see the abstract denotation denotes the intersection of the "reading" set (as illustrated by the "read" table in Table 1) with the product of "student" set and "book" set, which results in the same denotation as computed by the DCS tree in Figure 1, i.e. {John reads Ulysses, . . .}. However, the point is that F 1 itself is an algebraic formula that does not depend on any concrete databases.
Formally, we introduce the following constants: • W : a universal set containing all entities.  In addition we introduce following functions: • ×: the Cartesian product of two sets.
• ∩: the intersection of two sets.
Generally we admit projections onto multiple semantics roles, denoted by π R where R is a set of semantic roles.
• q r ⊂ : the division operator, where q r ⊂ (A, B) is defined as the largest set X which satisfies B r × X ⊂ A. 2 This is used to formulate universal quantifiers, such as "Mary loves every dog" and "books read by all students".
An abstract denotation is then defined as finite applications of functions on either constants or other abstract denotations.

Statements
As the semantics of DCS trees is formulated by abstract denotations, the meanings of declarative sentences are represented by statements on abstract denotations. Statements are declarations of some relations among abstract denotations, for which we consider the following set relations: Roughly speaking, the relations correspond to the logical concepts satisfiability and entailment.

Logical inference on DCS
Based on abstract denotations, we briefly describe our process to apply DCS to textual inference.

Natural language to DCS trees
To obtain DCS trees from natural language, we use Stanford CoreNLP 5 for dependency parsing (Socher et al., 2013), and convert Stanford dependencies to DCS trees by pattern matching on POS tags and dependency labels. 6 Currently we use the following semantic roles: ARG, SUBJ, OBJ, IOBJ, TIME and MOD. The semantic role MOD is used for any restrictive modifiers. Determiners such as "all", "every" and "each" trigger quantifiers, as shown in Figure 2.

DCS trees to statements
Here σ is the node nearer to the root. Furthermore, for each edge (σ, σ ) we can optionally assign a quantification marker.
Abstract denotation of a DCS tree can be calculated in a bottom-up manner. For example, the abstract denotation of H in Figure 2 is calculated from the leaf node Mary, and then: Node love (Mary loves): F 2 = love ∩ (Mary SUBJ × W OBJ ) Node animal (Animal that Mary loves): F 3 = animal ∩ π OBJ (F 2 ) Node have (Tom has an animal that Mary loves): Formally, suppose the root σ of a DCS tree T has children τ 1 , . . . , τ n , and edges (σ, τ 1 ), . . . , (σ, τ n ) labeled by (r 1 , r 1 ), . . . , (r n , r n ), respectively. The abstract denotation of T is defined as: 4 Negation and disjointness (" ") are explained in §2.5. 5 http://nlp.stanford.edu/software/ corenlp.shtml 6 In (Liang et al., 2011) DCS trees are learned from QA pairs and database entries. We obtain DCS trees from dependency trees, to bypass the need of a concrete database. 7 The definition differs slightly from the original Liang et al. (2011), mainly for the sake of simplicity and clarity. Figure 3: An example of proof using abstract denotations Table 3: An excerpt of axioms where T τ i is the subtree of T rooted at τ i , and R σ is the set of possible semantic roles for content word w(σ) (e.g. When universal quantifiers are involved, we need to add division operators to the formula. If (σ, τ i ) is assigned by a quantification marker "⊂" 8 , then the abstract denotation is 9 where T is the same tree as T except that the edge (σ, τ i ) is removed. For example, the abstract denotation of the first sentence of T in Figure 2 (Mary loves every dog) is calculated from F 2 (Mary loves) as After the abstract denotation [[T ]] is calculated, the statement representing the meaning of the sentence is defined as [[T ]] = ∅. For example, the statement of "students read books" is read ∩ (student SUBJ × book OBJ ) = ∅, and the statement of "Mary loves every dog" is q OBJ ⊂ (π OBJ (F 2 ), dog) = ∅, which is logically equivalent to dog ⊂ π OBJ (F 2 ). 10

Logical inference
Since meanings of sentences are represented by statements on abstract denotations, logical inference among sentences is reduced to deriving new relations among abstract denotations. This is done by applying axioms to known statements, and approximately 30 axioms are implemented (Table 3). 8 Multiple quantifiers can be processed similarly. 9 The result of [[T ]] depends on the order of the children τ1, . . . , τn. Different orders correspond to readings of different quantifier scopes.
These are algebraic properties of abstract denotations, among which we choose a set of axioms that can be handled efficiently and enable most common types of inference seen in natural language. For the example in Figure 2, by constructing the following abstract denotations: Tom has a dog: we can use the lexical knowledge dog ⊂ animal, the statements of T (i.e. dog ⊂ π OBJ (F 2 ) and F 6 = ∅), and the axioms in Table 3, 11 to prove the statement of H (i.e. F 4 = ∅) (Figure 3). We built an inference engine to perform logical inference on abstract denotations as above. In this logical system, we treat abstract denotations as terms and statements as atomic sentences, which are far more easier to handle than first order predicate logic (FOL) formulas. Furthermore, all implemented axioms are horn clauses, hence we can employ forward-chaining, which is very efficient.

Extensions
Further extensions of our framework are made to deal with additional linguistic phenomena, as briefly explained below.
Negation To deal with negation in our forwardchaining inference engine, we introduce one more relation on abstract denotations, namely disjointness A B, meaning that A and B are disjoint sets. Using disjointness we implemented two types of negations: (i) atomic negation, for each content word w we allow negationw of that word, characterized by the property w w; and (ii) root negation, for a DCS tree T and its denotation [[T ]], the negation of T is represented by T T , meaning that T = ∅ in its effect.
Selection Selection operators in relational algebra select a subset from a set to satisfy some spe-cific properties. This can be employed to represent linguistic phenomena such as downward monotonicity and generalized quantifiers. In the current system, we implement (i) superlatives, e.g. s highest (mountain ∩ (W ARG × Asia MOD )) (the highest mountain in Asia) and (ii) numerics, e.g. s two (pet ∩ fish) (two pet fish), where s f is a selection marker. Selection operators are implemented as markers assigned to abstract denotations, with specially designed axioms. For example superlatives satisfy the following property: . New rules can be added if necessary.
Coreference We use Stanford CoreNLP to resolve coreferences (Raghunathan et al., 2010), whereas coreference is implemented as a special type of selection. If a node σ in a DCS tree T belongs to a mention cluster m, we take the abstract denotation [[T σ ]] and make a selection s m ([[T σ ]]), which is regarded as the abstract denotation of that mention. Then all selections of the same mention cluster are declared to be equal.

Generating On-the-fly Knowledge
Recognizing textual entailment (RTE) is the task of determining whether a given textual statement H can be inferred by a text passage T. For this, our primary textual inference system operates as: 1. For a T-H pair, apply dependency parsing and coreference resolution.
2. Perform rule-based conversion from dependency parses to DCS trees, which are translated to statements on abstract denotations.
3. Use statements of T and linguistic knowledge as premises, and try to prove statements of H by our inference engine.
However, this method does not work for realworld datasets such as PASCAL RTE (Dagan et al., 2006), because of the knowledge bottleneck: it is often the case that the lack of sufficient linguistic knowledge causes failure of inference, thus the system outputs "no entailment" for almost all pairs (Bos and Markert, 2005).
The transparent syntax-to-semantics interface of DCS enables us to back off to NLP techniques during inference for catching up the lack of knowledge. We extract fragments of DCS trees as paraphrase candidates, translate them back to linguis-  Figure 4: RTE system tic expressions, and apply distributional similarity to judge their validity. In this way, our framework combines distributional and logical semantics, which is also the main subject of Lewis and Steedman (2013) and Beltagy et al. (2013).
As follows, our full system (Figure 4) additionally invokes linguistic knowledge on-the-fly: 4. If H is not proven, compare DCS trees of T and H, and generate path alignments.
5. Aligned paths are evaluated by a similarity score to estimate their likelihood of being paraphrases. Path alignments with scores higher than a threshold are accepted.
6. Convert accepted path alignments into statements on abstract denotations, use them in logical inference as new knowledge, and try to prove H again.

Generating path alignments
On-the-fly knowledge is generated by aligning paths in DCS trees. A path is considered as joining two germs in a DCS tree, where a germ is defined as a specific semantic role of a node. For example, Figure 5 shows DCS trees of the following sentences (a simplified pair from RTE2-dev): T: Tropical storm Debby is blamed for deaths. H: A storm has caused loss of life.
The germ OBJ(blame) and germ ARG(death) in DCS tree of T are joined by the underscored path. Two paths are aligned if the joined germs are aligned, and we impose constraints on aligned germs to inhibit meaningless alignments, as described below.

Aligning germs by logical clues
Two germs are aligned if they are both at leaf nodes (e.g. ARG(death) in T and ARG(life) in H, Figure 5), or they already have part of their meanings in common, by some logical clues. To formulate this properly, we define the abstract denotation of a germ, which, intuitively, represents the meaning of the germ in the specific sentence. The abstract denotation of a germ is defined in a top-down manner: for the root node ρ of a DCS tree T , we define its denotation [[ρ]] T as the denotation of the entire tree [[T ]]; for a non-root node τ and its parent node σ, let the edge (σ, τ ) be labeled by semantic roles (r, r ), then define Now for a germ r(σ), the denotation is defined as the projection of the denotation of node σ onto the specific semantic role r: For example, the abstract denotation of germ ARG(book) in Figure 1 is defined as π ARG (book ∩ π OBJ (read ∩ (student SUBJ × book OBJ ))), meaning "books read by students". Similarly, denotation of germ OBJ(blame) in T of Figure 5 indicates the object of "blame" as in the sentence "Tropical storm Debby is blamed for death", which is a tropical storm, is Debby, etc. Technically, each germ in a DCS tree indicates a variable when the DCS tree is translated to a FOL formula, and the abstract denotation of the germ corresponds to the set of consistent values (Liang et al., 2011) of that variable.
The logical clue to align germs is: if there exists an abstract denotation, other than W , that is a superset of both abstract denotations of two germs, then the two germs can be aligned. A simple example is that ARG(storm) in T can be aligned to ARG(storm) in H, because their denotations have a common superset other than W , namely π ARG (storm). A more complicated example is that OBJ(blame) and SUBJ(cause) can be aligned,  (storm)]] H , so they also have the common superset π ARG (storm). However, for example, logical clues can avoid aligning ARG(storm) to ARG(loss), which is obviously T : T' :  Figure 6: Tree transformation and generated onthe-fly knowledge (subsumption of denotations shown above the trees) meaningless.

Scoring path alignments by similarity
Aligned paths are evaluated by a similarity score, for which we use distributional similarity of the words that appear in the paths ( §4.1). Only path alignments with high similarity scores can be accepted. Also, we only accept paths of length ≤ 5, to prevent too long paths to be aligned.

Applying path alignments
Accepted aligned paths are converted into statements, which are used as new knowledge. The conversion is done by first performing a DCS tree transformation according to the aligned paths, and then declare a subsumption relation between the denotations of aligned germs. For example, to apply the aligned path pair generated in Figure 5, we use it to transform T into a new tree T' (Figure 6), and then the aligned germs, OBJ(blame) in T and SUBJ(cause) in T', will generate the on-the-fly knowledge: Similar to the tree transformation based approach to RTE (Bar-Haim et al., 2007), this process can also utilize lexical-syntactic entailment rules (Szpektor et al., 2007). Furthermore, since the on-the-fly knowledge is generated by transformed pairs of DCS trees, all contexts are preserved: in Figure 6, though the tree transformation can be seen as generated from the entailment rule "X is blamed for death → X causes loss of life", the generated on-the-fly knowledge, as shown above the trees, only fires with the additional condition that X is a tropical storm and is Debby. Hence, the process can also be used to generate knowledge from context sensitive rules (Melamud et al., 2013), which are known to have higher quality (Pantel et al., 2007;Clark and Harrison, 2009).
However, it should be noted that using on-thefly knowledge in logical inference is not a trivial task. For example, the FOL formula of the rule "X is blamed for death → X causes loss of life" is: which is not a horn clause. The FOL formula for the context-preserved rule in Figure 6 is even more involved. Still, it can be efficiently treated by our inference engine because as a statement, the formula [[OBJ(blame)]] T ⊂ [[SUBJ(cause)]] T' is an atomic sentence, more than a horn clause.

Experiments
In this section, we evaluate our system on FraCaS ( §4.2) and PASCAL RTE datasets ( §4.3).

Language Resources
The lexical knowledge we use are synonyms, hypernyms and antonyms extracted from WordNet 12 . We also add axioms on named entities, stopwords, numerics and superlatives. For example, named entities are singletons, so we add axioms such as To calculate the similarity scores of path alignments, we use the sum of word vectors of the words from each path, and calculate the cosine similarity. For example, the similarity score of the path alignment "OBJ(blame)IOBJ-ARG(death) ≈ SUBJ(cause)OBJ-ARG(loss)MOD-ARG(life)" is calculated as the cosine similarity of vectors blame+death and cause+loss+life. Other structures in the paths, such as semantic roles, are ignored in the calculation. The word vectors we use are from Mikolov et al. (2013) 13 (Mikolov13), and additional results are also shown using Turian et al. (2010) 14 (Turian10). The threshold for accepted path alignments is set to 0.4, based on preexperiments on RTE development sets.

Experiments on FraCaS
The FraCaS test suite contains 346 inference problems divided into 9 sections, each focused on a category of semantic phenomena. We use the data by MacCartney and Manning (2007), and experiment on the first section, Quantifiers, following Lewis and Steedman (2013). This section has 44 single premise and 30 multi premise problems. Most of  Table 4: Accuracy (%) on FraCaS the problems do not require lexical knowledge, so we use our primary textual inference system without on-the-fly knowledge nor WordNet, to test the performance of the DCS framework as formal semantics. To obtain the three-valued output (i.e. yes, no, and unknown), we output "yes" if H is proven, or try to prove the negation of H if H is not proven. To negate H, we use the root negation as described in §2.5. If the negation of H is proven, we output "no", otherwise we output "unknown". The result is shown in Table 4. Since our system uses an off-the-shelf dependency parser, and semantic representations are obtained from simple rule-based conversion from dependency trees, there will be only one (right or wrong) interpretation in face of ambiguous sentences. Still, our system outperforms Lewis and Steedman (2013)'s probabilistic CCG-parser. Compared to MacCartney and Manning (2007) and MacCartney and Manning (2008), our system does not need a pretrained alignment model, and it improves by making multi-sentence inferences. To sum up, the result shows that DCS is good at handling universal quantifiers and negations.
Most errors are due to wrongly generated DCS trees (e.g. wrongly assigned semantic roles) or unimplemented quantifier triggers (e.g. "neither") or generalized quantifiers (e.g. "at least a few"). These could be addressed by future work.

Experiments on PASCAL RTE datasets
On PASCAL RTE datasets, strict logical inference is known to have very low recall (Bos and Markert, 2005), so on-the-fly knowledge is crucial in this setting. We test the effect of on-the-fly knowledge on RTE2, RTE3, RTE4 and RTE5 datasets, and compare our system with other approaches.

Impact of on-the-fly knowledge
Results on test data are shown in Table 5. When only primary knowledge is used in inference (the first row), recalls are actually very low; After we activate the on-the-fly knowledge, recalls jump to over 50%, with a moderate fall of precision. As a result, accuracies significantly increase.    Table 6. Bos06 (Bos and Markert, 2006) is a hybrid system combining deep features from a theorem prover and a model builder, together with shallow features such as lexical overlap and text length. MacCartney08 (Mac-Cartney and Manning, 2008) uses natural logic to calculate inference relations between two superficially aligned sentences. Clark08 (Clark and Harrison, 2008) is a logic-based system utilizing various resources including WordNet and DIRT paraphrases (Lin and Pantel, 2001), and is tolerant to partially unproven H sentences in some degree. All of the three systems pursue a logical approach, while combining various techniques to achieve robustness. The result shows that our system has comparable performance. On the other hand, Wang10 (Wang and Manning, 2010) learns a treeedit model from training data, and captures entailment relation by tree edit distance. Stern11 (Stern and Dagan, 2011) and Stern12 (Stern et al., 2012) extend this framework to utilize entailment rules as tree transformations. These are more tailored systems using machine learning with many handcrafted features. Still, our unsupervised system outperforms the state-of-the-art on RTE5 dataset.

Analysis
Summing up test data from RTE2 to RTE5, Figure 7 shows the proportion of all proven pairs and their precision. Less than 5% pairs can be proven primarily, with a precision of 77%. Over 40% pairs can be proven by one piece of on-the-fly knowledge, yet pairs do exist in which more than 2 pieces are necessary. The precisions of 1 and 2 pieces on-the-fly knowledge application are over  60%, which is fairly high, given our rough estimation of the similarity score. As a comparison, Dinu and Wang (2009) studied the proportion of proven pairs and precision by applying DIRT rules to tree skeletons in RTE2 and RTE3 data. The proportion is 8% with precision 65% on RTE2, and proportion 6% with precision 72% on RTE3. Applied by our logical system, the noisy on-the-fly knowledge can achieve a precision comparable to higher quality resources such as DIRT.
A major type of error is caused by the ignorance of semantic roles in calculation of similarity scores. For example, though "Italy beats Kazakhstan" is not primarily proven from "Italy is defeated by Kazakhstan", our system does produce the path alignment "SUBJ(beat)OBJ ≈ OBJ(defeat)SUBJ" with a high similarity score. The impact of such errors depends on the data making methodology, though. It lowers precisions in RTE2 and RTE3 data, particularly in "IE" subtask (where precisions drop under 0.5). On the other hand, it occurs less often in "IR" subtask.
Finally, to see if we "get lucky" on RTE5 data in the choice of word vectors and thresholds, we change the thresholds from 0.1 to 0.7 and draw the precision-recall curve, using two types of word vectors, Mikolov13 and Turian10. As shown in Figure 8, though the precision drops for Turian10, both curves show the pattern that our system keeps gaining recall while maintaining precision to a certain level. Not too much "magic" in Mikolov13 actually: for over 80% pairs, every node in DCS tree of H can be covered by a path of length ≤ 5 that has a corresponding path of length ≤ 5 in T with a similarity score > 0.4.

Conclusion and Discussion
We have presented a method of deriving abstract denotation from DCS trees, which enables logical inference on DCS, and we developed a textual inference system based on the framework. Experimental results have shown the power of the representation that allows both strict inference as on FraCaS data and robust reasoning as on RTE data. Exploration of an appropriate meaning representation for querying and reasoning on knowledge bases has a long history. Description logic, being less expressive than FOL but featuring more efficient reasoning, is used as a theory base for Semantic Web (W3C, 2012). Ideas similar to our framework, including the use of sets in a representation that benefits efficient reasoning, are also found in description logic and knowledge representation community (Baader et al., 2003;Sowa, 2000;Sukkarieh, 2003). To our knowledge, however, their applications to logical inference beyond the use for database querying have not been much explored in the context of NLP.
The pursue of a logic more suitable for natural language inference is not new. For instance, Mac-Cartney and Manning (2008) has implemented a model of natural logic (Lakoff, 1970). While being computationally efficient, various inference patterns are out of the scope of their system. Much work has been done in mapping natural language into database queries (Cai and Yates, 2013;Kwiatkowski et al., 2013;Poon, 2013). Among these, the (λ-)DCS (Liang et al., 2011; framework defines algorithms that transparently map a labeled tree to a database querying procedure. Essentially, this is because DCS trees restrict the querying process to a very limited subset of possible operations. Our main contribution, the abstract denotation of DCS trees, can thus be considered as an attempt to characterize a fragment of FOL that is suited for both natural language inference and transparent syntaxsemantics mapping, through the choice of operations and relations on sets. We have demonstrated the utility of logical inference on DCS through the RTE task. A wide variety of strategies tackling the RTE task have been investigated (Androutsopoulos and Malakasiotis, 2010), including the comparison of surface strings (Jijkoun and De Rijke, 2005), syntactic and semantic structures (Haghighi et al., 2005;Snow et al., 2006;Zanzotto et al., 2009;Burchardt et al., 2009;Heilman and Smith, 2010;Wang and Manning, 2010), semantic vectors (Erk and Padó, 2009) and logical representations (Bos and Markert, 2005;Raina et al., 2005;Tatu and Moldovan, 2005). Acquisition of basic knowledge for RTE is also a huge stream of research (Lin and Pantel, 2001;Shinyama et al., 2002;Sudo et al., 2003;Szpektor et al., 2004;Fujita et al., 2012;Weisman et al., 2012;Yan et al., 2013). These previous works include various techniques for acquiring and incorporating different kinds of linguistic and world knowledge, and further fight against the knowledge bottleneck problem, e.g. by back-off to shallower representations.
Logic-based RTE systems employ various approaches to bridge knowledge gaps. Bos and Markert (2005) proposes features from a model builder; Raina et al. (2005) proposes an abduction process; Tatu and Moldovan (2006) shows handcrafted rules could drastically improve the performance of a logic-based RTE system.
As such, our current RTE system is at a proofof-concept stage, in that many of the above techniques are yet to be implemented. Nonetheless, we would like to emphasize that it already shows performance competitive to state-of-the-art systems on one data set (RTE5). Other directions of our future work include further exploitation of the new semantic representation. For example, since abstract denotations are readily suited for data querying, they can be used to verify newly generated assumptions by fact search in a database. This may open a way towards a hybrid approach to RTE wherein logical inference is intermingled with large scale database querying.


extfieldsofstudy:
Computer Science
Medicine

text:
Generic Learning-Based Ensemble Framework for Small Sample Size Face Recognition in Multi-Camera Networks

Multi-camera networks have gained great interest in video-based surveillance systems for security monitoring, access control, etc. Person re-identification is an essential and challenging task in multi-camera networks, which aims to determine if a given individual has already appeared over the camera network. Individual recognition often uses faces as a trial and requires a large number of samples during the training phrase. This is difficult to fulfill due to the limitation of the camera hardware system and the unconstrained image capturing conditions. Conventional face recognition algorithms often encounter the “small sample size” (SSS) problem arising from the small number of training samples compared to the high dimensionality of the sample space. To overcome this problem, interest in the combination of multiple base classifiers has sparked research efforts in ensemble methods. However, existing ensemble methods still open two questions: (1) how to define diverse base classifiers from the small data; (2) how to avoid the diversity/accuracy dilemma occurring during ensemble. To address these problems, this paper proposes a novel generic learning-based ensemble framework, which augments the small data by generating new samples based on a generic distribution and introduces a tailored 0–1 knapsack algorithm to alleviate the diversity/accuracy dilemma. More diverse base classifiers can be generated from the expanded face space, and more appropriate base classifiers are selected for ensemble. Extensive experimental results on four benchmarks demonstrate the higher ability of our system to cope with the SSS problem compared to the state-of-the-art system.

small number of samples of him. With insufficient samples, the estimated face space is very likely to overfit the small training data, and the real face space cannot be well represented. Conventional methods suffer serious performance degradation from the small training data compared to large appearance variations caused by occlusions, aging, illumination changes, head poses, facial expressions, etc. [13][14][15]. To address the SSS problem, there have been many attempts in the literature such as the random subspace [5], patch-based methods [16], etc. However, the trained classifiers from small data are likely to become unstable and have poor generalization ability [9]. Currently, a machine-learning technique, known as ensemble learning, has received considerable attention and has led to significant improvement in recognition accuracy. Such algorithms are based on the idea that a pool of different classifiers can offer complementary information for classification. They first generate multiple base classifiers and then aggregate them based on an ensemble rule. They benefit from the base classifier collaboration, where the overall discriminative power is higher than a single classifier.
In the context of ensemble, accuracy and diversity are two important parameters referring to the performance of an ensemble system. Diversity measures the disagreement degree in the output of a set of base classifiers [17]. Intuitively, there is not a clear accuracy gain in an ensemble built from a set of identical base classifiers. The ideal situation is that a set of base classifiers can bear with different errors, and the final classification error can be minimized by the combination of multiple base classifiers.
However, existing ensemble methods often suffer from an underlying problem that the species of base classifiers learned from insufficient training data are not diverse enough to form an adequate feature space. They are very likely to be tightly correlated and make similar errors. Having less diverse base classifiers has become a bottleneck of existing ensemble algorithms.
Even having a large number of diverse base classifiers, another problem is worth further discussion. We cannot guarantee that all generated base classifiers are appropriate for classification. Integrating inappropriate base classifiers may degrade the performance. The relationship between accuracy and diversity is illustrated in Figure 2, where the growth of accuracy and diversity can be classified into three stages: development, maturity and decline. The accuracy grows up with the increase of diversity in the development stage, halts at the maturity stage and then decreases, while the diversity keeps increasing in the decline stage. We can see that the increase of diversity can improve the accuracy to a certainty degree, but they are not always linearly related. This leads to the diversity/accuracy dilemma [17], which is a challenging problem for existing ensemble learning algorithms. To solve the diversity/accuracy dilemma, it is highly desirable to improve both the diversity and the accuracy in the development stage and to suppress the unexpected diversity in the decline stage. Inspired by this finding, this work proposes a novel generic learning-based ensemble framework (GL-E), which arguments the small training data by generating new samples to generate diverse base classifiers during the development stage and introduces a tailored 0-1 knapsack solution [18] to select appropriate base classifiers for ensemble in the decline stage, so that the final accuracy and diversity are located at the maturity stage.

Contributions
Compared to existing algorithms [5][6][7][8][9][10][11], GL-E has the following characteristics: • GL-E augments the small data by yielding new samples. From the enlarged training data, more diverse base classifiers can be generated than existing ensemble methods; • Conventional ensemble algorithms involve all base classifiers for aggregation, which leads to a diversity/accuracy dilemma. In contrast, GL-E selects just appropriate base classifiers for ensemble based on an optimal solution. This strategy achieves the trade-off between the diversity and accuracy.
The rest of this paper is organized as follows: Section 2 reviews some related works. The motivation of this work is stated in Section 3. Section 4 describes the proposed method in detail. We evaluate the system using four widely-used databases in Section 5. Finally, Section 6 concludes this paper.

Related Works
While this paper mainly concerns the SSS problem, we provided a literature review on ensemble learning-based methods for SSS face recognition. They can be mainly divided into three categories: (1) global feature selection using random subspace; (2) patch (block)-based local feature extraction; and (3) global and local feature integration.
The first category introduces a random subspace to ensemble. Literature work [19] finds that strong and stable base classifiers defined by subspace-based algorithms (e.g., Linear Discriminant Analysis (LDA)) are not suitable for ensemble rules. Thus, a random subspace (RS) [5] was employed to generate weak, but diverse base classifiers by doing random sampling in the PCA subspace. As RS focuses on the global-rather than local-based feature extraction, local discriminant information is not guaranteed. Motivated by this, the second category develops local feature extraction-based methods by partitioning face images into multiple patches/blocks and extracts features from each patch/block separately. These are named the patch (block)-based methods [9]. An early attempt [20] divided face images into six elliptical sub-regions, such as nose, mouth and eyes [12], and learned a local probabilistic model for recognition. Topcu et al. [16] proposed an alternative way of partitioning face regions into equally-sized small patches. Features extracted from each patch were classified separately, and the recognition results were combined by a weighted sum rule. As small patches usually have limited ability to deal with large variations, considering that global and local feature representation can provide complementary information, the third category integrates the global and local features for classification. For instance, Su et al. [21] developed a hierarchical model, where the global feature vector is extracted from a whole face image using the low frequency Fourier coefficients, and the local feature vectors are formed based on LDA. The global feature and local features are combined by a weighted sum rule. Zhu et al. [9] proposed a multi-scale patch-based collaborative representation (MPCRC) by integrating the complementary information obtained at different scales of patches. Spreeuwers et al. [8] proposed a 30-region method, which defined 30 regions of variant sizes according to experimental experience. The largest one covers almost the whole face region.
Beyond SSS face recognition, there have been some special attempts at SSPP face recognition. For instance, unsupervised learning-based methods apply the classical PCA and its variant extensions, such as Two-Dimensional PCA (2DPCA) [22], Projection-Combined Princi-pal Component Analysis ((PC) 2 A) [23] and 2-Directional 2-Dimensional PCA ((2D) 2 PCA) [24], to generate a holistic-feature vector from the total gallery data. Virtual sample generation-based methods, e.g., SVD-LDA [25], generate some virtual samples for each person. Generic learning-based methods, e.g., adaptive generic learning (AGL) [26] and adaptive discriminant analysis (ADA) [10], collect an auxiliary generic set containing multiple samples per person to learn the recognition model to identify the people with a single sample. Patch (block)-based methods, such as block PCA [27], block LDA [28] and discriminative multi-manifold analysis (DMMA) [11], are employed to learn base classifiers from local subregions and integrate them to form a final classifier.

Motivation
Ensemble learning can be performed in either the original training data or the enlarged training data. Generic learning (GL) is an effective approach to augment the small training data. Conventional GL-based approaches utilize an auxiliary set (named the generic set) containing a large number of samples to assist in learning the classification model of small data. Intuitively, the faces of all human beings look alike, which implies that different people may have similar face images. Conventional GL-based methods try to grab face images from the generic set that are similar to those in the sample set and treat them as the samples in the small sample set. However, no matter how similar these sample are, they actually do not belong to the subjects in the small sample set. These methods suffer from a severe problem that if these subjects, who belong to the generic set other than the small sample set, are present in the test sample set, they are very likely to be misidentified as the subjects in the small sample set.
To overcome this problem, this paper proposes augmenting the small training data by generating new samples based on a generic distribution other than grabbing samples from the generic set directly. To explore the generic distribution of face images, we use the YouTube Faces database (YTF), which contains the largest number of subjects (1595 different subjects) and has the highest degree of unconstrained behaviors. Each subject possesses an average of 2.15 videos. Each video ranges from 48 frames to 6070 frames, with an average of 182 frames per video. Faces in each frame were detected by the Viola-Jones face detector. We randomly selected 100 face images owned by five subjects and projected them to the 3D space for the ease of presentation. The distribution of face images is shown in Figure 3a.
We can see that all of the face images are uniformly distributed in the manifold face space. Motivated by this observation, for the given small training data, our algorithm aims to generate new samples based on a uniform generic distribution.
The main idea is illustrated in Figure 3b.
For the given small training data, which is located at the center of the face space, we introduce several random matrices R i , i = 1, 2, ..., L based on a uniform distribution to explore the new possibilities of face space. For each random matrix, we can generate a new training sample set. Additionally each training sample set can be used to train a base classifier. Specifically, instead of adding random matrices to the original face images, we first model the feature distribution of the small data by a template image f T and then add R i to f T to get an image f i T . Then, quad-tree decomposition [18] is performed on each f i T to get an image encoding pattern, according to which the original face images are re-organized to generate a new training sample set. Since all of the new samples are generated using the original face images, they should be located around the original small sample set. This strategy expands the face space to a large extent.

The Proposed System
The whole framework is illustrated in Figure 4, which involves the following three steps: • Generic learning-based base classifier definition: The face space is expanded by generating new samples based on a uniform distribution. Diverse base classifiers are generated from the expanded face space subsequently.
• Optimal solution-based base classifier selection: To address the diversity/accuracy dilemma, an optimal solution motivated by the 0-1 knapsack problem is employed to select appropriate base classifiers for ensemble.
• Majority voting-based base classifier integration: Multiple base classifiers are integrated based on majority voting.
We design each step in the following Sections 4.1-4.3, respectively.

Generic Learning-Based Base Classifier Definition
The generic learning-based base classifier definition mainly consists of three operations: (1) template image generation and random matrix introduction; (2) new sample generation based on quad-tree decomposition; and (3) the definition of the accuracy and diversity of base classifiers.

Template Image Generation and Random Matrix Introduction
Motivated by the idea of LDA, which encodes discriminant information by maximizing the between-class scatter matrix S b and minimizing the within-class scatter matrix S w (see Equation (1)), we define a template face f T by Equation (2) to represent the discrimination distribution across a database.
where c is the number of classes in the dataset, µ is the mean image of all classes, µ i is the mean image of class X i , N i is the number of samples in class X i and x k is the k-th sample of class X i . For the face images of size m × n, the covariance matrix S b Sw is of size (m × n) 2 . f T is defined by the diagonal vector of S b Sw , whose entries represent the variances at each pixel of the face region across the database. It is of the same size as the original face images.
Since the template image f T generated from the small training data has a weak ability to represent the whole face space, we generate several new images .., L is distinct and has the same size as f T , whose elements are randomly chosen from a uniform distribution. The new image f i T is generated by the dot product of f T and R i as: Please note that the generation of f T fails under SSPP, since no samples are available to construct S w . Regarding this, f T is defined by just S b under SSPP. An example of template face generation and random matrix introduction is shown in Figure 5.

New Sample Generation Based on Quad-Tree Decomposition
We perform quad-tree decomposition on each f i T to study the regions of high density of discriminant features across the face area. The decomposition is performed according to a function doSplit(r) defined in Equation (4) [18]. If the variance of a region r (starting from the whole region of f i T ) is higher than or equal to a threshold variance (t v ), then r is split into four sub-blocks of the same size. The partition carries on until no blocks satisfying the criterion function or candidate blocks have reached the smallest size.
The image f i T is split into less and bigger blocks for a large t v , but into more and smaller blocks for a small t v . Local variances usually vary on different databases. Even for one database, it is rather difficult to find the best partition using one universal threshold t v [18]. For this reason, this paper develops a data-adaptive threshold definition algorithm utilizing the quad-tree structure. The entire procedure is as follows: Step 1 Assign an initial estimate for the threshold: t v = 0.5 * var(wholeR), where wholeR denotes the whole region of f i T ; Step 2 Partition f i T using t v based on Equation (4). This step produces a hierarchical quad-tree structure as shown in Figure 6. It contains leaf and non-leaf nodes. For each leaf node subR i , we calculate its variance: var(subR i ); Step 3 From bottom to top, we calculate the variance of each non-leaf node subR j by the average of its four children subR k , k = 1, ..., 4 based on a weighted sum rule. The weight of each child node subR k is defined by the number of leaf nodes in the subtree rooted at subR k against that number rooted by its father node subR j . An example of the quad-tree structure with weight assignment is shown in Figure 6. When we reach the top level, we can calculate the value of the root node var(root) and assign it to the new threshold t v for the quad-tree partition.
Step 4 Repeat Steps 2 through 3 until the difference between two quad-tree partitions is smaller than a threshold distance. Specifically, we encode each quad-tree by a 0-1 sequence according to a full quad-tree partition, where leaf nodes are assigned one and non-leaf nodes are assigned zero. The distance between two quad-trees is defined by the Hamming distance of two 0-1 sequences. If this distance is smaller than a threshold distance denoted by ε * M , where ε is the tolerance error and M is the length of the 0-1 sequence, then the iterative process stops. Here, we define ε = 5% in this paper.
Our algorithm updates the threshold according to the last quad-tree structure in each repeat. The new threshold is closer to the values of regions containing a high density of discriminant features. Finally, our algorithm can find the most appropriate threshold for each f i T automatically. Figure 6. An example of a quad-tree partition.
After quad-tree partition, we get a face encoding pattern, as shown in Figure 7a. Each quad-tree structure refers to such a pattern. Given L random matrices, we can get L such encoding patterns. All face images in the original training set are re-organized according to each pattern to generate a new training sample set. The procedure is as follows: since larger blocks (in black) imply that the density of discriminate information within them is low, these blocks have no need to keep their original sizes. We do down-sampling on them by resizing them to smaller regions of ((d/2) × (d/2)), where d is the dimension of the block (in pixels). The smallest blocks (in white) imply that they have a high density of discriminant features. We will keep their size. Quad-tree decomposition and block resizing generate new face samples, which are smaller than the original face images. A base classifier b i is learned from each new training sample set. A interesting observation is that our quad-tree partitions shown in Figure 7 prove an important literature finding in the biometric field. Recently, researchers have used the area around the eye, the periocular region (see Figure 8), as a stand-alone biometric with promising results [30]. They found that the periocular region offers advantages over full face biometrics, such as: (1) it is least affected by expression variations, aging effects and changes due to the growth of male facial hair; (2) the performance of full face recognition degrades in the presence of pose variations, whereas the periocular region-based identification may perform better in the case of extreme pose changes when only one eye is completely visible; and (3) periocular region-based recognition remains effective even if most of the lower face region is occluded and as long as only one eye remains visible. Currently, these findings have only been observed from experimental results. They have not been proven from other perspectives, yet. Our partition results shown in Figure 7 demonstrate the higher density of the discrimination information in the periocular region as opposed to other regions and prove theses findings accordingly.

The Definition of the Accuracy and Diversity of Base Classifiers
We regard the performance of an ensemble E as a function F , which corresponds to two parameters: (1) the accuracy (acc(E)); and (2) the diversity (div(E)).
Let a labeled training sample set be The accuracy of each base classifier b j is defined in Equation (5) by the ratio of its correctly-classified samples against the total samples. Additionally, the accuracy of the ensemble acc(E) is defined by that ratio based on the majority voting of a set of base classifiers in Equation (6).
The diversity of ensemble (div(E)) is investigated in several literature works. For instance, in [17], six common measurements are analyzed, namely disagreement measure, double fault measure, KWvariance, inter-rater agreement, generalized diversity and measure of difficulty. As concluded in [17], these measures are motivated by different problems in pattern classifications. None of them is universal for all applications. In this paper, we utilize the disagreement measurement to calculate div(E), which was originally proposed in an ensemble framework [31], and the intuition behind its definition coincides with the expectation of our method (two diverse classifiers perform differently on the same training data).
For a query set containing N test samples, each base classifier b i , 1 ≤ j ≤ L assigns a label to each sample x i , 1 ≤ i ≤ N . The diversity between each pair of base classifiers b i and b j is defined by the number of samples for which they have different labels against the total number of samples: where a and b denote the labels assigned by b i and b j , respectively; n(a, b), a = b represent the number of samples, on which b i and b j have different labels. Diversity among all base classifiers is calculated by averaging over all pairwise diversities in Equation (8), which measures the total disagreement among all base classifiers.

Optimal Solution for Base Classifier Selection
As mentioned before, not all generated base classifiers are located within the face space, as we expected. Even the base classifiers in the face space may perform differently according to the discriminant features involved. That is, some base classifiers are not appropriate for classification. Integrating inappropriate base classifiers may lead to the diversity/accuracy dilemma, which has been illustrated by the experimental results in Figure 9. To alleviate this problem, an optimal solution motivated by the 0-1 knapsack algorithm is tailored to select appropriate base classifiers for ensemble. The selection can be considered as a combinatorial optimization task. Suppose each base classifier has two items: (1) the recognition accuracy; and (2) the disagreement with other base classifiers in making decisions; which contribute to the diversity of an ensemble. Given a set of base classifiers, our goal is to find an optimal subset of base classifiers E that maximizes the final accuracy, while the diversity of E is still higher than or equal to a threshold diversity t d . The mathematical interpretation of our problem is: where D(E) = div(E) denotes the diversity of E and t d is the diversity threshold.
Our problem is very similar to the conventional 0-1 knapsack problem, which is defined as: given a set of items, each item has a mass and a value. We select some items and put them into a knapsack K, which maximizes the total value of K, and the total weight of K is less than or equal to the capacity of K. This can be interpreted as: where value(K) and mass(K) denote the total value and total mass of selected items in K, and t c represents the capacity of K. Comparing optimization (9) and (10), we find that they are very similar to each other. The value(K) and mass(K) are much like the acc(E) and D(E) in our problem. Nevertheless, our problem is not equivalent to the 0-1 knapsack problem. One of the main difference lies in the constraint interpretation, where the knapsack problem requires the total weight to be less than or equal to a given limit, and our problem requires the diversity of ensemble to be higher than or equal to T d . So that our problem more naturally converts to the 0-1 knapsack problem, we rewrite the constraint as: the inverse of the total diversity of E is less than or equal to the inverse of the diversity threshold t d .
Another difference is that the traditional 0-1 knapsack problem assumes that different items have different masses and weights, and hence the optimal solution is unique. However, in our case, since different base classifiers may have the same accuracy and diversity, multiple subsets of base classifiers may achieve the optimal solution simultaneously. Under such circumstances, to reduce the computational complexity of an ensemble, we select the subset with the least number of base classifiers as the final optimal solution.
Finally, our problem can be formulated as: where num(E) denotes the number of base classifiers involved in E. The diversity threshold t d is defined by such a diversity, which the accuracy of an ensemble achieves at its highest value. As shown in Figure 9, such t d varies on different databases. Actually, the definition of t d depends on both the application requirement and data property. For applications with a high requirement on diversity, we should assign a relatively high value to t d (e.g., 0.9), and vice versa. In this paper, to make t d adapt to different databases, we define t d as the mean value of such t d s on four databases.

Base Classifier Integration
To aggregate the selected base classifiers B = {b 1 , b 2 , ..., b L }, we use the majority voting scheme. The ensemble classifies test samples by taking a majority vote among all base classifiers and assigns the class label that receives the largest vote to them.

Algorithm Description and Analysis
The skeleton of the proposed GL-E framework is illustrated in Algorithm 1. Generate a template image f T using Equation (1). For r = 1, 2, ..., L, repeat 1.1: Add a random matrix R r to f T to get a new image f r T defined by Equation (3); 1.2: Perform quad-tree decomposition on f r T to get an encoding pattern P r by Equation (4) and use P r to generate a new gallery dataset X G r ; 1.3: Perform PCA + LDA on X G r to define a base classifier b i , the output decision vector of b r is Y r , the accuracy of b r is denoted by acc(b r ). end Step 2: Optimal selection: Select a subset of base classifiers E using the optimal solution in Equation (11).
Step 3: Majority voting: Integrate the base classifiers in E using the majority voting.

Output decision vector:
Output the labels of samples in the probe set Y = max( Y r ).
We briefly analyze the computational complexity of GL-E according to its three main processing stages: generic learning-based base classifier definition, optimal base classifier selection and majority voting. The first stage mainly involves a template image calculation, quad-tree decomposition and the performance analysis of base classifiers based on PCA + LDA.  d 2 m)). In the second stage, the tailored optimal 0-1 knapsack problem can be solved by dynamic programming, which requires O(LlogL) computations. The majority voting takes O(L) computations. Thus, the total computational complexity of our system is O(L(d 3 + d 2 m + LogL + 1)).

System Performance Analysis
We evaluated our system (GL-E) on four widely-used databases, namely: ORL [33], Extended Yale (Yale2) [34], AR [35] and FERET [36]. First, we analyzed the influences of a key parameter of our method: the number of base classifiers. Then, we compared our method with a wide range of face recognition algorithms on SSS and 15 state-of-the-art methods on the SSPP problem. Finally, we evaluated the performance of optimal base classifier selection, followed by the summary of simulation. To better compare our method with existing methods, we conduct the SSS face recognition with different numbers of enrolled samples as the training data. We randomly select p samples per subject from the database as training data and the rest of the samples as test data. We perform 10 splits for each database. For each split, we apply k-fold cross-validation (k = 5) to evaluate the performance of our algorithm with and without base classifier selection, respectively. Specifically, both the training data and test data are divided into k subsets, as shown in Figure 10. Each subset has the same number of subjects. The holdout validation is repeated k times. Each time, one of the k subsets is treated as training data and validation data, which is used to train the base classifier selection. The other k − 1 subsets are treated as training data and test data to report the performance of our method with and without base classifier selection (denoted by Our-Selection ('Our-Sel.') and Our-Original ('Our-Org.'), respectively). The final performance of our method is calculated by the average accuracy over 10 * k trials (10 random splits by k-fold cross-validation). We use PCA + LDA to extract features and apply the nearest neighbor classification with the L 2 -norm for matching. The feature dimension of the PCA + LDA subspace is defined by subjectN umber − 1 for each database.  . Each subject has 26 samples, taken in two sessions (separated by two weeks), and each session contains 13 samples. Similar to [11], eight subsets (A to H) of 800 images (eight images per subject) from 100 different subjects (50 men and 50 women) were used in our experiments. They were taken from two separate sessions and with different expressions. Figure 11c shows sample images from Subsets A to H, where A is used for training and the remaining seven subsets for testing.
• FERET database: This contains 13,539 facial images corresponding to 1565 subjects. Images differ in facial expression, ethnicity, gender and age. We worked with the grayscale images from GrayFERET (FERET Database, 2001). Two subsets (FERET-1 and FERET-2) are used to evaluate the performance of our method on SSS and SSPP face recognition, respectively. Similar to [7], FERET-1 contains all available subjects that have more than four frontal images. There are 665 images from 82 subjects in total. Similar to [11], FERET-2 is a subset containing 400 frontal face images belonging to 200 different people (71 females and 129 males). Each subject has two images (Fa and Fb) varying in race, gender, age, expression, illumination, scale, etc. Face images in the first three databases are aligned to 32 × 32 using the method in [32]. The FERET database is normalized using the CSUFace Identification Evaluation System 5.1 [37]. The face images are cropped to the same size: 32 × 32. Sample images of all databases after histogram equalization are shown in Figure 11.

Parameter Analysis
We investigate a key parameter of our method: the number of base classifiers L. We pick up two representative databases for analysis: a relatively large database, Yale2 with p = 5, and a small database, ORL with p = 2. The recognition accuracy of our method for these two databases, where L ranges from 20 to 50, is demonstrated in Figure 12a,b, respectively. We observe that GL-E has a stable recognition accuracy versus a large range of base classifiers for both databases. In order to save computational cost, L is set to a relatively small value, 20, without losing performance.

Comparison with Existing Methods on SSS Face Recognition
In this part, we compared our method with a wide range of algorithms on SSS face recognition, including: conventional algorithms without ensemble and existing ensemble methods [5][6][7][8][9][10][11]. Tables 1-3 tabulate the rank-one recognition accuracy of comparison methods on ORL, Yale2 and FERET-1 databases. In Tables 1-3, the fist column lists the comparison methods, and the rest of the columns report the recognition accuracy of these methods using p samples per person as the training data. ROC curves of our method on four databases are shown in Figure 13.

Comparison with Conventional Face Recognition Algorithms without Ensemble
We have compared our method with several conventional face recognition algorithms without ensemble, including: PCA family [7], LDA family [32], LPP family (locality preserving projections) [32], CCA family (canonical correlation analysis) [6] and several other representative methods, such as SVM, neural network-based methods (MLP (multilayer perception) and RBF (radial basis function network)) [7]. For a fair comparison, we reported the performances of these methods presented in their published papers. As these methods were not implemented on all of the databases in the reference papers, we compare with different methods on variant databases.
We got the following observations from Tables 1-3: (1) Performance degrades for the SSS problem: For all databases, we find that conventional methods obtain relatively high performance when the gallery data have moderate or a large number of training samples. However, their performances degrade as p decreases. This implies that the SSS problem challenges existing face recognition algorithms.
(2) Supervised learning outperforms unsupervised learning: Compared with PCA-based unsupervised learning methods, LDA-based supervised learning methods have relatively higher performance on almost all experiments, which shows the superiority of employing supervised learning in dealing with the SSS problem.
(3) Global and local feature-based methods have both advantages and disadvantages: For the ORL database, which contains multiple variations caused by head poses, facial expressions, open/closed eyes, head scale changes, with/without glasses, etc., the local feature-based method (the classical LPP) outperforms the global feature-based method (the classical LDA). However, this is opposite for the Yale2 database, which contains illumination variations. This implies that both global-and local feature-based methods have their own advantages and disadvantages. Feature representation is not the key point in solving the SSS problem.
(4) Increasing diverse samples is more important: An interesting observation is captured between 2DCCA(in Tables 1 and 2) and 2DPCA (in Table 3). 2DCCA is an upgraded CCA algorithm targeting the SSS problem by directly extracting features from the image matrix rather than from the matrix to vector transformations. It consistently outperforms other variants of CCA in Tables 1 and 2. Similarly, 2DPCA applies this strategy, but it fails at performance improvement (see Table 3). This implies the 2D-matrix-based feature representation is not always effective for the SSS problem. The key point is to expand the face space by generating more samples rather than changing its representation.
(5) Our method performs better: Compared with all conventional methods without ensemble, our method, GL-E, obtains better performance on all experiments. There are two main reasons: (1) by generating new samples from GL-E, the original training data have been enlarged effectively, such that the face space can be represented by our method more accurately; (2) the generated base classifiers learned from the enlarged training data are diverse, offering complementary information for classification, and hence, the overall discriminative power is much greater than a single classifier. Benefiting from both new sample generation and ensemble learning, our method shows a better ability to address the SSS problem over conventional face recognition methods.

Comparison with Existing Ensemble Methods
Ensemble methods have been widely applied to deal with SSS face recognition. We have compared our method with three kinds of representative methods: (1) global feature selection based on a random subspace [5]; (2) patch (block)-based local feature extraction, such as PCRC [9], and a patch-based method using LBP (local binary pattern) [7], which partition face images into small patches of the same size; and (3) global and local feature integration-based methods, such as the 30 region method [8], which defines 30 regions with large overlaps according to experimental experience, and the multi-scale patch-based method, MPCRC [9], which integrates the collaboration of patches of multi-scales to generate global feature representation. We reported the performance of LBP-based methods in [7]. We implemented the 30 region method and used the source code of PCRC and MPCRC in [9]. As this source code [9] requires all subjects to have the same number of training samples and test samples, only ORL and Yale2 met this requirement.
We got the following observations from Tables 1-3: (1) Ensemble learning can improve the performance: In Table 2, we observe that the ensemble-based methods outperform conventional algorithms without ensemble. This demonstrates the effectiveness of ensemble. However, existing ensemble methods are not always effective at coping with the SSS problem. For example, in Table 1, higher performances are achieved by the CCA and LPP families rather than existing ensemble algorithms. This shows the limited ability of existing methods when dealing with SSS.
(2) Local feature-based ensemble outperforms global feature-based ensemble: Compared with RS, the local patch-based method PCRC outperforms all conventional face recognition methods without ensemble of the Yale2 database (see Table 2) and has comparable results with S-LDA and S-LPP for the ORL database (see Table 1), which obtains the highest accuracy among conventional methods without ensemble. This shows the superiority of local feature extraction over global feature selection when dealing with local variations. However, the performance of patch-based methods is sensitive to the design of the patch size. An inappropriate patch size may lead to performance degradation, which has been illustrated in Table 3. Among the three variants of LBP, the one with a patch size of 7×7w performs better than the other methods at p = 2. However, this is not true for the other two versions (LPP 5 × 5 and LPP 7 × 7).
(3) Global and local feature integration improves performance further: To overcome the problem of patch-based methods, the global and local feature integration-based methods were proposed. We find that the 30 region method outperforms RS and PCRC in Table 2, and MPCRC obtains the highest performance among all existing methods in Tables 1 and 2. This implies the effectiveness of integrating local patches of variant sizes together to generate the global feature representation. However, we observe that the 30 region method performs worse than some of conventional methods for the ORL and FERET databases. The main reason is that the 30 regions are manually designed according to experimental experience after face registration. For well-registered databases, such as Yale2, which contains only near frontal images, the 30 region method performs well. However, for not well-registered databases, such as ORL and FERET, which contain variations of head poses, ethnicity, gender and age, its performance reduces obviously. We also find that MPCRC performs not so satisfactorily for the ORL database (see Table 1), which contains more variations. There are two main reasons: (1) it is developed on the small gallery data, while the probing set contains much more variations. Although the patch-based representation can deal with some local appearance variations, it is unable to reconstruct the expected face space with large variations caused by head poses etc.; (2) the multi-scale scheme of MPCRC just integrates the complementary information obtained at different scales of patches without considering the geometric co-relationship between local patches. According to the finding in [11], there is high overlap between manifolds of local patches. This suggests that the geometric information between local patches is also important for recognition.
(4) Our method performs better than existing ensemble methods: Compared with existing ensemble methods, our method obtains better performance in almost all experiments. It offers advantages over existing methods thanks to three main benefits: (1) Unlike existing methods, which train base classifiers from small training data, our method generates new samples to enlarge the given data. Base classifiers generated from the enlarged training data are more diverse and accurate for estimating the face space; (2) Other than existing methods, which divide face regions into separated patches, GL-E partitions face images into blocks of variant sizes according to a tree structure, which preserves the geometric correlationship between local blocks; (3) In contrast to existing methods, which involve all generated base classifiers for ensemble, our method formulates the ensemble as an optimal base classifier selection, which just selects appropriate base classifiers for integration. Our algorithm achieves a trade-off between diversity and accuracy. From Tables 1-3, we can observe that Our-Sel. outperforms Our-Org. for almost all splits of databases, which demonstrates the effectiveness of base classifier selection.
(1) Block-wise supervised learning does not always outperform the block-wise unsupervised learning: For the AR database, we find that the block-LDA does not perform better than block-PCA. This is because block-wise approaches assume that features are distributed in blocks evenly. Block-LDA partitions face images into multiple blocks and treats each block as an independent sample to estimate the within-class scatter matrix. However, the literature work [11] finds that there is high overlap between manifolds of local blocks. Summarizing separated blocks without considering any associations between them is not reliable to estimate the within-class matrix of LDA.
(2) The key point of virtual sample generation is to generate diverse samples: The virtual sample generation-based method, SVD-LDA, obtains the worst performance for the AR database. The reason is that by discarding just some smaller singular values of the original image, the virtually generated new samples are highly related to the original sample. Hence, the within-class scatter matrix cannot be accurately estimated under such cases. We draw the conclusion that generating new diverse samples, which have less co-relationship with the original samples, is the key point of applying virtual sample generation to take advantage of supervised learning.
(3) Generic learning needs further investigation: Compared with the generic learning-based method, ADA, we can see that both DMMA and GL-E achieve better performance than ADA. This further proves that generic learning needs to generate news samples other than grabbing samples from the generic set directly.
(4) Global and local feature-based ensemble reduces performances under SSPP: The performance of MPCRC and the 30 region method is not stable under SSPP. MPCRC degenerates to the original patch-based method, PCRC, without any collaboration of multiple patches of variant scales. As mentioned before, the performance of local patch-based methods is very sensitive to the design of patch size, especially when the database contains many local deformations. That is why it performs well on Subset E of the AR database, which contains just nearfrontal faces without any expressions, but degrades dramatically to 79% for the FERET-2 database, which contains a large number of local deformations caused by facial expressions etc. As explained before, the 30 region method reduces the performance for not well-registered databases. Thus, it performs well for part of AR database, which contains only frontal images, but not for the FERET-2 database.
(5) Our method shows advantages for SSPP: Among all of the comparison algorithms, GL-E outperforms most of the methods, and it obtains comparable performances with the recently developed DMMA algorithm for the AR database and outperforms DMMA with a gain in accuracy of 1.0 percent for the FERET-2 database. The reason why our algorithm is comparable to these state-of-the-art methods is that GL-E does expand the face space in the training stage by generating new samples. Compared with existing virtual sample generation methods, the new generated samples are quite diverse and different from the original training data, thanks to the introduction of random matrices. Moreover, our method not only encodes discriminant features, but also geometric information, which contribute to recognition. We acknowledge that DMMA outperforms our method on some subsets of the AR database. This is mainly because it extracts features in a person-specific manner rather than in a generic way. By modeling the manifold surface for each subject and performing classification through maximizing the manifold margin between different subjects, it employs personal characteristics (e.g., age, hair style, etc.) during recognition and improves the recognition accuracy. However, we argue that the effectiveness of this strategy is challenged by the number of subjects involved. With the increase of the number of subjects in the database, the maximization of the manifold margins between different subjects becomes more difficult. This then causes errors. That is why DMMA has a reduced performance for the FERET-2 database, which contains twice the subjects of the AR database. our method performs well on a large range of base classifiers. Compared with conventional algorithms on SSS face recognition, we observe that ensemble learning improves the recognition accuracy, thanks to the base classifier collaboration. Benefiting from both new sample generation and ensemble learning, our method outperforms existing ensemble methods, whether with or without ensemble. Moreover, our base classifiers encode not only discriminant features, but also the geometric correlationship between subregions. For SSPP face recognition, our method performs better than almost all 15 state-of-the-art methods, and it obtains comparable performances with the latest developed DMMA algorithm, which demonstrates the superiority of our system in dealing with both SSS and SSPP problems. Through evaluation of the optimal base classifier selection using kappa-error diagrams, we find that the number of base classifiers and the average errors are reduced obviously after selection. Our system effectively alleviates the diversity/accuracy dilemma.

Conclusions
In multi-camera networks, person re-identification is an essential and challenging task. It often uses faces as a distinct trial and suffers from the small sample size (SSS) problem arising from the small number of training samples compared to the high dimensionality of the sample space. In this paper, we propose a novel generic learning-based ensemble framework (GL-E) to address this problem. GL-E overcomes the two serious problems of existing ensemble methods for SSS face recognition: (1) base classifiers are not diverse enough using small training data; and (2) the diversity/accuracy dilemma occurs during ensemble. We solve the first problem by generating more diverse base classifiers from the enlarged training data using generic learning. Additionally, the second problem is settled by applying an optimal base classifier selection, which selects a subset of appropriate base classifiers for aggregation. Use of this solution achieves the trade-off between the diversity and the accuracy of an ensemble. Extensive experimental results on four widely-used databases demonstrate that GL-E estimates a more accurate and robust ensemble for both SSS and SSPP face recognition.
Though promising results have been achieved, the proposed system still has space to extend. For instance, we adopt random matrices in generating base classifiers; random matrices may introduce some noises, which influence the quad-tree decomposition. How to remove such noises needs further investigation. Moreover, diversity is an important factor to evaluate an ensemble system. We simply use a common definition, the "disagreement degree", in this paper. There should be better schemes to investigate this factor. For the future work of this paper, we are going to improve the system with respect to these issues.