Egon Stemle

Alexander Onysko

Automated L1 identification in English learner essays and its implications for language transfer

, which involves a sample of 12,100 essays written by participants in the TOEFL® test from 11 different language backgrounds (Arabic, Chinese, French, German, Hindi, Italian, Japanese, Korean, Spanish, Telugu, and Turkish). The article will show our results in automatic L1 detection in the TOEFL11 corpus. These results are discussed in light of relevant transfer features which turned out to be particularly informative for automatic detection of L1 German and L1 Italian.

Introduction

In the field of research on language transfer, computational means of authorship identification are a fairly recent development that can provide empirical insight in the relevance of transfer phenomena among language learners. As described in the first volume devoted to this topic (Jarvis and Crossley 2012), automatic recognition of transfer is based on the presupposition that a learner's L1 will influence the use of the learner language (Jarvis 2012: 1). Furthermore, if groups of learners sharing the same L1 background are considered, it is likely that they will show similar patterns in using the learner language. In other words, language learners of the same L1 will exhibit intragroup homogeneity while learners from different L1 backgrounds will be heterogeneous to each other (Jarvis 2012: 5). Based on this premise, computational calculations of different textual features are supposed to bring to light such intergroup differences. Thus, if other factors are sufficiently controlled for, a classification of learner texts according to the L1 of their authors becomes possible.

Apart from the obvious benefit of being able to process large amounts of language data by computational means, automated classification of learner texts also allows taking a detection-based approach to possible transfer effects. By feeding computer classifiers with general parameters for calculating textual features relating to, for example, text size, word choice, punctuation, parts of speech, and syntactic information, the results of such classifications can provide evidence for L1-based patterns of transfer that emerge as characteristics of a specific learner group. It is intrinsic to this type of automated approach to transfer as measurable crosslinguistic influence (cf. [START_REF] Jarvis | Crosslinguistic Influence in Language and Cognition[END_REF] that primarily instances of negative transfer are detected. These appear as structures and patterns of language which either stick out from native language use or from the comparison with observable patterns of other learner groups.

Embracing the potential of automated L1 identification for the investigation of language transfer, our paper reports on a study conducted as part of a Native Language Identification Task (cf. [START_REF] Tetreault | A report on the first Native Language Identification shared task[END_REF] open to participants in spring 2013. The task was carried out on the basis of 12,100 written TOEFL® texts (short argumentative essays) from learners of English involving 11 different first languages. In this paper, we will show the results of our automated classification and then focus on some of the patterns that are particularly informative for successfully detecting the L1 backgrounds of German and Italian learners of English. These patterns will be discussed in light of their origin as potential transfer effects. Before presenting the results and discussing the role of transfer, the next section will provide an overview of previous research on transfer in computational L1 classification, and Section 3 will lay out the methodology of the task and our computational approach.

Previous research on transfer in automated L1 identification

Research on L1 identification 2 has grown out of the field of stylometry, which is concerned with authorship attribution based on statistical calculations of textual features (cf. [START_REF] Barr | Two styles in the New Testament epistles[END_REF]. Classifying texts by the L1 of their speakers is also generally related to research on automated text classification, which frequently applies machine learning algorithms to sort texts by their type or author attributes. For example, [START_REF] Baroni | A new approach to the study of translationese: Machine-learning the difference between original and translated text[END_REF] employ support vector machines to successfully differentiate between original and translated Italian texts in 86.7% of their corpus of Italian articles.

As pointed out in Jarvis (2012: 14), the first study applying means of automated text classification according to the L1 of an author is described in a paper by [START_REF] Tomokiyo | You're not from 'round here, are you'? Naïve Bayes detection of non-native utterance text[END_REF], which aimed at distinguishing between Chinese and Japanese learners of English. Further studies focusing on other L1 backgrounds of learners of English followed 2 The term Native Language Identification is also used synonymously by some authors in this field. When investigating transfer, however, the notion of L1 (or first language) is more adequate as it refers to language dominance rather than sequential exposure to language. In addition, the notion of L1 supports a flexible conception of a person's language competence. Thus, particularly in multilingual contexts, a person might grow up with more than one native language that can be perceived differently in terms of their proficiency or dominance. Throughout the course of one's life, proficiency and dominance of a language can shift or be flexible depending on changing usage contexts or certain situations of use. The notion of (shifting) L1 describes such dynamic situations whereas the term native language mainly refers to the language a speaker is first exposed to in life. over the next few years [START_REF] Koppel | Determining an author's native language by mining a text for errors[END_REF][START_REF] Estival | Author profiling for English emails[END_REF][START_REF] Tsur | Using classifier features for studying the effect of native language on the choice of written second language words[END_REF][START_REF] Wong | Contrastive analysis and native language identification[END_REF]. These studies were mostly targeted at experimenting with different types of textual features to optimize the results of computational L1 classification. Apart from an occasional mention of L1 patterns that occurred in the different classification experiments (cf. e.g. [START_REF] Wong | Exploiting parse structures for Native Language Identification[END_REF], these studies did not explicitly consider the role of L1 transfer in automated classifications. Jarvis and Crossley (2012) The study by [START_REF] Jarvis | Detecting L2 writers' L1 on the basis of their lexical styles[END_REF] is based on a corpus of English texts written by 446 foreign-language learners of English from five L1 backgrounds (Danish, Finnish, Portuguese, Spanish, and Swedish). The texts are prompted by a sequence taken from a Charlie Chaplin silent movie. Relying on Linear Discriminant Analysis (for details see [START_REF] Mclachlan | Discriminant Analysis and Statistical Pattern Recognition[END_REF], the authors take a lexical approach to text classification. In detail, they select the 30 most frequent words in the texts of each L1 group. Overlap between the words reduces the final feature set for their classifier to a total of 53 function and content words. The particular distributions of these 53 words in the learner texts as determined by a stepwise feature selection integrated in standard 10-fold cross validation results in a classification accuracy of 76.9%. Among the words that have the most discriminatory value, the usage of the determiners a and the indicates L1 influence. Thus, the fact that Finnish lacks articles leads to a significantly lower use of articles in Finnish learner English while the wider distribution of the definite article in Spanish and Portuguese induces a relative overuse of the in comparison to Danish and Swedish speakers of English (Jarvis, Castañeda-Jiménez, and Nielsen 2012: 61).

In a second study, [START_REF] Jarvis | Exploring the role of n-grams in L1 identification[END_REF] further explore the role of lexical patterns for L1 identification. This time the authors rely on learner texts in ICLE and expand the range of L1 backgrounds to twelve languages.

Lexical n-grams are selected as features for text classification. Jarvis and Paquot consider the 200 most frequent lexical 1-grams (i.e. single words) and the multiword combinations of the 200 most frequent lexical 2-grams, lexical 3-grams, as well as the 122 most frequent 4-grams found in the data.

Their results show that, first of all, classification by lexical 1-grams is much more accurate than classification by multiword combinations. Secondly, while a combination of 1-grams with multiword n-grams shows consistently better results, only the combined use of unigrams and bigrams leads to a significant improvement of classification results, with the highest accuracy of 53.6% (2012: 91). When considering lexical n-grams that are powerful indicators of L1 differences, the authors provide some evidence for their possible relation to L1 transfer. The bigram, we can, for example, is typically overused by Spanish and Italian learners of English because of the wider usage scope of the Spanish and Italian modals poder and potere.

Furthermore, the bigram going to is highly indicative of Spanish learners in the selected ICLE texts. In this case, Spanish has a similar construction to mark futurity, ir a+ infinitve (2012: 96-97).

The study by [START_REF] Crossley | Detecting the first language of second language writers using automated indices of cohesion, lexical sophistication, syntactic complexity and conceptual knowledge[END_REF] uses the more abstract textual features of cohesion, lexical sophistication, syntactic complexity, and conceptual knowledge to construct a computational model that is tested on 900 argumentative essays from ICLE written by learners of English from four L1 backgrounds (Czech, German, Finnish, and Spanish). While their model shows a success rate of 66% in correctly predicting L1, the bundle of measures used to discriminate between the learner groups is more difficult to interpret in terms of L1 transfer effects.

Similarly, the approach taken by [START_REF] Bestgen | Error pattern and automatic L1 identification[END_REF] of using error patterns for automated L1 identification emphasizes the fact that transfer is not the only reason for differences between groups of learners. The authors apply seven error domains as features for classification, which yields an accuracy of 65% in the error tagged subset of ICLE (consisting of 223 learner essays). At the same time, the authors stress the importance of controlling for learner proficiency in line with the observation that language learners rely less on (negative) transfer the higher their level of proficiency (cf. e.g. [START_REF] Taylor | The use of overgeneralisation and transfer learning strategies by elementary and intermediate students of ESL[END_REF].

Apart from these studies on the relation between automated L1 classification and transfer, research on L1 identification has seen a recent boost due to an open call to participate in the first shared task in Native Language Identification (cf. [START_REF] Tetreault | A report on the first Native Language Identification shared task[END_REF]. 29 teams participated in the shared task and many of the individual solutions for L1 identification are gathered in the Proceedings of the Eighth Workshop on Innovative Use of NLP for Building Educational Applications.

As described in more detail in Section 3, the shared task was based on the TOEFL11 corpus (cf. [START_REF] Blanchard | TOEFL11: A Corpus of Non-Native English[END_REF], which was specifically designed to meet the demands of automated L1 identification. This makes TOEFL11 better suited to the task than the comparably smaller ICLE corpus (Tetreault, Blanchard, and Cahill 2013: 48).

Considering the overall results in the task, the best classification accuracies ranged between 80% and 84%, which was achieved by the submissions of 13 teams (Tetreault, Blanchard, and Cahill 2013: 53). Among these submissions, lexical features played a key role for successful classifications. Thus, the authors obtaining the highest accuracy score in the This is the postprint version (author accepted manuscript), i.e. the draft of the article reflecting any changes made in the peer review process, of DOI: 10.1075/hsld.4.13ste <http://dx.doi.org/10.1075/hsld.4.13ste>. The article is under copyright and the publisher should be contacted for permission to re-use or reprint the material in any form.

main task conclude from their results that "the most reliable L1 specificity in the TOEFL11 is to be found simply in the words, word forms, sequential word combinations, and sequential POS [part of speech] combinations that the nonnative writers produced" (Jarvis, Bestgen, and Pepper 2013: 117).

This observation emphasizes the fact that even if a whole range of parameters are used to train computer classifiers including lexical, syntactic, and stylistic features, as well as dependency parsers and grammatical errors, it is striking that high baselines of classification can be achieved by a simple combination of lexical n-grams and character n-grams using support vector machines (cf. Tetreault, Blanchard, and Cahill 2013: 54-56). Several studies report that, among a mix of features, lexical unigrams and bigrams contribute most to their classification accuracies accounting for baselines close to 80% (cf. [START_REF] Gebre | Improving Native Language Identification with TF-IDF Weighting[END_REF][START_REF] Wu | Simple yet powerful Native Language Identification on TOEFL11[END_REF], Brook and Hirst 2013).

The importance of lexical n-grams and character n-grams for successful L1 identification has also been shown in other research on different corpora (e.g. [START_REF] Ahn | Automatically Detecting Authors' Native Language[END_REF][START_REF] Van Halteren | Source language markers in EUROPARL translations[END_REF][START_REF] Tsur | Using classifier features for studying the effect of native language on the choice of written second language words[END_REF]. This leads to the conclusion that a speaker's L1 background influences her/his lexical choice in English, which, in turn, could be based on certain transfer effects from the L1.

In our paper, we would like to explore this relation further. For that, we first of all build a general computational model based on simple grammatical, orthographical, and lexical features for classifying English texts in TOEFL11 according to the L1 of their authors. The results of applying this model to the corpus are then analyzed to find the most distinctive features in the texts of L1 German and Italian learners of English.

These features are finally discussed for their potential to indicate L1 transfer in the English texts.

Methods

A few methodological issues lie at the core of every effort in automated L1 identification. This is, first of all, the design of the database or corpus used for the task. Moreover, performance in automated text classification is also dependent on the kind of computational classifier as well as on the type and amount of information which is applied to guide the classifier in making decisions on the L1 of language learners. Below, these aspects are addressed in the context of our study.

The design of TOEFL11

As mentioned in section 2, TOEFL11 has been compiled to meet the needs of automated L1 classification better than previously used corpora and collections of texts. Turkish [START_REF] Blanchard | TOEFL11: A Corpus of Non-Native English[END_REF]. The corpus comprises 1,100 English texts for each of the L1s and care has been taken to sample texts as evenly as possible among 8 topic prompts and three ratings given by human examiners for the learners' written proficiency levels (low / medium / high).

According to [START_REF] Blanchard | TOEFL11: A Corpus of Non-Native English[END_REF] 2011). However, as pointed out by Jarvis, Bestgen, and Pepper (2013: 113-114), TOEFL11 is not perfectly balanced for the number of essays per prompt and language. For example, the number of essays for prompt 64 is particularly low for German, Hindi, Italian, Telugu, and Turkish compared to the other languages (cf. Blanchard et al. 2013: 12). In addition, there is even more variability in the distribution of texts for proficiency level and language. In an ideal case, about 33% of all texts per language would cohere with one of the three proficiency levels (low / medium / high). However, Jarvis, Bestgen, and Pepper (2013: 113) point out that the distribution is highly skewed for a few languages. In general, most of the essays in all languages fall into the medium range of proficiency. By comparison, the number of texts rated as high is considerably smaller, and texts having low proficiency ratings are few and far between (cf. Blanchard et al. 2013: 13).

In the examples of L1 German and Hindi merely 1.4% and 2.5% of texts are rated as low compared with 61.5% (German) and 57.6% (Hindi) rated as high (cf. Jarvis, Bestgen, and Pepper 2013: 113). Despite these imbalances among prompts and proficiency levels, TOEFL11 remains the most extensive and balanced resource for L1 identification so far and could thus provide some interesting insight into characteristic patterns of L1 transfer in learners of English.

Automated classification and feature selection

The TOEFL11 data set has been prepared for applying machine learning (ML) algorithms as it is divided into a training set (9,900 texts), a development set (1,100 texts), and a test set (1,100 texts). All texts have been tokenized. For automatic classification and data analysis, we used the Scikit-learn Python package version 0.13 (Pedregosa et al. 2011). The ML algorithm (LinearSVC with standard parameter settings) was modeled on the development set of 1,100 texts, and its performance was tested with 10fold cross-validation on the larger set of 9,900 texts. The results of the classification for the eleven languages in the corpus are shown in Section 4.

Apart from the classification, we also wanted to take a closer look at the most discriminative features for the machine learning algorithm as these This is the postprint version (author accepted manuscript), i.e. the draft of the article reflecting any changes made in the peer review process, of DOI: 10.1075/hsld.4.13ste <http://dx.doi.org/10.1075/hsld.4.13ste>. The article is under copyright and the publisher should be contacted for permission to re-use or reprint the material in any form.

features represent L1-specific patterns in the English texts. It is interesting to investigate whether the most informative features for the ML algorithm can be related to L1-specific transfer effects that distinguish one group of learners of English from another one. For the scope of this paper, we focus In linguistic terms, our features relate to four different characteristics of the learner texts: 1) text surface features, 2) grammatical and discourse features, 3) orthographical features, and 4) derivational and lexical features.

Text surface features comprise the number of characters, digits, tokens (i.e.

words and punctuation marks), sentences, and paragraphs. In addition, we This is the postprint version (author accepted manuscript), i.e. the draft of the article reflecting any changes made in the peer review process, of DOI: 10.1075/hsld.4.13ste <http://dx.doi.org/10.1075/hsld.4.13ste>. The article is under copyright and the publisher should be contacted for permission to re-use or reprint the material in any form.

also measured the number of words with initial capital letters, with all capital letters as well as the number of sentences starting without a capital letter and the number of hyphenated words. The last two textual features were added as the observation of the sample texts indicated that writers of different L1 backgrounds differed in their use of capitalization. Checking the amount of hyphenated words relates in particular to learners of English of an L1 German background as it is sometimes observed that compounding in German more frequently involves hyphenization of its constituents compared to English and other language standards.

Among grammatical and discourse features, we took a lexical approach to identifying any patterns that could be indicative of L1 transfer.

This means that we considered specific lexical items and character combinations which are indicative of certain grammatical aspects, morphological forms, and discourse related features. Table 1 provides an overview of the grammatical and discourse features and their corresponding lexical and character combinations used in the automated text classification. 1 shows, an approach purely based on lexical and certain character string combinations allows capturing some of the peculiar grammatical and discourse related aspects of the English language. However, this approach also has some limitations. First of all, it is far from being exhaustive of grammatical and discourse characteristics of English. Secondly, the lexical mapping of grammatical and discourse features can also bear the danger that not all of the chosen indicators are actually representative of a specific grammatical or discourse pattern. In some cases there is also an overlap between the categories and their indicators. This, for example, occurs in the use of clitics and the Saxon genitive. In our study, we take the string <'s> as indicative of the possessive construction. However, the same string also designates the cliticized version of is or has, which has to be considered when interpreting results on <'s>. Similarly, counting the amount of <to> might not only be indicative of whether an L1 prefers verbal constructions over a nominal style, but it can also relate to the prepositional usage of to. In This is the postprint version (author accepted manuscript), i.e. the draft of the article reflecting any changes made in the peer review process, of DOI: 10.1075/hsld.4.13ste <http://dx.doi.org/10.1075/hsld.4.13ste>. The article is under copyright and the publisher should be contacted for permission to re-use or reprint the material in any form.

order to minimize the skewing of results when probing for the use of progressive aspect, we excluded some common words ending in <ing> from the results (e.g. thing, something, everything, according, evening, morning, sing, king, and so on). Furthermore, the lists of conjunctions/connectives, distributives/quantifiers, and intensifiers merely represent some common members of these categories. Neither are they to be regarded as closed and comprehensive lists, nor can all of the items be considered as only carrying this particular discourse function. An interpretation involving any of these categories will have to be made on an individual basis.

The limitations for the grammatical and discourse features also apply to some extent to the orthographical features and particularly to the items <a>, <an>, and <the>, each of which are counted individually.

Furthermore, a summary score was also calculated for all three articles and compared among the different learner populations.

With the exception of a few lexical items (e.g.

particular/particularly and special/especially), the lexical features in our classification scheme relate to the automatically generated set of n-grams

(2-grams to 5-grams) from the development set of the corpus. The complete list of 184 features included in the classification task can be found on the web (cf. note 5). These features are most informative for distinguishing the 11 languages in the development set. To highlight just a few characteristics of the automatically generated discriminators, it is notable that there is quite a substantial number of bigrams involving a punctuation mark and a lexical item (e.g. <. indeed>; <however ,>; <, i>; <, the>). In addition, the list consists only of bigram combinations with the exception of 8 trigrams (<in a group>; <a successful people>; <to conclude ,>; <now a days>; <knowledge of all>; <as i am>; <person who is>; <one specific subject>) and one 4gram (<. for example ,>). This outcome ties in with the findings by Jarvis and Paquot (2012), who report that lexical unigrams and bigrams contribute most to the accuracy of L1 identification of English learner texts.

For the analysis of the results in the next section, only the most significant observation-based and automated features are taken into account for classifying English texts written by L1 German and L1 Italian speakers.

Finally, it has to be emphasized that this approach of testing relevant This is the postprint version (author accepted manuscript), i.e. the draft of the article reflecting any changes made in the peer review process, of DOI: 10.1075/hsld.4.13ste <http://dx.doi.org/10.1075/hsld.4.13ste>. The article is under copyright and the publisher should be contacted for permission to re-use or reprint the material in any form.

features for classifying the L1 background of German and Italian learners is one that generates hypotheses on possible L1 transfer patterns. Ideally, each of the hypotheses would have to be empirically tested in follow-up studies.

Results

In this section, we would like to present two sets of results. Accuracies in classification and a confusion matrix will show the performance of our specific set of features in automatically detecting the L1 background of learner texts in TOEFL11. This is followed by an overview of the most informative features for classifying texts written by L1 Italian and L1

German learners of English.

Results of the classification task

The overall performance of the ML algorithm fed with our selection of 400 features on the training set of TOEFL11 is displayed in and recall. 7 The harmonic mean of precision and recall (i.e. the f1-score) is taken as the indicator of classification accuracy. The average f1-score across all languages represents the overall accuracy in L1 identification. On the whole, our classification system performed at an accuracy of 0.59, which means that 59% of all texts have been accurately identified according to their authors' L1 backgrounds from the pool of 11 languages. The results show that there is some variation in the accuracy of L1 classification as measured by f1-scores. Identifying L1 German and L1

Italian authors is most accurate while TOEFL essays written by Spanish

This is the postprint version (author accepted manuscript), i.e. the draft of the article reflecting any changes made in the peer review process, of DOI: 10.1075/hsld.4.13ste <http://dx.doi.org/10.1075/hsld.4.13ste>. The article is under copyright and the publisher should be contacted for permission to re-use or reprint the material in any form.

learners of English exhibit the lowest rate of identification. This can be interpreted as an indication that the selected set of features is particularly relevant for capturing L1 Italian and L1 German profiles in English learner texts; or, to put it in more cautious terms, we can say that English texts written by L1 German and L1 Italian learners in TOEFL11 are most likely to be discriminated from all other learner languages in the corpus according to the selected features for text classification.

To get a more precise picture of the classification results, it is interesting to consider the distribution of correctly and incorrectly assigned texts for each of the languages. This information is given in the confusion matrix shown in Figure 1. achieve the highest numbers of correctly identified texts. The confusion matrix also shows some interesting language family and areal effects among the learners' first languages represented in the corpus. Thus, automatic classification confuses English texts by Japanese and Korean learners to a great extent. Similarly, texts written by learners pertaining to the Romance language family show a higher number of misattributions among each other.

This is particularly noticeable in English texts composed by Italian and Spanish learners. Although they do not belong to the same language family, the areally related languages of Hindu and Telugu show the largest amount of mix-up in automatic classification. This is a token of their long history of intense language contact, which has led to some convergence between Indic and Dravidian languages (cf. Thomason 2001: 116). 8 Altogether, the emerging effects of language family and language contact in the confusion matrix emphasize the fact that the L1 backgrounds of learners of English leave an identifiable footprint in their use of the English language as represented in TOEFL® test essays. Since this footprint transcends the boundaries of individual languages and holds for learners of areally and typologically related languages, the hypothesis is strengthened that L1 transfer underlies some of the patterns that are helpful in automatic classification. In order to explore the role of transfer further, the next section This is the postprint version (author accepted manuscript), i.e. the draft of the article reflecting any changes made in the peer review process, of DOI: 10.1075/hsld.4.13ste <http://dx.doi.org/10.1075/hsld.4.13ste>. The article is under copyright and the publisher should be contacted for permission to re-use or reprint the material in any form.

will focus on important features for identifying L1 German and L1 Italian as they achieved the best results in the classification. For L1 German, 84 automatically generated lexical n-grams and 97 observation-based features turn out to be significant indicators (p<0.05).

Features for classifying

Similarly, 86 automatically generated lexical n-grams and 98 observationbased features achieve significance (p<0.05) for L1 Italian. The complete tables of significant features are available on the web (cf.note 5). For the sake of illustration, only the 50 most significant features for each L1 are shown in Table 3 and4 As can be gleaned from Table 3, both automatically generated lexical ngrams and observation-based features are quite evenly dispersed among the most highly significant indicators of L1 German. While the most significant lexical n-grams consist to a large extent of bigrams involving the combination of a punctuation mark and a lexical item, many of the observation-based features relate to grammatical and discourse phenomena such as articles, prepositions, pronouns, and certain discourse related lexical choices. There are also a few punctuation marks that emerge as peculiar features of L1 German. Moreover, merely formal features emerge as characteristics such as the number of characters, words (i.e. tokens), sentences, and paragraphs. The comparatively higher amount of each of these indicators merely emphasizes the fact that German learners of English have composed longer test essays than their peers from other L1 backgrounds. In turn, the reason why these purely formal features of the learner texts are relevant for automatic classification could be related to the This is the postprint version (author accepted manuscript), i.e. the draft of the article reflecting any changes made in the peer review process, of DOI: 10.1075/hsld.4.13ste <http://dx.doi.org/10.1075/hsld.4.13ste>. The article is under copyright and the publisher should be contacted for permission to re-use or reprint the material in any form.

composition of the TOEFL11 corpus as the selection of texts was not evenly balanced across proficiency levels.

In fact, when looking at the most significant features for classifying L1 Italian learner texts in Apart from the important, albeit opposite, effect of formal textual features for identifying L1 German and L1 Italian texts in the corpus, Table 4 shows that the classification of L1 Italian relies on rather different significant features than those relevant for L1 German. Thus, the informative features for automatic classification highlight different profiles of L1 German and L1 Italian learners of English. The next section will take a closer look at some of the relevant features for each learner group and discuss possible relations to L1 specific habits of language use.

Possible transfer effects from L1 German and L1 Italian

Before the features in Table 3 and4 that the relevance of the features can be dependent on the design of the corpus.

Despite these limitations, a few of the patterns identified as peculiar to L1 German and L1 Italian call for an explanation which makes a case for L1 influence in the use of written English. The ensuing discussion will highlight some of these candidate constructions and patterns without attempting to be exhaustive for all the features given in Table 3 and4. These might contain more features revealing L1 transfer.

Hypotheses of transfer from L1 German

To start with the peculiar features helping the automatic identification of L1

German in TOEFL11, the highest ranked indicator, the bigram <, that>, invites a straightforward explanation of transfer. Thus, German comma rules foresee the obligatory use of a comma in front of the equivalent final clause conjunction dass whereas commas are generally ruled out in front of the conjunction that in English. The same type of L1 influence is also evident in the bigram <, because>, which mirrors the German conventions of placing a comma in front of subordinating conjunctions. This, however, does not usually occur in English. The comparatively lower rate of <, and> is a further indication of L1 influence on comma use as it follows the German convention of not putting a comma in front of the coordinating conjunction in contrast to English.

This is the postprint version (author accepted manuscript), i.e. the draft of the article reflecting any changes made in the peer review process, of DOI: 10.1075/hsld.4.13ste <http://dx.doi.org/10.1075/hsld.4.13ste>. The article is under copyright and the publisher should be contacted for permission to re-use or reprint the material in any form.

Transfer of another orthographic convention is most likely at the root of the second most distinctive feature of L1 German texts in the corpus. The relative overuse of hyphens can be motivated by their common use as phrase connectors (i.e. as a dash, which is realized in the corpus data as a hyphen). On the other hand, there is no measurable effect concerning the occurrence of hyphens for connecting compound constituents.

Apart from orthographical transfer, a few instances of lexical usage reflect German lexical choices compared to learners of English from other L1 backgrounds. Ranked fourth in Table 3, the class feature <ESPECIALLY_VOC_all> combines the uses of the terms special and especially, both of which show a significantly higher rate in texts written by L1 German learners of English. This is most likely due to the fact that its German cognate form speziell is very frequently used in German, also in the function of a discourse marker. Similarly, the high relative frequency of the bigram <of course>, can be related to the very common German discourse marker natürlich, which literally translates as of course but is more versatile than its English equivalent. Another peculiar lexical construction which is quite highly ranked in However, it is difficult to argue for a transfer hypothesis in this case as the use of intensifiers and adverbials generally increases with higher proficiency in English as a learner language. Since there is a bias towards high level texts in the German component of TOEFL11, the higher rate of these adverbials compared to other L1 backgrounds might simply be a sampling effect of the corpus.

A case for a possible transfer can be made for the more frequent use of the conjunction or in texts of L1 German learners of English. While or is typically used in an exclusive sense in English, its German equivalent conjunction oder can also be used in a loosely coordinating sense similar to the function of und ('and') when connecting the final element in listings.

Another potential instantiation of transfer can be found in the elevated occurrence of indefinite articles and prepositions by German learners of English. However, the significance of these features might also be a consequence of the comparison between learner groups and might not show in comparison to L1 English speakers. This is due to the fact that the set of learner languages contains a few languages which lack definite and/or indefinite articles (e.g. Korean and Hindi; cf.

Hypotheses of transfer from L1 Italian

Among the indicators that make up the automatic feature profile of L1 learners of English. As with German learners of English, there is also evidence for some transfer of comma conventions by L1 Italian speakers, as indicated in the frequent use of the bigrams <, that> and <, because>. In a similar vein, <, but> appears as one of the most significant discriminators of L1 Italian texts. This most likely relates to the fact that the Italian equivalent conjunction ma is very versatile and frequently used in Italian, stimulating its relative overuse also in English argumentative essays.

The significantly higher rate of colons, brackets, and exclamation marks is difficult to motivate by an explanation involving transfer. It might be tempting to connect the higher rate of exclamation marks with a more emphatic style of argumentation; however, the lack of support from related indicators of the group of intensifiers does not allow any further speculation.

A clear indication of transfer on the orthographic level, on the other hand, can be gleaned from the prominence of clitics. This is not only indicated by the more frequent use of all clitics considered as such (<CLITICS_VOC_all> ) but also by the relatively high number of n-grams such as <' m>, <it ' s>, <n ' t>, and <' s>. As Italian regularly uses clitics in standard orthography, it seems as if Italian learners of English more readily embrace cliticized constructions even if they are marked as informal variants of their full forms in written English.

On the lexical level, a few significant indicators call for an Finally, two interesting hypotheses arise for transfer involving grammatical aspects. On the more speculative side, Italian learners of English show a significantly lower use of prepositions in TOEFL11.

Tentatively, this difference coheres with the characterization of Italian as a verb-framed language, where path and manner of motion is more likely to be encoded in the lexical verb. English and Germanic languages, by contrast, are described as satellite-framed languages, which rely more on prepositions and adverbials to encode path and manner of motion (cf. [START_REF] Talmy | Toward a Cognitive Semantics[END_REF][START_REF] Slobin | The many ways to search for a frog: linguistic typology & the expression of motion events[END_REF]). The hypothesis for potential L1 influence in this area would have to be explored in separate studies devoted to this aspect.

A stronger case for transfer can be made for the use of modals modal verbs of potere ('can / could') and dovere ('must / have to'). Thus, the results of the automatically generated feature profile of Italian learners gives numerical evidence that the expression of modality in English can be subject to transfer from Italian.

Conclusion

This article has explored the current topic of how texts written by learners of English can be automatically classified according to a learner's L1

  is the first volume that brings L1 transfer into the picture of text classification. The book includes five studies exploring different features of learner texts for automated classification. Four of these studies are based on texts taken from the International Corpus of English (ICLE), and one investigation focuses on written English narratives prompted by an excerpt from a Charlie Chaplin film. 3 The studies in the volume are similarly structured in that the individual research designs and the results of the classification procedures are presented before a final discussion highlights how some of the informative classification patterns are related to the L1 backgrounds of their authors.

  on the features which proved to be particularly indicative for L1 German and L1 Italian learners of English. In detail, the amount of a feature in the 900 texts each for German and Italian is compared to the remaining body of the TOEFL11 training set consisting of 9000 learner texts from the other ten L1 backgrounds. Thus, the informative features indicating either German or Italian L1 emerge from a comparison with their distribution in other learner texts and not with a comparison of texts by L1 English speakers. The informative features were ranked according to ANOVA F-score calculations provided by Scikit-learn. As discussed in Section 2, the type of features that are selected for training an ML algorithm are crucial for achieving a high accuracy in text classification. The most successful approaches to determining the L1 background in the shared task based on the TOEFL11 corpus (cf. Blanchard et al. 2013) used a combination of lexical n-grams (mostly from single words up to 5 word combinations) and character n-grams. While these features cover the characteristics of learner texts to a high degree, their results are often difficult to interpret in terms of possible transfer effects from a learner's L1. Since the detection of possible transfer effects is the aim of our study, we have opted for a mixed methodology of feature This is the postprint version (author accepted manuscript), i.e. the draft of the article reflecting any changes made in the peer review process, of DOI: 10.1075/hsld.4.13ste <http://dx.doi.org/10.1075/hsld.4.13ste>. The article is under copyright and the publisher should be contacted for permission to re-use or reprint the material in any form. selection combining introspection with automated extraction while keeping the overall amount of features low, not exceeding 400. In detail, introspective feature selection relied on observations in a sample of 30 texts per L1 background, which led to the formation of hypotheses on group specific patterns. Automatic feature extraction, on the other hand, drew on the results of n-grams which were generated from the development set of 1,100 texts. More specifically, all combinations of tokenized items in the texts (e.g. words and punctuation marks) were automatically computed for combinations of two tokens up to five tokens. In order to build the complete set of 400 features from these two different ways of selection, we first of all included all observation-based hypothetical features and added the most discriminating n-gram combinations, leading to an overall distribution of 216 observation-based and 184 automatically extracted features. For reasons of space, the complete lists of all the features used for automatic L1 identification are available on the web. 5

  derivational features selected for this study. The orthographical features consist primarily of the regular set of punctuation marks (<.>; <,>; <;>; <:>; <->; </>; <?>; <!>) and the amount of misspelled words per text as indicated by the widely used and freely available spell checker Hunspell (cf. http://hunspell.sourceforge.net/). The derivational features are based on the hypothesis that learners from a Romance L1 background might use more English words of historically Romance roots. This is why we added up the numbers of words ending in <ment>, <ion>, and <ize> as an indicator of Romance vocabulary in English.Whenever a single feature represents a category of features, we counted the single instances for each item and the summary score of all items in a category. For example, the category of article use consists of the This is the postprint version (author accepted manuscript), i.e. the draft of the article reflecting any changes made in the peer review process, of DOI: 10.1075/hsld.4.13ste <http://dx.doi.org/10.1075/hsld.4.13ste>. The article is under copyright and the publisher should be contacted for permission to re-use or reprint the material in any form.

Figure 1 :

 1 Figure 1: Confusion matrix of L1 classification in TOEFL11

  transfer effects emerging from automated classification, it is important to focus on the features that are most helpful for the classifier in discriminating L1 German and L1 Italian from the other languages in the corpus. Therefore, we carried out ANOVA F-score calculations for the 400 features of the classifier, comparing the relative amount and distribution of each feature in L1 German and in L1 Italian texts with the other 10 languages. All the features whose distributions show a significant difference for L1 German and L1 Italian are closely considered for whether they possibly reflect a particular pattern of language use in the L1 of the learners.

  . The features are ranked from 1 to 50 according to This is the postprint version (author accepted manuscript), i.e. the draft of the article reflecting any changes made in the peer review process, of DOI: 10.1075/hsld.4.13ste <http://dx.doi.org/10.1075/hsld.4.13ste>. The article is under copyright and the publisher should be contacted for permission to re-use or reprint the material in any form.their F-score, and their p-values are close to zero (p<0.01) indicating highly language specific effects for L1 German and L1 Italian.In addition to their score and ranking, the tables show the average rate of each feature in an L1 text (Num/900). This figure is compared to the average occurrence of the feature in a text pertaining to the other L1s in the corpus (Num/9000). To show the dispersion of a feature across the learner texts for L1 German and for L1 Italian, the tables give further information on the number and ratio of texts in which the feature occurs. The overall number of texts containing the feature is furthermore split into texts of a medium and of a high proficiency level. The rightmost column in each tableindicates the features, which appear as actual search strings or class names as shown in appendices 1 and 2. To differentiate between automatically generated n-gram features and the observation-based criteria, a difference has been made in the capitalization of the letter n (number) preceding the feature name: a small n flags the automatically generated token n-grams while a capital N signifies observation-based features.

  are discussed in terms of their possible grounding in L1 transfer, it is important to stress some limitations of this approach. First and foremost, an interpretation of the significant features for automatically classifying L1 German and L1 Italian texts can at best generate hypothesis of L1 transfer into English if a particular phenomenon can be related to an L1-specific pattern of language use. Secondly, the features arise from comparing learners of English from different L1 backgrounds and not from a comparison with L1 English speakers. This might skew the relevance of certain features which might not be informative for the automatic classifier if compared with L1 English texts. Finally, the general discussion of the results in the previous section has made it clear This is the postprint version (author accepted manuscript), i.e. the draft of the article reflecting any changes made in the peer review process, of DOI: 10.1075/hsld.4.13ste <http://dx.doi.org/10.1075/hsld.4.13ste>. The article is under copyright and the publisher should be contacted for permission to re-use or reprint the material in any form.

  explanation in terms of transfer. The overuse of <in fact> finds a model in the semantically close Italian expression infatti, used as a conjunction and This is the postprint version (author accepted manuscript), i.e. the draft of the article reflecting any changes made in the peer review process, of DOI: 10.1075/hsld.4.13ste <http://dx.doi.org/10.1075/hsld.4.13ste>. The article is under copyright and the publisher should be contacted for permission to re-use or reprint the material in any form. discourse marker. Interference of the Italian term is emphasized by numerous examples of the spelling infact found in texts by Italian learners of English. Boosts in the use of probably and particular/ly due to their Italian cognates of probabilmente and in particulare/particularmente are further candidates of lexical transfer.

among

  Italian learners in TOEFL11. In general, texts of L1 Italian learners show a markedly low rate of modal verbs as captured in the class feature <MODALS_VOC_all>. A more detailed look at the individual modals provides a diversified picture. The modals <may>, <might>, <would>, <should>, and <will> exhibit a significantly low rate whereas <must> and <could> are significantly overrepresented. This maps nicely onto the inventory of modal verbs in Italian, which essentially consists of the two This is the postprint version (author accepted manuscript), i.e. the draft of the article reflecting any changes made in the peer review process, of DOI: 10.1075/hsld.4.13ste <http://dx.doi.org/10.1075/hsld.4.13ste>. The article is under copyright and the publisher should be contacted for permission to re-use or reprint the material in any form.

  background. For this we have equipped an ML algorithm with a mixed set of features combining indicators based on observation and automatically generated n-grams. The overall set of 400 features was used on the TOEFL11 corpus, yielding an average classification accuracy of 59% of correct assignments to one of 11 different L1s. As pointed out above, this is not a very high accuracy rate compared with the thirteen best results of the NLI Shared Task that range between 80% and 84% of classification accuracy on the same dataset. Rather than tuning our machine learning algorithm for higher accuracy, we pursued the aim of investigating potential transfer effects. This, first of all, guided our limited selection of lexical features, and then made us test whether the most discriminating features for classifying L1 German and L1 Italian texts might take their origin in transfer from these languages. A discussion of the most significant features has highlighted a few specific patterns and habits of L1 use. At the same This is the postprint version (author accepted manuscript), i.e. the draft of the article reflecting any changes made in the peer review process, of DOI: 10.1075/hsld.4.13ste <http://dx.doi.org/10.1075/hsld.4.13ste>. The article is under copyright and the publisher should be contacted for permission to re-use or reprint the material in any form.time, explanations motivating these features due to the existence of model words, structures, and conventions in the L1 remain hypothetical claims for L1 transfer effects. It would be interesting to investigate these hypotheses further and to carry out additional empirical tests of their relevance. For the time being, evidence from the TOEFL11 corpus emphasizes the conclusion that learners of English from different language backgrounds indeed show distinguishable L1 profiles in their English prose. At least part of these profiles reflects L1 specific patterns of language use, highlighting the observation that transfer plays a substantial role.

  This is the postprint version (author accepted manuscript), i.e. the draft of the article reflecting any changes made in the peer review process, of DOI: 10.1075/hsld.4.13ste <http://dx.doi.org/10.1075/hsld.4.13ste>. The article is under copyright and the publisher should be contacted for permission to re-use or reprint the material in any form.

  This is the postprint version (author accepted manuscript), i.e. the draft of the article reflecting any changes made in the peer review process, of DOI: 10.1075/hsld.4.13ste <http://dx.doi.org/10.1075/hsld.4.13ste>. The article is under copyright and the publisher should be contacted for permission to re-use or reprint the material in any form.

	The compilers of the corpus describe TOEFL11 as
	consisting of short essays written during TOEFL® examinations in 2006
	and 2007 by learners of English of eleven L1 backgrounds: Arabic, Chinese,
	French, German, Hindi, Italian, Japanese, Korean, Spanish, Telugu, and

Table 1 :

 1 Grammatical and discourse features implemented in automated L1This is the postprint version (author accepted manuscript), i.e. the draft of the article reflecting any changes made in the peer review process, of DOI: 10.1075/hsld.4.13ste <http://dx.doi.org/10.1075/hsld.4.13ste>. The article is under copyright and the publisher should be contacted for permission to re-use or reprint the material in any form. This is the postprint version (author accepted manuscript), i.e. the draft of the article reflecting any changes made in the peer review process, of DOI: 10.1075/hsld.4.13ste <http://dx.doi.org/10.1075/hsld.4.13ste>. The article is under copyright and the publisher should be contacted for permission to re-use or reprint the material in any form.

	identification
	Grammatical /	Search strings
	Discourse features
	Adverbs	<ly> word finally

<otherwise>; <in this case>; <in that case>; <consequently>; <as a result>; <before>; <after>; <until>; <in order to>; <in order that> Clitics <'ll>; <n't>; <'m>; <'d>; <'ve>; <'re>;

Table 2 .

 2 Separate scores for each of the 11 L1 learner groups indicate the amount of successfully classified texts according to the standard measures of precision 6This is the postprint version (author accepted manuscript), i.e. the draft of the article reflecting any changes made in the peer review process, of DOI: 10.1075/hsld.4.13ste <http://dx.doi.org/10.1075/hsld.4.13ste>. The article is under copyright and the publisher should be contacted for permission to re-use or reprint the material in any form.

6

Precision is calculated as the number of correctly identified texts divided by the sum of correctly and incorrectly retrieved texts.

Table 2 :

 2 Accuracy of automated L1 identification in TOEFL11

	L1	Precision	Recall	F1-score	Number of texts
	Arabic	0.60	0.62	0.61	900
	Chinese	0.61	0.63	0.62	900
	French	0.61	0.57	0.59	900
	German	0.66	0.72	0.69	900
	Hindu	0.53	0.53	0.53	900
	Italian	0.62	0.66	0.64	900
	Japanese	0.60	0.60	0.60	900
	Korean	0.57	0.52	0.54	900
	Spanish	0.53	0.49	0.51	900
	Telugu	0.63	0.63	0.63	900
	Turkish	0.55	0.55	0.55	900
	Average/total	0.59	0.59	0.59	9900

Table 2 ,

 2 German and ItalianThis is the postprint version (author accepted manuscript), i.e. the draft of the article reflecting any changes made in the peer review process, of DOI: 10.1075/hsld.4.13ste <http://dx.doi.org/10.1075/hsld.4.13ste>. The article is under copyright and the publisher should be contacted for permission to re-use or reprint the material in any form.

Table 3 :

 3 The 50 most significant features (of 181) for classifying L1 This is the postprint version (author accepted manuscript), i.e. the draft of the article reflecting any changes made in the peer review process, of DOI: 10.1075/hsld.4.13ste <http://dx.doi.org/10.1075/hsld.4.13ste>. The article is under copyright and the publisher should be contacted for permission to re-use or reprint the material in any form. This is the postprint version (author accepted manuscript), i.e. the draft of the article reflecting any changes made in the peer review process, of DOI: 10.1075/hsld.4.13ste <http://dx.doi.org/10.1075/hsld.4.13ste>. The article is under copyright and the publisher should be contacted for permission to re-use or reprint the material in any form.

	German
	Rank F-	Num/	Num/	Num	Num	Num	Feature name
		score	900	9000	texts	texts	texts
						(med)	(high)
	1	538.88 0.56	0.13	283 / 0.31 112 / 0.33 167 / 0.30 n_, that
	2	253.05 0.40	0.08	165 / 0.18 50 / 0.15 113 / 0.21 N_-

Table 4

 4 , the same formal features indicating number of paragraphs, sentences, tokens, and characters pop up again. Only that this time Italian learners of English produce significantly shorter texts than the average across all other learner populations. A comparison of L1 German and L1 Italian shows the relation between text length and proficiency level. The set of 1,100 German texts in TOEFL11 consists of 15 low, 412 medium, and 673 high while L1 Italian is represented by 164 low, 623 medium, and 313 high (cf. Blanchard et al. 2013: 9).

Table 4 :

 4 The 50 most significant features (of 185) for classifying L1 Italian This is the postprint version (author accepted manuscript), i.e. the draft of the article reflecting any changes made in the peer review process, of DOI: 10.1075/hsld.4.13ste <http://dx.doi.org/10.1075/hsld.4.13ste>. The article is under copyright and the publisher should be contacted for permission to re-use or reprint the material in any form. This is the postprint version (author accepted manuscript), i.e. the draft of the article reflecting any changes made in the peer review process, of DOI: 10.1075/hsld.4.13ste <http://dx.doi.org/10.1075/hsld.4.13ste>. The article is under copyright and the publisher should be contacted for permission to re-use or reprint the material in any form.

	Rank F-	Num/	Num/	Num texts Num	Num	Feature name
		score	900	9000	texts	texts
					(med)	(high)
	1	640.29 1.07	0.35	522 / 0.58 328 / 0.64 125 / 0.48 n_think that
	2	551.19 0.72	0.18	352 / 0.39 205 / 0.40 118 / 0.46 N_:
	3	483.16 1.32	0.55	578 / 0.64 365 / 0.71 138 / 0.54 n_i think
	4	451.86 11.92 15.94 900 / 1.00 516 / 1.00 258 / 1.00 N_.
	5	425.51 0.30	0.06	188 / 0.21 106 / 0.21 61 / 0.24 n_in fact
	6	388.55 12.92 16.67 900 / 1.00 516 / 1.00 258 / 1.00 N_SENTS
	7	273.53 0.24	0.04	139 / 0.15 89 / 0.17 32 / 0.12 N_'m
	8	195.69 0.91	0.48	475 / 0.53 277 / 0.54 143 / 0.55 n_, but
	9	186.30 0.48	0.16	224 / 0.25 141 / 0.27 52 / 0.20 n_it 's
	10	173.01 9.54	7.58	895 / 0.99 514 / 1.00 258 / 1.00 N_DEMONS_VO
							C_all
	11	168.43 1.65	0.88	513 / 0.57 315 / 0.61 123 / 0.48 N_CLITICS_VOC
							_all
	12	141.63 2.37	1.63	761 / 0.85 442 / 0.86 221 / 0.86 N_this

Table 3

 3 This is the postprint version (author accepted manuscript), i.e. the draft of the article reflecting any changes made in the peer review process, of DOI: 10.1075/hsld.4.13ste <http://dx.doi.org/10.1075/hsld.4.13ste>. The article is under copyright and the publisher should be contacted for permission to re-use or reprint the material in any form.

	is the bigram <a certain>, which translates
	literally from German ein gewisser/eine gewisse. Furthermore, the more
	frequent use of adverbials subsumed in the study under the label of
	intensifiers (<INTENSIFIERS_VOC_all>) is another lexical pattern that
	characterizes L1 German learners of English in the corpus. This is
	particularly evident in the items <still>, <even>, <just>, and <only>.

  This is the postprint version (author accepted manuscript), i.e. the draft of the article reflecting any changes made in the peer review process, of DOI: 10.1075/hsld.4.13ste <http://dx.doi.org/10.1075/hsld.4.13ste>. The article is under copyright and the publisher should be contacted for permission to re-use or reprint the material in any form.Finally, there is evidence of another possible transfer effect concerning the encoding of impersonal reference. In German, particularly in the genre of argumentative essays, general statements are frequently built around the use of the impersonal referent man which can be represented by using the pronoun you with impersonal reference in English. In this respect, it is quite striking to observe that texts written by L1 German learners of English show a significant overuse of the pronoun you and of its combinations in particular bigrams. In detail, automatic classification has established the following order of relevance among the significant features

	Dryer 2013a). For the use of
	prepositions, comparatively lower figures in texts from learners of Turkish,
	Telugu, Hindi, Korean, and Japanese L1 backgrounds falls in line with the
	observation that these languages use postpositions instead of prepositions
	(cf. Dryer 2013b).

containing you: <you have>; <if you>; <you>; <. you>; <you are>; <you can>; <that you>; <you do>; <you will>; <when you>. Some of these bigrams reverberate common combinations of modals and conjunctions with impersonal man, which are particularly used in argumentative prose such as wenn man ('if you'/ 'when you'), man kann ('you can'), dass man ('that you'), and man wird ('you will').

  This is the postprint version (author accepted manuscript), i.e. the draft of the article reflecting any changes made in the peer review process, of DOI: 10.1075/hsld.4.13ste <http://dx.doi.org/10.1075/hsld.4.13ste>. The article is under copyright and the publisher should be contacted for permission to re-use or reprint the material in any form.

	Italian texts in TOEFL11, a few can be related to Italian patterns, which
	shine through in the English essays. The bigrams <think that> and <i think>
	as well as the consistently more frequent occurrence of other features
	containing the first person pronoun (e.g. <and i>; <. i>; <my>; <in my>) are
	a token of a personal style in the argumentative texts written by L1 Italian

We would like to thank an anonymous reviewer for helpful comments on an earlier version of the paper.

So far, almost all research on L1-based text classification has focused on learners of English. A few exceptions are[START_REF] Aharodnik | Automatic Identification of Learners' Language Background based on their Writing in Czech[END_REF], who focus on learners of Czech, as well as[START_REF] Golcher | Stylometry and the interplay of topic and L1 in the different annotation layers in the Falko corpus[END_REF], who use the Falko corpus of German as a learner language.

Prompt 6: Do you agree or disagree with the following statement? The best way to travel is in a group led by a tour guide. Use reasons and examples to support your answer.

The set of features, the complete classification results, and the computational implementation will be freely available at https://bitbucket.org/commul/2013_nli-st after publication.

Recall represents the ratio of the number of correctly retrieved texts from the set of relevant texts.

Widespread multilingualism among learners of English in India might be a further factor heightening convergence between the learner populations.

the 49th Annual Meeting of the Association for Computational

This is the postprint version (author accepted manuscript), i.e. the draft of the article reflecting any changes made in the peer review process, of DOI: 10.1075/hsld.4.13ste <http://dx.doi.org/10.1075/hsld.4.13ste>. The article is under copyright and the publisher should be contacted for permission to re-use or reprint the material in any form.

Linguistics: Human Language Technologies, 180-189. Portland, Oregon, USA: Association for Computational Linguistics.


Praveen Kulkarni
email: praveen.kulkarni@technicolor.com

Joaquin Zepeda
email: joaquin.zepeda@technicolor.com

Frédéric Jurie

Patrick Pérez
email: patrick.perez@technicolor.com

Louis Chevallier
email: louis.chevallier@technicolor.com

Frederic Jurie
email: frederic.jurie@unicaen.fr

Learning the Structure of Deep Architectures Using L1 Regularization

come

Introduction

Since Krizhevsky et al. [START_REF] Krizhevsky | ImageNet Classification with Deep Convolutional Neural Networks[END_REF] demonstrated the outstanding results that can be obtained in image classification by using Deep Neural Networks (DNNs), the popularity of DNNs has exploded. DNN methods have indeed resulted in very large increases in performance on a wide range of image classification datasets, including large scale datasets such as ImageNet [START_REF] Krizhevsky | ImageNet Classification with Deep Convolutional Neural Networks[END_REF], and, by means of transfer learning, smaller datasets such as PascalVOC 2007/2012 [START_REF] Oquab | Learning and Transferring Mid-Level Image Representations using Convolutional Neural Networks[END_REF], SUN397 [START_REF] Gong | Multi-scale orderless pooling of deep convolutional activation features[END_REF] and MIT Indoor datasets [START_REF] Cimpoi | Deep convolutional filter banks for texture recognition and segmentation[END_REF][START_REF] Gong | Multi-scale orderless pooling of deep convolutional activation features[END_REF].

DNNs consist of concatenations of standard layers. The first several layers are usually convolutional layers consisting each of n j (with j the layer index) spatially-convolutional kernels that operate on the n j-1 dimensional spatial signals output by the previous layer. Interspersed between these layers are normalization layers and spatial max-pooling layers that can be seen as non-linear convolutional operators. The normalization layers process a single spatial position and effectively balance kernel output energy across space. The maxpooling layers reduce the spatial support of the signal by max-pooling signals in small spatial neighborhoods. Given the convolutional nature of all these operators, they can process input images of arbitrary dimensions.

The latter layers of DNN architectures are instead fully connected layers that require inputs of fixed size. This constraint on input size propagates down the convolutional layers, effectively fixing the DNN architecture's expected input image size (sizes around 225 × 225 are common [START_REF] Jia | Caffe : Convolutional Architecture for Fast Feature Embedding[END_REF][START_REF] Krizhevsky | ImageNet Classification with Deep Convolutional Neural Networks[END_REF]). In this respect, the convolutional layers of DNN architectures can be seen as very large fully connected layers that have been constrained to have a weights matrix that is structured and highly sparse, effectively regularizing the architecture.

One important consideration when designing DNN architectures is the choice of weights matrix size across the various Fully Connected Layers (FCLs). Besides being another important means of regularization, the size of the FCL weight matrices has a strong impact on system complexity. The first fully connected layer, in particular, can account for 90% of the number of coefficients in the DNN [START_REF] Krizhevsky | ImageNet Classification with Deep Convolutional Neural Networks[END_REF]. When using pre-learned DNNs as generic image feature extractors [START_REF] Chatfield | Return of the Devil in the Details: Delving Deep into Convolutional Nets[END_REF][START_REF] Gong | Multi-scale Orderless Pooling of Deep Convolutional Activation Features[END_REF][START_REF] Sharif Razavian | CNN Features off-the-shelf : an Astounding Baseline for Recognition[END_REF], rectangular weights matrices further have the potential advantage of producing reduced-size feature vectors [START_REF] Chatfield | Return of the Devil in the Details: Delving Deep into Convolutional Nets[END_REF][START_REF] Kulkarni | Max-Margin, Single-Layer Adaptation of Transferred Image Features[END_REF]. But, up to now, the approach used to select the dimensions of the rectangular matrices across the various layers has been empirical, and researchers have mostly focused on using constant sizes across all fully connected layers.

The main contribution of the present work is hence to show that the sizes of the FCL weight matrices can be selected as a part of the supervised DNN learning procedure. We do this by inserting a diagonal matrix D j between layers ( j, j + 1), accordingly penalizing the DNN learning objective with the sparsity inducing 1 norm on the diagonal coefficients of each D j . Our method can be seen as formalizing the tradeoff between the generalization power of the model and its storage/computation requirements, as represented by the FCL weight matrix sizes. We then show experimentally that it is indeed possible to choose optimal FCL weight matrix sizes and that these vary with the layer index. Our experiments further show that the approach results not only in smaller feature vectors, but also in higher image classification performance.

The remainder of this paper is organized as follows: in the next section, we present a review of DNN methods that are related to our work. In Section 3, we present our proposed method, subsequently evaluating it experimentally in Section 4. We then provide some concluding remarks in Section 5.

Background

Given the large number of free parameters in DNN architectures, regularization is an important consideration when learning deep architectures, and various works have explicitly addressed it. One very successful approach currently deployed in publicly available DNN learning algorithms [START_REF] Jia | Caffe : Convolutional Architecture for Fast Feature Embedding[END_REF] is dropout [START_REF] Srivastava | Dropout : A Simple Way to Prevent Neural Networks from Overfitting[END_REF]. Dropout aims to prevent neighboring units from memorizing training samples. This is accomplished by randomly zeroing a subset of the activation values at the output of each fully connected layer, choosing a different random subset for each training example. The end result is that a different effective training set is used for neighboring weights. A related approach, DropConnect, zeros the FCL weights instead of the activation coefficients [START_REF] Wan | Regularization of Neural Networks using DropConnect[END_REF]. Other regularization approaches instead consist of using unsupervised learning either as an initializing stage before a second, strongly supervised stage, or in a mixed supervised/unsupervised approach [START_REF] Goh | Top-Down Regularization of Deep Belief Networks[END_REF].

A related line of work consists of pre-learning an entire architecture on a large, generic image dataset and then adapting the resulting architecture to a new target dataset. The approach of [START_REF] Chatfield | Return of the Devil in the Details: Delving Deep into Convolutional Nets[END_REF], for example, adapts the entire architecture by continuing the learning process at a reduced learning rate using the samples from the new target dataset. In [START_REF] Oquab | Learning and Transferring Mid-Level Image Representations using Convolutional Neural Networks[END_REF], the adaptation is instead carried out by entirely re-learning the last two layers on the new target dataset. A similar idea consists of using the activations of the penultimate layer of a pre-learned architecture as an image feature. When used for image classification, SVM classifiers are then learned on top of these features [START_REF] Sharif Razavian | CNN Features off-the-shelf : an Astounding Baseline for Recognition[END_REF], and the collection of such linear classifiers can be seen as a single fully connected adaptation layer. Linear classifiers have also been used in place of the soft-max classifier when learning either the entire architecture [START_REF] Chatfield | Return of the Devil in the Details: Delving Deep into Convolutional Nets[END_REF], or along with one other fully-connected adaptation layer [START_REF] Kulkarni | Max-Margin, Single-Layer Adaptation of Transferred Image Features[END_REF].

Various authors have also considered DNN variants of classical approaches including the ubiquitous spatial pyramid [START_REF] Lazebnik | Beyond Bags of Features : Spatial Pyramid Matching for Recognizing Natural Scene Categories[END_REF], the Fisher kernel [START_REF] Florent Perronnin | Improving the fisher kernel for large-scale image classification[END_REF] and bag-of-words [START_REF] Sivic | Video Google: A text retrieval approach to object matching in videos[END_REF]. The approach of [START_REF] Kulkarni | Hybrid Multi-Layer Deep CNN / Aggregator Feature for Image Classification[END_REF], for example, consists of treating the n j -dimensional spatial signals at the output of the j-th layer as a densely extracted local descriptor, and then building an aggregated representation such as a bag-of-words or a Fisher vector on top of these local descriptors.

The work of [START_REF] He | Spatial Pyramid Pooling in Deep Convolutional Networks for Visual Recognition[END_REF] uses a Spatial Pyramid Pooling (SPP) layer between the last convolutional layer and the first fully-connected layer. This should make it possible to use input images of arbitrary size, as the SPP layer maps the arbitrarily-sized output from the last convolutional layer to a vector of constant size compatible with the subsequent fully connected layer. In practice, however, the approach is implemented using a max-pooling layer with large stride.

The approach presented in [START_REF] Gong | Multi-scale Orderless Pooling of Deep Convolutional Activation Features[END_REF] consists of using a DNN as a local feature extractor by treating each patch from a dense sampling of image patches as an image. The activation features resulting from each patch are then treated as local descriptors to build an aggregated, global feature vector. A similar approach is presented in [START_REF] Girshick | Rich feature hierarchies for accurate object detection and semantic segmentation[END_REF]: given a large number of region proposals derived from the input image, the method extracts CNN activation features for each region and classifies them into given set of classes using linear classifiers. Approaches such as that of [START_REF] Girshick | Rich feature hierarchies for accurate object detection and semantic segmentation[END_REF][START_REF] Gong | Multi-scale Orderless Pooling of Deep Convolutional Activation Features[END_REF] that use DNNs as local feature extractors suffer from a very large computational complexity, and could hence benefit from complexity constrained DNNs such as the ones presented herein.

Learning the structure of deep architectures

In this section we present our proposed approach, illustrated in Fig. 1. The architecture we consider consists of a sequence of fully-connected layers, with a diagonal matrix between them. We will constrain the diagonal matrix to have a sparse diagonal, and this will implicitly define the size of the weights matrices of each layer. Rather than using the standard soft-max classification layer as the last layer, we will use a bank of linear SVM classifiers similarly to the approaches in [START_REF] Chatfield | Return of the Devil in the Details: Delving Deep into Convolutional Nets[END_REF][START_REF] Kulkarni | Max-Margin, Single-Layer Adaptation of Transferred Image Features[END_REF].

Constraining layer complexity

Formally, we can express the architecture in Fig. 1 as a concatenation of units of the following form:

f j (x) = D j M j x + b j + , (1)
where [z] + = [max(0, z i )] i is the commonly used Rectified Linear Unit (ReLU) non-linearity, here applied to a vector z = [z i ] i . Input vector is n j-1 -dimensional and output is n j -dimensional. This layer is defined by n j -dim vector b j , n j -dim diagonal matrix D j and matrix M j of size n j × n j-1 . A deep architecture can be derived from (1) using the standard stacking approach. Letting • denote the composition operator such that f • g(x) = f (g(x)), this can be denoted as

f J • . . . • f 1 (x), (2)
where, in this case, the vector x denotes the representation of the image at the input of the architecture. The image representation can consist of a direct re-ordering of the RGB values in the image [START_REF] Chatfield | Return of the Devil in the Details: Delving Deep into Convolutional Nets[END_REF][START_REF] Krizhevsky | ImageNet Classification with Deep Convolutional Neural Networks[END_REF], or it can be a feature derived from the image [START_REF] Kulkarni | Max-Margin, Single-Layer Adaptation of Transferred Image Features[END_REF][START_REF] Oquab | Learning and Transferring Mid-Level Image Representations using Convolutional Neural Networks[END_REF], which is the approach we follow in the present work. We are interested in the case when the diagonal entries of D j are sparse. When this is the case, the corresponding rows of M j and b j can be removed, as well as the corresponding columns of M j+1 . To see this, let I denote the support (indices of non-zero positions) of the diagonal entries of D j . Let A I,. , A .,I and A I,I denote, respectively, the sub-matrices derived from matrix A by retaining respectively the rows, the columns and both at positions indexed by I. After being processed by the weights matrix M j+1 of the next layer, the expression in (1) becomes

f j+1 (x) = M j+1 .,I D j I,I M j I,. x + b j I + + b j+1 I + . (3)
In this sense, the sparsity of the diagonal of D j encodes the computational complexity of the system, as it selects the effective dimensions of the M j matrices and the b j vectors.

Problem formulation

The architecture in Fig. 1 consists of a large number of parameters. Besides the variables M j , D j , b j associates to each layer j = 1, . . . , J in (1), one needs to learn the vectors w 1 , . . . , w K that define the SVM classifiers for the K classes. We will learn these variables from an annotated training set comprised of N training images x i , i = 1, . . . , N, each with K labels y k i ∈ {-1, 1}, k = 1, . . . , K indicating whether image i belongs to class k or not. Given such a training set, our approach consists of minimizing the following objective over all the variables {(M j , b j , D j )} J j=1 and all the classifiers {w k } K k=1 :

1

K K ∑ k=1 w k 2 2 + C N N ∑ i=1 l y k i ( f J • . . . • f 1 (x i )) w k + δ J ∑ j=1 D j * + µ J ∑ j=1 M j 2 F . (4)
In the above expression, we have used (i) l(x) to denote the hinge loss, given by max(0, 1x); (ii) D * to denote the trace norm, given by ∑ i |D ii | for the case of diagonal D; and (iii) M 2 F to denote the squared Frobenius norm ∑ i j M 2 i j . To illustrate the motivation behind this learning objective, we note first that the terms inside the summation over k in (4) are recognizable as an SVM objective for class k, where the scalar C is the SVM regularization parameter. The feature vectors used within this SVM objective are given by f J • . . . • f 1 (x i ), which depends on {(M j , b j , D j )} J j=1 . Hence we are learning the classifiers jointly with the feature extractor used to represent the input images. A similar approach has been used in [START_REF] Sydorov | Deep Fisher Kernels -End to End Learning of the Fisher Kernel GMM Parameters[END_REF] in the context of Fisher vector encoders to learn the encoder's GMM parameters under a discriminative objective.

The two regularization terms comprised of summations over j in (4) serve multiple purposes. One first purpose is to keep the SVM terms from decreasing indefinitely. Recall that the aim of an SVM objective is to maximize the margin between positive and negative examples. If it were not because of the penalty terms w k 2 2 , it would be possible to minimize this indefinitely by multiplying the linear classifiers by a very large scalar. The penalty terms on the D j and M j serve a similar purpose when learning the features jointly with classifiers.

A second important purpose is to automatically select the shapes of the weights matrices M j and b j . When applied to diagonal matrices such as D j , the trace norm is equivalent to an 1 norm computed from the diagonal vector of D j , and 1 norms are known to be wellbehaved (i.e., convex and differentiable almost everywhere) sparsity inducing norms. They are hence excellent surrogates for the 0 pseudo-norm that counts the number of non-zero entries of a vector. Since the matrices D j multiply corresponding M j and M j+1 matrices, low-valued coefficients of D j can be compensated with increased norm of rows in M j and columns in M j+1 . The penalty terms on the norm of the M j 's hence address this ambiguity.

Approaches other than the one presented in (4) and Fig. 1 are indeed possible. For example, it would be possible to dispense altogether of the matrices D j by using an alternative, structure inducing penalization on the matrices M j . The 1,2 matrix norm is an appealing alternative. Letting m i denote the transposed i-th row of M, it is given by

M 1,2 = ∑ i m i 2 , ( 5
)
and this is in turn an 1 penalization of the vector [ m i 2 ] i of 2 norms of the rows of M. As such, it forces entire rows of M to be zero. Yet in the context of learning problems such as ours, Stochastic Gradient Descent (SGD) optimization methods that process a single example at a time are a must. An adaption of SGD is thus required that processes one example at a time while retaining nonetheless the sparse structure. As we will see next, our approach (4) using diagonal matrices can accomplish this with a simple adaptation of SGD-based solvers for 1 penalized SVM problems [START_REF] Bottou | Stochastic gradient descent tricks[END_REF].

Learning approach

In order to derive an algorithm to minimize (4), we will first re-write it in a more convenient form using the following definitions:

r k,i = w k 2 2 +Cl y k i ( f J • . . . • f 1 (x)) w k , (6)
R i = 1 K K ∑ k=1 r k,i + δ J ∑ j=1 D j * + µ J ∑ j=1 M j 2 F , (7)
the resulting form of ( 4) is

1 N N ∑ i=1 R i . (8)
In order to minimize (8), we will employ a block-coordinate SGD approach wherein, for each sample i, we process each block of coordinates M 1 , D 1 , b 1 , . . . , M J , D J , b J , w 1 , . . . , w K successively. Letting θ denote a generic block of coordinates, the update step for that block at time instance t is as follows, where i t is a sample index drawn randomly at time t, and the coefficient γ t is the learning rate chosen using cross-validation:

θ t+1 = θ t -γ t ∂ R i t ∂ θ θ t . (9)
The required sub-gradient ∂ R i ∂ θ is given by

∂ R i ∂ θ = 1 K K ∑ k=1 ∂ r k,i ∂ θ + δ J ∑ j=1 ∂ D j * ∂ θ + µ J ∑ j=1 ∂ M j 2 F ∂ θ (10)
Expressions for ∂ r k,i ∂ θ when θ represents a classifier w k are readily available from the literature on SGD-based SVM solvers [START_REF] Bottou | Stochastic gradient descent tricks[END_REF][START_REF] Shalev-Shwartz | Pegasos : Primal Estimated sub-GrAdient SOlver for SVM[END_REF], and expressions for the case when θ represents a weights matrix M j or offset vector b j are available from the literature on deep learning [START_REF] Lecun | Efficient Back-Prop[END_REF]. The gradient of the squared Frobenius norm is just a rasterization of 2M j (whenever θ represents the corresponding block of coordinates M j ).

Concerning the gradient with respect to the matrices D j , it is possible to apply the update rule specified in [START_REF] Krizhevsky | ImageNet Classification with Deep Convolutional Neural Networks[END_REF] directly, but this will produce matrices D j with diagonals that are only approximately sparse. Instead, we will use a procedure adapted from 1 penalized SVM solvers [START_REF] Bottou | Stochastic gradient descent tricks[END_REF]. To this end, we represent each D j in terms of two non-negative vectors v j and u j :

D j = diag(v j ) -diag(u j ), where v j , u j ≥ 0. ( 11
)
In order to enforce the non-negativeness of the v j and u j , whenever we are optimizing over one of these blocks, we will follow the SGD update step in ( 9) by a projection into the set of non-negative vectors. The modified update step is given by

θ t+1 = θ t -γ t ∂ R i t ∂ θ θ t + . ( 12
)
Choice of learning rate. In order to make our algorithm converge at a fast rate, we will use an adaptive learning rate that gets updated and kept fixed for each batch of B samples. The learning rate is updated at the beginning of the batch using γ t = γ t-1 • 2 -n , where successive values of n = 0, 1, 2, . . . are tested until further increasing n no longer reduces the cost computed over a subset of the B samples from the batch. This approach has the advantage that the subset used to choose n is small, and hence adaptation is fast.

Early-stopping and choice of regularization parameters. We used two different earlystopping strategies that allowed us to select the number of iterations T (expressed as number of epochs) to use, both based on cross-validation. In one case we used the iteration that produced the highest mean Average Precision (mAP) over the validation set, while in the second case we chose the iteration giving the lowest cost, again computed over the validation set. We likewise use the validation set to choose the regularization parameters.

Results

In this section we evaluate our proposed learning algorithm and compare it against various state-of-the-art algorithms. To this end, we use the Pascal VOC 2007 dataset, which consists of 4192 test images and 5011 training images. We hold out 811 training images, choosing them uniformly over all classes, and use them as a validation set. As an image representation, we will use the VGG-M model of [START_REF] Chatfield | Return of the Devil in the Details: Delving Deep into Convolutional Nets[END_REF] which produces 128-dimensional features, accordingly using weights matrices of size 128 × 128.

Choice of regularization values Our learning algorithm is governed by three different regularization methods: the penalty weights µ and δ , and the number of training epochs T . The number of training epochs is determined using the validation set by computing either the (i) the validation mAP or (ii) the validation cost and choosing the number of training epochs that gives the best value. We found that using the validation mAP to determine T resulted in higher test mAP, but diagonal matrices D j that are not necessarily sparse. Using the validation cost to determine T , on the other hand, resulted in slightly lower mAP values but in much higher sparsities for the matrices D j . In Fig. 2 we illustrate the cross-validation method we use to choose the penalty weights µ and δ . The approach consists of keeping one penalty weight fixed while varying the second one, and then choosing the penalty weight that results in the highest validation mAP (this corresponded roughly to the value producing the highest test mAP).

Varying the number of layers J In Table 1, we evaluate the performance of our method as a function of the number of layers J in the architecture. We choose the regularization values following the procedure outlined above, using the validation cost to select the stopping point T . Note that our method succeeds in choosing sparse matrices D j while retaining a high test mAP. For J > 2, only the first layer results in a matrix D j with sparse diagonal. The reason for this is that the cross-validation procedure used to select δ in [START_REF] Gong | Multi-scale orderless pooling of deep convolutional activation features[END_REF] only takes the mAP into account.

In Fig. 3, we hence plot both the sparsity for all layers and the corresponding test and validation mAPs when varying the penalty weight δ . Note that increasing δ drastically increases the number of zero diagonal entries in the architecture while only slightly affecting the classification performance. For example, for δ = 2.5e -3 , close to 82% of the diagonal entries in all D j are zero, while the test mAP has only dropped by 4.5%. For δ = 8e-4, close to 40% of the diagonal entries are zero, while the system mAP is nearly unaffected. For completeness, in Fig. 4 we present a plot of layer sparsity as a function of the training epoch. Note that D 1 becomes sparse initially, and this reduces the intrinsic dimensionality of the signals at the input of the second layer, hence enabling D 2 to become sparse.

Comparison against state-of-the-art In Table 2 we compare our proposed method against various state-of-the-art algorithms derived from CNN methods. We include four reference methods that rely on data augmentation (the first four), and two reference methods that do not (the next two). The last three lines in the table correspond to three variants of our architecture. The first two have depth J = 1, 3 and are learnt with sparsity in mind by using a stopping criterion T selected using validation cost. The last one is learned using validation mAP to select the stopping criterion T . Note that, for J = 1, 3, our method produces very small features of size 35 and 36, respectively, while at the same time outperforming all the reference methods not-relying on augmentation, even when these use features many times larger. Our architecture with J = 6 results in a mAP value that outperforms not only the non-augmented references approaches, but also two of the four approaches relying on augmentation.

Conclusion

We present a method that automatically selects the size of the weight matrices inside fullyconnected layers comprising a deep architecture. Our approach relies on a regularization penalty term consisting of the 1 norm of the diagonal entries of diagonal matrices inserted between the fully-connected layers. Using such a penalty term forces the diagonal matrices to be sparse, accordingly selecting the effective number of rows and columns in the weights matrices of adjacent layers. We present a simple algorithm to solve the proposed formulation and demonstrate it experimentally on a standard image classification benchmark.

c 2015 .

 2015 The copyright of this document resides with its authors. It may be distributed unchanged freely in print or electronic forms. Pages 23.1-23.11 DOI: https://dx.doi.org/10.5244/C.29.23

Figure 1 :

 1 Figure 1: Proposed deep processing pipeline. Given an image representation, e.g., the output of the convolutional part of a pre-trained state-of-art DNN, J fully connected layers, each involving a diagonal matrix that controls its effective dimensions, are jointly learned with final linear SVM classifiers. Here, [z] + = [max(0, z i )] i is the commonly used Rectified Linear Unit (ReLU) non-linearity.

Figure 3 :

 3 Figure3: Effect of the penalty weight δ on (left) the number of zero diagonal entries of D j , j = 1, . . . , 4, and (right) on the classification performance as measured by mAP. The zero diagonal entries are presented as stacked plots so that the vertical displacement of any shaded regions corresponds to the number of zero diagonal entries of D j for the corresponding layer.

Figure 4 :

 4 Figure 4: Number of zero entries in diagonal of D j versus iteration number (expressed as number of epochs) for an architecture of J = 2 layers.

Table 1 :

 1 Using validation cost to choose the number of training epochs T , and validation mAP to choose the best δ first, and then the best µ.

		76
							76
	mAP	72 74				mAP	75
			Test mAP				74				Test mAP
		70	Valid. mAP								Valid. mAP
		1	2	3		4	1	1.2	1.4	1.6	1.8	2
			δ		•10 -3				µ		•10 -5
	Figure 2: Effect of the penalty weights δ and µ for a single-layer architecture, using valida-
	tion cost as a stopping criterion.
		J Test mAP Number of zeros in diagonal of D j	δ	µ	T
				j = 1	2	3 4 5	6
		1	76.38	93	-	---	-	8.0e-4 1.5e-5 120
		2	76.20	105	105 ---	-	1.4e-3 3.5e-5 180
		3	76.58	92	0	0 --	-	8.0e-4 1.0e-5 240
		5	76.55	91	0	0 0 0	-	8.0e-4 2.5e-5 360
		6	76.19	88	0	0 0 0	0	7.0e-4 1.4e-5 420

Table 2 :

 2 Comparison of our proposed method with various existing CNN methods. The training time indicated includes only the training time related to Pascal VOC, and not training time incurred when learning on ImageNet. The top four methods rely on some form of data augmentation and have training sets that effectively many times bigger than the PascalVOC training set. The bottom five methods (including ours) only use the training images specified in PascalVOC.

	Method	Train time Dim # params. mAP
	CNN S TUNE-RNK_aug[2]	-	4K ∼100M 82.42
	VGG-128_aug [2]	∼ 10s	128	2560	78.90
	off-the-shelf_aug[17]	-	4K	81K	77.2
	PRE1000C [15]	∼ 1 day	-	∼8.5M 77.73
	VGG-128 [2]	∼ 10s	128	2560	76.34
	off-the-shelf[17]	-	4K	81K	73.9
	Ours(J = 1)	210s	35	7040	76.38
	Ours(J = 3)	630s	36	9760	76.58
	Ours(J = 6)	1260s	128	100K 77.63