PARTIAL RULE MATCH FOR FILTERING RULES IN ASSOCIATIVE CLASSIFICATION

In this study, we propose a new method to enhance the accuracy of Modified Multi-class Classification based on Association Rule (MMCAR) classifier. We introduce a Partial Rule Match Filtering (PRMF) method that allows a minimal match of the items in the rule’s body in order for the rule to be added into a classifier. Experiments on Reuters-21578 data sets are performed in order to evaluate the effectiveness of PRMF in MMCAR. Results show that the MMCAR classifier performs better as compared to the chosen competitors.

INTRODUCTION
Associative Classification (AC) is a learning mechanism that mainly integrates association rule discovery and classification in data mining (Han, 2003). In classification task in data mining, given a set of labeled data, the objective is to build a classification model consisting of a set of rules in order to use it for predicting test cases. Hence, it is a typical supervised learning approach in which the target class is previously defined in the training data set and the aim is to guess the class for unseen data set. On the other hand, association rule discovers hidden relationships among products or items in a relational database such as sales promotion, shelving and planning (Niu et al., 2009). Many recent studies (Liu et al., 1999;Han, 2003;Thabtah et al., 2005;Li et al., 2008) give indications that AC is able to derive higher accurate models than classic classification approaches like KNN (Tan, 2005), rule induction (William, 1995) and decision trees (Quinlan, 1993). One reason of getting higher prediction accuracy by AC algorithms is the additional knowledge they discovered through association rule mining. Such an approach reveals possible joints between the items and the class values in the training data. Nevertheless, the massive number of rules generated by AC algorithms may be problematic in some cases as we will see later in this article.
There are many AC algorithms disseminated in literature in the last decade, such as CBA (Liu et al., 1999), CMAR (Li et al., 2001), CPAR (Han, 2003), MCAR (Thabtah et al., 2005), CACA (Tang and Liao, 2007), ACCF (Li et al., 2008), BCAR (Yoon and Lee, 2008), MAC (Abdelhamid et al., 2012) and CBAR (Han, 2003) PCBA (Chen et al., 2012). These techniques use different methods to discover the rules, sort the rules, store rules, filter out redundant rules and assigns the right class to test cases. AC algorithm such as CACA (Tang and Liao, 2007) or MCAR (Thabtah et al., 2005) discover rules according to two main parameters inherited from association rule named minimum support (minsupp) and minimum confidence (minconf). Meaning, when a ruleitem (item(s) along with its class) within the training dataset has the frequency larger than a predefined minsupp and minconf values, it becomes a rule. The algorithm then chooses one subset of the discovered rules to build a classifier that is able to predict the classes of new dataset (i.e., test data). One of the vital problems associated with AC approach is the very large number of rules inside its classifiers. This numerous number of rules exist as AC algorithms employ an association rule mining approach like Apriori Science Publications JCS or FP-Growth in discovering the rules from the input data set. For example, CBA, CACA, L3G and LC are known AC algorithms that employ Apriori-like learning methodologies during the training phase in which each ruleitem is tested in an iterative manner. In other words, the AC algorithm is going to compute the support of each ruleitem starting from those of size one and ending with those of size N. The outcome will be very large frequent ruleitems where many of them are converted into rules if they exceed the minconf value. This large set of rules may contain rules that are redundant, contradictory and/or overlap in the training examples, hence creating the need for filtering methods that treat these shortcomings to end up with a reasonable size classifier.
In this study, we propose a Partial Rule Match Filtering method (PRMF) to be employed in MMCAR (Yusof and Refai, 2013). The PRMF considers different scenarios when evaluating rules on the training data set during the process of constructing the classifier. This study is structured as follows: AC problem and its solution scheme are given in Section 2. Current prediction and rule filtering methods used in AC are reviewed in Section 3. Section 4 is devoted to present details on Partial Rule Match Filtering Method and the comparison results between PRMF and other classification methods are discussed in Section 5. Finally, the conclusion is given in Section 6.

The AC Problem and Related Definitions
According to (Thabtah et al., 2005), AC is a particular case of the association rule problem in which only the class attribute is considered in the rule's right hand side so for a rule like A→C, C is the class. Hereunder is the main related to definition to AC (Thabtah, 2007), where the input training data T has n attributes A 1 , A 2 ,…, A m and C is a set of classes. The size of T is denoted |T|.

Definition 1:
A training example in T can is a joint of attributes A i and values a ij , plus a class c j .

Definition 2:
An item is as a term name A i and a value a i , denoted <(A i , a i )>.

Definition 3:
An itemset is as a set of disjoint items contained in a training example, denoted < (A i1 , a i1 ), …, (A ik , a ik )>.

Definition 4:
A ruleitem r is of the form <itemset, c>, where cεC is the class.

Definition 5:
The occurrence (occr) of a ruleitem r in T is the number of example in T that match the items of r.

Definition 6:
The support count (suppcount) of ruleitem r is the number of example in T that match r's itemset and belong to the class c of r.

Definition 7:
The occurrence of an itemset i (occatt) in T is the number of rows in T that match i.

Definition 10:
Any ruleitem r that passes the minsupp threshold is said to be a frequent ruleitem.

Definition 11:
A rule is in the form: (A i1 ,a i1 ) ∧…∧ (A i1 ,a i1 )→c, where the left had side is an itemset and the right hand side is a class.
A classifier is a mapping form H: A→Y, where A is the set of ruleitems and Y is the set of class labels. The main task of AC is to construct a set of rules (model) that is able to predict the classes of previously unseen data, known as the test data set, as accurately as possible. In other words, the goal is to find a classifier hεH that maximizes the probability that h (a) = y for each test case.
Generally, the AC works as follow. First, all frequent ruleitems (1,2,…, N) that have frequencies in the training data set above the minsupp parameter are extracted. So an AC algorithm firstly finds frequent 1-ruleitems (ruleitems having a single item) in the first pass and then in each next pass, they start with ruleitems found to be frequent in the previous pass in order to generate possible frequent ruleitems involving more items. This means, frequent 1-ruleitems is the input for the process Science Publications JCS of discovering frequent 2-ruleitems and frequent 2ruleitems is the input for discovering frequent 3ruleitems and so forth.
When the complete set of frequent ruleitems are found, the AC algorithm checks their confidences and transform any of which pass the minconf parameter. Meaning a ruleitem that have confidence bigger than or equal the minconf is produced as a candidate rule. However, the number of rules extracted could be large and many of which are redundant. Therefore, rule filtering processes discard these redundant rules and a considerable number of rules might be removed at phase of building the classification model. Finally, rules that cover training cases and pass the filtering phase becomes part of the model that is laterally employed to assign class values to test data.

Rule Filtering Methods in Associative Classification
A number of rule filtering methods have been used in AC mining to reduce the number of rules in the produced classifiers. Some of these methods were taken from decision trees like Information Gain (Quinlan, 1993) and others from statistics such as weighted Chi-Square (Li et al., 2001). These methods are used during the construction of the model and sometimes in early phases especially during rule discovery. Throughout this section, we discuss filtering methods that are developed within AC mining and not adopted from statistics and machine learning. This is simply because we focus on removing rules during the step of building the model and not during frequent ruleitems discovery step.

Database Coverage Filtering
The database coverage is a filtering method used in CBA (Liu et al., 1999) and operates once the candidate rules have been created and sorted. This is when all frequent ruleitems that exceed the minconf value is transformed into rules and got sorted based on parameters such as confidence, support and rule length. The discovered rules are then evaluated on a training data set to check their effectiveness in covering the dataset. The database coverage evaluates rules in a top down manner starting from the first ordered rule and checks if the particular rule is able to cover at least one training example in the training data set. If so, the selected rule is inserted into the model and all examples covered by the rule are deleted from the training data set. The same process is repeated on the remaining candidate rules until all of the candidate rules are tested or no more uncovered example are left in the training data set. The database coverage method was used first by CBA (Liu et al., 1999) and then latterly by other AC algorithms, including CMAR (Li et al., 2001), ARC-BC (Antonie and Zaiane, 2002), CAN (Kundu et al., 2008), Multi-label Classification based on Association Rules and ACCF (Li et al., 2008).

Specific Rules Filtering
A rule filtering method that removes large and rules with less confidence value than general rules was developed in (Li et al., 2001) and laterally used in (Antonie and Zaiane, 2002). Once the rule generation process is finished and rules are sorted, the proposed rule filtering works as follows: For the candidate rules such as I′ → c from the set of produced rules, if there is some general rule I → c of a higher rank and I ⊆ I′ then I′ → c is removed. The specific rule deletion took place immediately after a rule is inserted into the compact data structure, the CR-tree within the CMAR (Li et al., 2001). When a rule is added to the CR-tree, a query is issued to check if the inserted rule can be filtered or some other existing rules in the tree can be removed.

General Rules Filtering
There are certain AC algorithms called lazy such as in (Baralis et al., 2004;) that prefer keeping massive rules for the sake of improving the classification accuracy of the classifiers. Such work believe that filtering should happen only on rules that lead to wrong classification during building the model. The main difference between lazy and database coverage is that rules which don't cover a training example are stored by the lazy AC algorithms in the memory whereas algorithms that employ database coverage completely remove such rules.

No Class Identically Filtering Method
Recently, an AC algorithm called MAC (Abdelhamid et al., 2012) proposed a new rule filtering method based database coverage. This method works as follows: For each sorted candidate rule and during building the classifier, starting with the first training example, look for the highest sorted rule that may cover it and without checking the class similarity of the candidate rule and the training example. If there are candidate rules that may cover the training example, mark the candidate rule and remove the training example. Repeat the process on the remaining examples in the training data set until it becomes empty. At that Science Publications JCS point, insert all marked candidate rules into the classification system and delete any unmarked rules. This method surely increases the rule coverage on training examples and reduces the size of the model since no class similarity is required as the database coverage and other filtering methods.

PARTIAL RULE FILTERING METHOD
Most of the current rule filtering methods in AC mining are based on database coverage in which they consider a candidate rule is part of the classifier when this rule correctly covers at least one training example during the classification development. Hence, there exist two conditions that must be met before a rule can be inserted into the classifier: • The candidate rule items (left hand side) must be within the items of training examples • The class of the candidate rule (right hand side) must be similar to the training example class Based on such approach, we argue on two main issues • Situations when there isn't any candidate rule(s) that covers the training case (no identical similarity). Currently, existing methods use the remaining unclassified training example to be converted as a default rule. Such an approach may raise higher error rate • The condition of having similar classes is unnecessary and can cause overlearning the training data by keeping greedily rules that maximizes the accuracy rate only on the training data without taken into account that the rules are not yet generalized for testing on unseen data which is the main goal of classification in data mining. We believe that by relaxing this constraint and merge it with the partly matching we can end up with a much smaller size of classification model. This can be achieved by allowing the candidate rule to cover more training examples and therefore many redundant lower sorted rules will be unmarked and thus deleted after the building the model step is finished Hereunder we present a rule filtering methods proposed by us in AC context. We assume that all candidate rules are extracted and sorted from highest to lowest using confidence, support and rule length criteria.
For each training data, PRMF finds the first rule that satisfies the training example by having all of the rule's items inside the training example. When the rule is found, the algorithm marks it and deletes the training example. However, when there isn't any rule that fully match the training example (don't have a body that could be inside the training example) PRMF takes on the first rule that partly covers the training example rather than leaving this example to be covered later by the default class rule. By doing this, PRMF rule filtering method minimizes the number of training examples that will be used to make the default rule. The main difference between the PRMF and of database like is that the proposed PRMF method includes not only full covered rules but also the partly covered rules into the model. In addition, existing filtering method consider class similarity between the training example and the candidate rule as an important condition to cover the training example.
Whereas the PRMF ignores the class similarity as it aims to reduce overlearning. In the remainder of this section we distinguish between our rule filtering method and those of MCAR and CBA using example. Consider Table 1 that shows candidate rules and Table 2 that lists six (6) training examples. Please note that the last two columns of Table 2 denotes the rule that have been used by our method and those of (MCAR, CBA) respectively. For the first training data (1), the proposed classifier and those of MCAR and CBA used rule number (RuleID 2). This is because there is a fully match between RuleID 2 and training data (#1). The same thing occurs for training data (#2) in which RuleID 1 has been used to cover the data. Though, for the third training data, the CBA and MCAR methods leave it for the default rule because there is no candidate rule to cover it. This is because none of the existing candidate rules matches with training data (#3). On the other hand, our classifier that employs PRMF uses the first partly match rule, which is RuleID 2 to cover training data (#3). The same scenario happens again for training data (#4) in which our classifier uses the partly match rule (#6) whereas other AC algorithms employs default rule. The above example shows the demonstration of the proposed rule filtering method that indeed reduces error by allowing partly matching rule to be part of the classifier instead on taking the default rule. All rules that have been applied during the classifier builder are inserted into the classifier whereas the remaining rules get deleted since they have no training data coverage. In summary, the proposed PRMF is as shown in Fig. 1. The input of the PRMF method is the training data (TranD) and discovered Rules Rank is (RuleR) and the output is classifier (C).

EXPERIMENT AND RESULTS
In this section, different traditional classification algorithms as well as rule-based classification algorithms are compared with MMCAR based on the prediction accuracy. The data used in the experiments is the Reuters-21578 (Lewis). The Reuters-21578 is the most commonly used data set in the text categorisation research. We used the ModApte version of Reuters-21578 that leads to a corpus of 9,174 documents consisting of 6,603 training and 2,571 of testing documents. The algorithms used in the comparison are CBA (Liu et al., 1999), BCAR (Baralis et al., 2004) and MCAR (Thabtah et al., 2005) from the associative classification approaches while Naïve Bayes (Lewis, 1998), K-NN (Tan, 2005) and SVM (Japkowicz and Stephen, 2002) represent the traditional approaches. We tested the proposed algorithm using the minsupp and minconf values of 2 and 40%, respectively. Table 3 shows the number of documents in training and testing sets per category (REUTERS-21578). Table 4 depicts a comparison results between the proposed algorithm against other well-known classifiers. It should be noted that the results of the BCAR algorithm is reported in (Yoon and Lee, 2008) while for MCAR the results were obtained via experiment.  7-0-0 5-0-2 4-1-2 6-0-1 4-0-3 5-0-2 Table 4 reveals that the proposed method has the highest accuracy for three of the dataset-Acq, Grain and Money-FX. With an average of 89.33%, it can be considered that the MMCAR employing PRMF shown an acceptable result as compared to other algorithms. This is due to the fact that the MMCAR obtains more number of winning as compared to other competitors. The results of a win-tid-lose record is depicted in Table  5. The three values (Win/lose/tie) record are respectively the number of datasets for which a method obtains higher, lower or equal classification accuracy, compared with an alternative method. For example, it is learned that MMCAR overcomes (win) the BCAR for 5 dataset and lost two, hence generating a values of 5-0-2. Figure 2 shows the "relative BEF rate" that denotes the variation in the accuracy rates of the proposed algorithm with reference to those resulting by the chosen competitors. In other words, it indicates, how good or bad MMCAR performs with reference to the competitors on the utilized datasets. The relative accuracy rate is obtained using the following relations Equation (1) where, Accuracy MMCAR is the accuracy rate of the proposed method and the Accuracy Other methods is the accuracy of other algorithms such as KNN, Naïve Bayes, SVM, MCAR, CBA and BCAR.

CONCLUSION
In this article, the problem of rule filtering in associative classification data mining has been investigated. The outcome is a Partial Rule Filtering Method which is employed in MMCAR Experimental results on Reuters-21578 indicated that our proposed method is highly competitive when compared with traditional classification algorithms such as SVM, KNN and Bayes in terms of prediction accuracy, win/lose/tie and relative BEF. Furthermore, our method scales well if compared with popular AC approaches like CBA, MCAR and BCAR with regards to breakeven point.


The RWTH Aachen German-English Machine Translation System for WMT 2014

This paper describes the statistical machine translation (SMT) systems developed at RWTH Aachen University for the German!English translation task of the ACL 2014 Eighth Workshop on Statistical Machine Translation (WMT 2014). Both hierarchical and phrase-based SMT systems are applied employing hierarchical phrase reordering and word class language models. For the phrase-based system, we run discriminative phrase training. In addition, we describe our preprocessing pipeline for German!English.

Introduction
For the WMT 2014 shared translation task 1 RWTH utilized state-of-the-art phrase-based and hierarchical translation systems. First, we describe our preprocessing pipeline for the language pair German→English in Section 2. Furthermore, we utilize morpho-syntactic analysis to preprocess the data (Section 2.3). In Section 3, we give a survey of the employed systems and the basic methods they implement. More details are given about the discriminative phrase training (Section 3.4) and the hierarchical reordering model for hierarchical machine translation (Section 3.5). Experimental results are discussed in Section 4.

Preprocessing
In this section we will describe the modification of our preprocessing pipeline compared to our 2013 WMT German→English setup.

Categorization
We put some effort in building better categories for digits and written numbers. All written numbers were categorized. In 2013 they were just handled as normal words which leads to a higher number of out-of-vocabulary words. For German→English, in most cases for numbers like '3,000' or '2.34' the decimal mark ',' and the thousands separator '.' has to be inverted. As the training data and also the test sets contain several errors for numbers in the source as well as in the target part, we put more effort into producing correct English numbers.

Remove Foreign Languages
The WMT German→English corpus contains some bilingual sentence pairs with non-German source or/and non-English target sentences. For this WMT translation task, we filtered all nonmatching language pairs (in terms of source language German and target language English) from our bilingual training set.
First, we filtered languages which contain nonascii characters. For example Chinese, Arabic or Russian can be easily filtered when deleting sentences which contain more than 70 percent nonascii words. The first examples of Table 1 was filtered due to the fact, that the source sentence contains too many non-ascii characters.
In a second step, we filtered European languages containing ascii characters. We used the WMT monolingual corpora in Czech, French, Spanish, English and German to filter these languages from our bilingual data. We could both delete a sentence pair if it contains a wrong source language or a wrong target language. That is the reason why we even search for English sentences in the source part and for German sentences in the target part. For each language, we built a word count of all words in the monolingual data for each language separately. We removed punctuation which are no indicator of a language. In our experiments, we only considered words with frequency higher than 20 (e.g. to ignore names). Given the word frequency, we removed a bilingual sentence pair from our training data if more than 70 percent of the words had a higher count in a different language then the one we expected. In Table 1 some example sentences, which were removed, are illustrated.
In Table 2 the amount of sentences and the corresponding vocabulary sizes of partial and totally cleaned data sets are given. Further we provide the number of out-of-vocabulary words (OOVs) for newstest2012. The vocabulary size could be reduced by ∼130k words for both source and target side of our bilingual training data while the OOV rate kept the same. Our experiments showed, that the translation quality is the same with or without removing wrong sentences. Nevertheless, we reduced the training data size and also the vocabulary size without any degradation in terms of translation quality.

Morpho-syntactic Analysis
In order to reduce the source vocabulary size for the German→English translation further, the German text is preprocessed by splitting German compound words with the frequency-based method described in (Koehn and Knight, 2003). To reduce translation complexity, we employ the long-range part-of-speech based reordering rules proposed by Popović and Ney (2006).

Translation Systems
In this evaluation, we employ phrase-based translation and hierarchical phrase-based translation. Both approaches are implemented in Jane (Vilar et al., 2012;Wuebker et al., 2012), a statistical machine translation toolkit which has been developed at RWTH Aachen University and is freely available for non-commercial use. 2 In the newest internal version, we use the KenLM Language Model Interface provided by (Heafield, 2011) for both decoders.

Phrase-based System
In the phrase-based decoder (source cardinality synchronous search, SCSS, Wuebker et al. (2012)), we use the standard set of models with phrase translation probabilities and lexical smoothing in both directions, word and phrase penalty, distancebased distortion model, an n-gram target language model and three binary count features. Additional models used in this evaluation are the hierarchical reordering model (HRM) (Galley and Manning, 2008) and a word class language model (wcLM) (Wuebker et al., 2013). The parameter weights are optimized with minimum error rate training (MERT) (Och, 2003). The optimization criterion is BLEU (Papineni et al., 2002).

Hierarchical Phrase-based System
In hierarchical phrase-based translation (Chiang, 2007), a weighted synchronous context-free grammar is induced from parallel text. In addition to contiguous lexical phrases, hierarchical phrases with up to two gaps are extracted. The search is carried out with a parsing-based procedure. The standard models integrated into our Jane hierarchical systems (Vilar et al., 2010; are: Phrase translation probabilities and lexical smoothing probabilities in both translation directions, word and phrase penalty, binary features marking hierarchical phrases, glue rule, and rules with non-terminals at the boundaries, three binary count features, and an n-gram language model. We utilize the cube pruning algorithm for decoding (Huck et al., 2013a) and optimize the model weights with MERT. The optimization criterion is BLEU.

Other Tools and Techniques
We employ GIZA++ (Och and Ney, 2003) to train word alignments. The two trained alignments are heuristically merged to obtain a symmetrized word alignment for phrase extraction. All lan-  (Stolcke, 2002) or with the KenLM language model toolkit (Heafield et al., 2013) and are standard 4-gram LMs with interpolated modified Kneser-Ney smoothing (Kneser and Ney, 1995;Chen and Goodman, 1998). We evaluate in truecase with BLEU and TER (Snover et al., 2006).

Discriminative Phrase Training
In our baseline translation systems the phrase tables are created by a heuristic extraction from word alignments and the probabilities are estimated as relative frequencies, which is still the state-of-the-art for many standard SMT systems.
Here, we applied a more sophisticated discriminative phrase training method for the WMT 2014 German→English task. Similar to (He and Deng, 2012), a gradient-based method is used to optimize a maximum expected BLEU objective, for which we define BLEU on the sentence level with smoothed 3-gram and 4-gram precisions. To that end, the training data is decoded to generate 100best lists. We apply a leave-one-out heuristic (Wuebker et al., 2010) to make better use of the training data. Using these n-best lists, we iteratively perform updates on the phrasal translation scores of the phrase table. After each iteration, we run MERT, evaluate on the development set and select the best performing iteration. In this work, we perform two rounds of discriminative training on two separate data sets. In the first round, training is performed on the concatenation of newstest2008 through newstest2010 and an automatic selection from the News-commentary, Europarl and Common Crawl corpora. The selection is based on cross-entropy difference of language models and IBM-1 models as described by Mansour et al. (2011) and contains 258K sentence pairs. The training took 4.5 hours for 30 iterations. On top of the final phrase-based systems, a second round of discriminative training is run on the full news-commentary corpus concatenated with new-stest2008 through newstest2010.

A Phrase Orientation Model for Hierarchical Machine Translation
In Huck et al. (2013b) a lexicalized reordering model for hierarchical phrase-based machine translation was introduced. The model scores monotone, swap, and discontinuous phrase orientations in the manner of the one presented by (Tillmann, 2004). Since improvements were reported on a Chinese→English translation task, we investigate the impact of this model on a European language pair. As in German the word order is more flexible compared with the target language English, we expect that an additional reordering model could improve the translation quality. In our experiments we use the same settings which worked best in (Huck et al., 2013b).

Setup
We trained the phrase-based and the hierarchical translation system on all available bilingual training data. Corpus statistics can be found in the last row of Table 2. The language model are 4-grams trained on the respective target side of the bilingual data, 1 2 of the Shuffled News Crawl corpus, 1 4 of the 10 9 French-English corpus and 1 2 of the LDC Gigaword Fifth Edition corpus. The monolingual data selection is based on crossentropy difference as described in (Moore and Lewis, 2010). For the baseline language model, we trained separate models for each corpus, which were then interpolated. For our final experiments, we also trained a single unpruned language model on the concatenation of all monolingual data with KenLM.

Experimental Results
The results of the phrase-based system (SCSS) as well as the hierarchical phrase-based system (HPBT) are summarized in Table 3. The phrase-based baseline system, which includes the hierarchical reordering model by (Galley and Manning, 2008) and is tuned on new-stest2012, reaches a performance of 25.9% BLEU on newstest2013. Adding the word class language model improves performance by 0.4% BLEU absolute and the first round of discriminative phrase training by 0.5% BLEU absolute. Next, we switched to tuning on a concatenation of new-stest2011 and newstest2012, which we expect to be more reliable with respect to unseen data. Although the BLEU score does not improve and TER goes up slightly, we kept this tuning set in the subsequent setups, as it yielded longer translations, which in our experience will usually be preferred by human evaluators. Switching from the interpolated language model to the unpruned language model trained with KenLM on the full concatenated monolingual training data in a single pass gained us another 0.3% BLEU. For the final system, we ran a second round of discriminative training on different training data (cf. Section 3.4), which increased performance by 0.1% BLEU to the final score 27.2.
For the phrase-based system, we also experimented with weighted phrase extraction (Mansour and Ney, 2012), but did not observe improvements.
The hierarchical phrase-based baseline without any additional model is on the same level as the phrase-based system including the word class language model, hierarchical reordering model and discriminative phrase training in terms of BLEU. However, extending the system with a word class language model or the additional reordering models does not seem to help. Even the combination of both models does not improve the translation quality. Note, that the hierarchical system was tuned on the concatenation newstest2011 and new-stest2012. The final system employs both word class language model and hierarchical reordering model.
Both phrase-based and hierarchical phrasebased final systems are used in the EU-Bridge system combination (Freitag et al., 2014).

Conclusion
For the participation in the WMT 2014 shared translation task, RWTH experimented with both phrase-based and hierarchical translation systems. For both approaches, we applied a hierarchical phrase reordering model and a word class language model. For the phrase-based system we employed discriminative phrase training. Additionally, improvements of our preprocessing pipeline compared to our WMT 2013 setup were described. New introduced categories lead to a lower amount of out-of-vocabulary words. Filtering the corpus for wrong languages gives us lower vocabulary sizes for source and target without loosing any performance.


extfieldsofstudy:
Computer Science
Mathematics

text:
Fundamental Limits of Caching: Improved Bounds For Small Buffer Users

In this work, the peak rate of the caching problem is investigated, under the scenario that the users are with small buffer sizes and the number of users is no less than the amount of files in the server. A novel coded caching strategy is proposed for such a scenario, leading to a lower peak rate compared to recent results in the literature. Furthermore, it is verified that our peak rates coincides with the cut-set bound analytically in an information-theoretic view.

I. INTRODUCTION
Caching, a technique playing a crucial role in combatting the peak hour network traffic congestion, receives increasing attention recently. A natural way to reduce peak hour traffic is to duplicate some contents at the end users. In the literature, there are several works focusing on investigating how to duplicate fractions of files at end users so that the peak rate is minimized and network congestion is reduced. Usually, caching works in two phases. One is the placement phase, which is performed during off-peak times. The other is the delivery phase, performed during rush hours when network resources are scarce. The general model with caching strategy were discussed in [1]- [7] where no coding strategy was applied and the gain comes only from local duplication. However, if each user is equipped with a cache with a small size compared with the amount of the content in the server, this gain is readily observed to be negligible.
In [8], the index coding strategy was discussed. In [10], a new coded caching strategy from an information-theoretic perspective was proposed to achieve a new achievable rate region for general scenarios, where some finite rate-cache pairs were firstly derived and then the lower convex envelope of these points is shown to be achievable by memory sharing. This strategy was shown to enjoy both the local gain from duplication as well as the global gain from coding. This fundamental idea was then extended to [12] where a decentralized coded caching algorithm was presented and to [11] where the nonuniform demand scenario was investigated. In [14], the secure issue with coded caching was investigated.
In this work, however, we investigate the fundamental achievable rate for a special case where all users are equipped with a cache of a small size. In this case, appropriate coded duplication of contents is essential to reduce the delivery rates. To this end, we introduce a new coded caching strategy and it is shown that the rate of this strategy coincides with the lower cut-set bound when the cache size is rather small. With memory sharing, it is shown that our strategy outperforms the strategy proposed in [10] in terms of achievable delivery rates when the cache size is relatively small.

II. PROBLEM SETTING
A system consisting of one server and K users is considered. An error-free link is assumed to be shared by all users connecting the server, where N files are stored for fetching. We also assume that each user is equipped with a cache of size Z k (k = 1, . . . , K) and each user is assumed to request only one full file. The aim is to design a novel coded strategy to achieve a lower peak rate that can guarantee each user obtaining the file requested, compared with the recent results on caching problems in [10]. In this work, we turn our interest on the special case that all users are with small buffer sizes (Z k ≤ 1/K) and K ≥ N, i.e., the amount of users is no smaller than that of the files in the server.
For clarity, we denote the smallest peak rate achieved by our strategy by R(M), i.e., the cache-rate pair (M,R(M)) is on the boundary of the achievable region, where M denotes the cache size of all users. For comparison, we denote the minimum peak rate achieved in [10] by R c (M) and the lower cut-set bound by R * (M).

III. MAIN RESULTS
Theorem 1: For N ∈ N files and K (K = N) users each with cache of size M = 1/N, the cache-rate is achievable.
is achievable.
Theorem 3: For N ∈ N files and K (K = N) users each with cache of size M ≤ 1/N, the achievable rate coincides with the associated cut-set bound.

Theorem 4:
For N ∈ N files and K (K ∈ N and K > N) users each with cache of size M ≤ 1/K, the achievable rate coincides with the associated cut-set bound.
Note that in [10], the achievable rate with M = 1/K is on the line connecting the two cache-rate pair points (0, N) and the first non-trivial point (N/K, min ((K − 1)/2, N(K − 1)/K)) 1 and is hence given by, where the inequalities in (5) and (7) follow from the setting that K ≥ N ≥ 1. Note also that the inequality in (7) strictly holds as long as N > 1, which demonstrates the gain achieved by our coding strategy over the strategy designed in [10] for the small cache size scenario.
Furthermore, with our coding strategy, we have Which is an encouraging result. In other words, with a smaller cache size M = 1/K, the designed coding strategy can achieve a rate no smaller than that in [10] with the cache size M = N/K if K ≥ 2N.
Therefore, compared with [10], the rate with the cache size of M < N/K is improved by our results through memory sharing, where the exact expression of the achievable rate with 0 ≤ M ≤ N/K is given on top of next page. For clarity, the cache-rate pair is achieved by memory sharing of the three points (0, N), (1/K, N − K/N) by our results and (N/K, min((K − 1)/2, N(K − 1)/K)) from [10].
It is also noted that our result does not hold for the case K < N, i.e., in this case, the cut-set bound is not achievable for the small buffer size (M ≤ 1/K) scenario. In addition, in our study, our algorithm cannot be applied in the case with relatively higher cache size, which still remains an interesting direction in future on how to achieve the cut-set bound for the case with relatively high cache size.

IV. EXAMPLES
Example 1. In this example, we set N = K = 3, i.e., a system consists of three files in the server and three intended users. Let W 1 = A, W 2 = B and W 3 = C. We would like to show that the (M, R) pair With cache size M = 1/3, we split each file into three subfiles with equal size, i.e., In the placement phase, the cache content of user k is designed , which is an XORed version of three subfiles from different files in the server.
In the delivery phase, let us consider an example that user 1 requires A, user 2 requires B an user 3 requires C. Hence, to obtain the missing files for user 1, we should transmit B 1 and C 1 to obtain A 1 from the XORed subfile in Z 1 as well as A 2 and A 3 for the missing files of A. In a similar manner, for user 2 requesting file B, the server need to transmit B 3 for the missing part of B (B 1 is obtained from the shared link satisfying user 1). In addition, the server transmits C 2 to obtain B 2 (as A 2 has been transmitted and received by user 2). Note that the server has satisfied user 3 since the missing subfiles C 1 and C 2 are already received by it. In addition, with the received A 3 and B 3 from the shared link user Therefore, the server has to transmit (B 1 , C 1 , A 2 , A 3 , B 3 , C 2 ) to satisfy the requests of all users in this example. In a similar manner, all other requests can be satisfied. Since each subfile has rate 1/3, the total rate 2 is achievable.
On the other hand, the cut set bound derived in [10] indicates the minimum rate is R * (1/3) = 3−3/3 = 2 and is identical to the achievable rate. By cache sharing, we conclude that the achievable rate coincides with the cut set bound if 0 ≤ M ≤ 1/N.

Example 2.
In this example, we consider a system with a server of 4 files and 4 users, i.e., N = K = 4.
The four files are termed as W 1 = A, W 2 = B, W 3 = C and W 4 = D.
Consider the case with the cache size M = 1/4. In this example, we split each file into four parts of equal In the placement phase, we let user i caches the XORed subfile In the delivery phase, for instance, consider that user i requires W i , i.e., user 1 requests A, user 2 requests B, user 3 requests C and user 4 requests D. We can satisfy all requests of different users by . It is observed that with this transmission subfile list, all missing subfiles can be received by intended users. In addition, it is readily verified that the intended subfile which is XORed in the cache of each user is also obtained by XORing the three other XORed subfiles. For example, for user 1, it receives B 1 , C 1 and D 1 , hence A 1 is also fetched by In a similar manner, user 2, user 3 and user 4 can also obtain B 2 , C 3 and D 4 respectively. Therefore, by sending these subfiles, all user requests are satisfied with rate 3, as the rate of each subfile is 1/4.
Similarly, we can realize any possible requests with rate 3 with the cache size M = 1/4. Hence, the cache-rate pair (1/4, 3) is achievable and can be verified to coincide with the cut-set bound, which is Akin to Example 1 and 2, the cache-rate pair (1/N,N − 1) is achievable for an arbitrary number of files N in the server with the same number of users as that of the files in the server, i.e., K = N. The proof for this general case is left to the next section.
Example 3. Consider a system with N = 3 files and K = 4 users. We term each file as W 1 = A, W 2 = B and W 3 = C. Consider the case with cache size M = 1/4. We split each file into 12 parts of equal size, i.e., A = (A 1 , · · · , A 12 ), B = (B 1 , · · · , B 12 ) and C = (C 1 , · · · , C 12 ). Each cache can therefore store three subfiles. In the placement phase, we let user i caches the three XORed subfiles as Hence one user caches 9 exclusive subfiles in an XORed version and any subfiles partitioned in the server can be found in the cache of one and only one user.
In the transmissions phase, let us assume that user 1 needs A, user 2 needs B, user 3 needs C and user 4 needs A. To fully exploit the coded caching strategy, we then delivery the subfiles (B 1 , C 1 , B 2 , C 2 , B 3 , C 3 ) for user 1 to XOR A 1 , A 2 and A 3 . By delivering of these subfiles, B 1 , B 2 are received by user 2 and C 1 , C 2 are received by user 3. Similarly, we deliver (A 4 , C 4 , A 5 , C 5 , A 6 , C 6 ) for user 2 to obtain B 4 , B 5 and B 6 . (A 7 , B 7 , A 8 , B 8 , A 9 , B 9 ) for user 3 to obtain C 7 , C 8 and C 9 . (B 10 , C 10 , B 11 , C 11 , B 12 , C 12 ) for user 4 to obtain A 10 , A 11 and A 12 .
Hence, by delivering these 24 subfiles, user 2 receive the complete file B and user 3 receive the entire file C. However, user 1 still lacks the subfiles (A 10 , A 11 , A 12 ) and user 4 is in need of the subfiles . To exploit the side information at the caches, we hence delivery (A 1 ⊕ A 10 , A 2 ⊕ A 11 and  parts of equal size, i.e., A = (A 1 , · · · , A 15 ), B = (B 1 , · · · , B 15 ) and C = (C 1 , · · · , C 15 ) and each cache can store three subfiles. In the placement phase, we let user i caches the three XORed subfiles as Each user then stores 9 exclusive subfiles in an XORed version and each subfile can be found in the cache of one and only one user.
In the transmissions phase, let us assume that user 1 needs A, user 2 needs B, user 3 needs C, user 4 needs A and user 5 requests B. Similar to Example 3, we deliver the subfile list (  It is worth pointing out that, the cut-set bound at the point M = 1/5 is R * (1/5) = 3 − 3/5 = 12/5 and equals the achievable rate R(1/5). By memory sharing, the cut-set bound is therefore achievable in the interval M ∈ [0, 1/5] in this example.

V. PROOF OF THEOREMS
We now present the achievable scheme for an arbitrary number of users with K ≥ N. We shall show that with the cache size of M ≤ 1/ max(N, K), the delivery rates presented in Theorem 1-2 are achievable and the cut-set bound is met for such points with cache size M ≤ 1/ max(N, K).

A. Proof of Theorem 1
Here we prove Theorem 1 for the case with an equal number of files and users, i.e., N = K. We prove it in two folds. Firstly, we verify that the point (1/N,N − 1) is achievable by a constructed coded caching scheme. Secondly, we show that any points with M < 1/N can achieve a rate of N − NM by memory sharing.
In the placement phase, the cache of user j is designed to be Z j = W 1j ⊗ . . . ⊗ W N j , an XORed version of subfiles, which contains one and only one subfile from all files. With this coded placement scheme, each user caches some exclusive part of all files.
In the delivery phase, if the users request L ≤ N − 1 files, we can simply transmit these requested files and the delivery rate is L files. We then move to the case that the users request N files, i.e., each user requests a different file. Due to symmetry, we only need to study the case that user i requests file W i .
The transmission algorithm is therefore presented as follows.
As for each file (N − 1)/N fraction of it is delivered, we totally deliver N − 1 files.
With this transmission, we argue that each user can obtain the files requested. For instance, for the ith user requesting W i , it can obtain all subfiles except W ii from the delivery of W i directly. In addition, user i receives all W ki (j = i) subfiles from file W k . Hence it can obtain the subfile W ii by

B. Proof of Theorem 2
Here we prove Theorem 2 for the case with N < K. The files are defined by W i (i = 1, . . . , N) and we split each file into NK subfiles, i.e., W i = (W i,1 , . . . , W i,N K ).
In the placement phase, the cache of user i is designed to store N XORed version of subfiles, which are, With this coded placement scheme, each user caches some exclusive part of all files and the union set of the caches comprises all N files in the server.
In the delivery phase, if all users request L (L ≤ N − 1) distinct files in total, we can simply transmit these requested files one by one and the total amount of files delivered is L files and the associated rate is less than N − N/K. We then move to the case that all N files are requested. Suppose user i requests the file W d i and correspondingly the subfile W i is requested by totally k i users. By definition, we hence The transmission procedure can be divided into two steps as follows.
2) In the second step, for the rest subfiles requested by users, we apply the following algorithm by firstly grouping the users requesting the same file and then applying coding strategy to reduce transmissions. The details are presented as follows. ii) If u = 1, deliver the N coded subfiles, W i,N (K 1 −1)+j ⊕ W i,N (K 2 −1)+j (j = 1, . . . , N) and set u ← u + 1.
iv) If u < k i − 1 go to Step iii), otherwise terminate the delivery of subfiles of W i .
Note that in step 2), a) follows from two facts. The first is that the ith user obtains W d i ,N (i−1)+j (j = 1, . . . , N) via coded delivery. The second is that it receives directly W d i ,N (k−1)+j (k = i and j = 1, . . . , N) in the first step because they are delivered for other users for XORing. Therefore, the ith user can reconstruct the full file W d i directly after Step 1).
Similarly for the case that W i is requested by more than one users (k i > 1) in b) of Step 2), the fact that each user requesting W i needs (k i − 1)N follows also from two facts. The first is that it receives N subfiles via coded delivery in Step 1). The second is that it directly receives N(K − k i ) subfiles for the users requesting other files in Step 1). Therefore, only NK − N − N(K − k i ) = N(k i − 1) subfiles is requested by each of the users requesting W i .
In the following, we shall show that the sub-algorithm in b) in Step 2) can help all users requesting W i receive all the residue files.
Note that for user K m requesting W i , it receives the subfile list (W i,N (Km−1)+j ⊕ W i,N (K m+1 −1)+j ) (m = 1, . . . , k i −1, j = 1, . . . , N). It can firstly obtain W i,N (K m−1 −1)+j and W i,N (K m+1 −1)+j (j = 1, . . . , N) from the m−1th and the m delivery of subfiles via XORing. It can then recursively obtain W i,N (K m−k −1)+j (k = 2, . . . , m − 1) and W i,N (K m+k −1)+j (k = 2, . . . , k i − m). Hence, user K m can obtain the complete file W i . In a similar manner, we can verify that any other users in the same group requesting W i can receive the complete file W i .
As W i is an arbitrary file in the server, we conclude that all users can obtain the requested file by our algorithm and in the following we shall derive the achievable rate for M = 1/K by applying the algorithm above. We first denote C i as the amount of subfiles delivered in Step i) and n k i as the amount of the XORed version of subfiles delivered for W i in Step 2). In Step 1), it is observed that the total amount of subfiles delivered is given by, As designed in Step 2) for file W i , the total amount of the remaining transmissions is Therefore, the total amount of subfiles delivered in the second step is The total amount of subfile deliveries in these two steps is given by The associated delivery rate therefore is and we can claim that (1/K, R(1/K)) = (1/K, N(1 − 1/K) is an achievable cache-rate pair. In addition, regarding the trivial cache-rate pair (0, N), for any M ≤ 1/K, the rate pair (M, N(1 − M)) is achievable by memory sharing. Theorem 2 is hence proved.

C. Proof of Theorem 3 and Theorem 4
Here we show that the achieved rate given in Theorem 3 and Theorem 4 for the scenario with N ≤ K and M ≤ 1/K coincides with the lower cut-set bound.
From [10], the cut-set lower bound is given by, From the above derivation, it is hence concluded that for the scenario N ≤ K and M ≤ 1/K, the lower cut-set bound is achievable. Theorem 3 and Theorem 4 are therefore verified.

VI. CONCLUSION
In this work, we studied the caching problem when all users are with a small buffer size and the number of users is no less than the amount of files in the server. A novel coded caching scheme was proposed to achieve the cut-set bound rate for such a scenario.


text:
Inference for feature selection using the Lasso with high-dimensional data

Penalized regression models such as the Lasso have proved useful for variable selection in many fields - especially for situations with high-dimensional data where the numbers of predictors far exceeds the number of observations. These methods identify and rank variables of importance but do not generally provide any inference of the selected variables. Thus, the variables selected might be the"most important"but need not be significant. We propose a significance test for the selection found by the Lasso. We introduce a procedure that computes inference and p-values for features chosen by the Lasso. This method rephrases the null hypothesis and uses a randomization approach which ensures that the error rate is controlled even for small samples. We demonstrate the ability of the algorithm to compute $p$-values of the expected magnitude with simulated data using a multitude of scenarios that involve various effects strengths and correlation between predictors. The algorithm is also applied to a prostate cancer dataset that has been analyzed in recent papers on the subject. The proposed method is found to provide a powerful way to make inference for feature selection even for small samples and when the number of predictors are several orders of magnitude larger than the number of observations. The algorithm is implemented in the MESS package in R and is freely available.

Introduction
Molecular technologies have reached a state where it is possible to quickly and cheaply measure the status of millions of nucleotides, mRNAs, genes, proteins, or metabolites simultaneously and repeatedly over time. The availability of these massive data ideally allows for complex and detailed modeling of the underlying biological system but they also pose a serious potential multiple testing problem because the number of covariates are typically orders of magnitude larger than the number of observations. Recently, investigators are starting to combine several of these high-dimensional dataset which has increased the demand for analysis methods that accommodates these vast data (Nie et al., 2006;Brink-Jensen et al., 2013;Su et al., 2011;Kamburov et al., 2011).
As data sets increase in size, methods that promote sparse results have become more important and popular. Hastie et al. (2005) and Hesterberg et al. (2008) provide an overview of the development of these methods of which the Lasso (least absolute shrinkage and selection operator) is the most widely used (Tibshirani, 1996). While all these estimators enforce sparsity (since only a fraction of the variables are believed to be influential) and perform variable selection, they lack the inference from traditional statistics, such as p-values and confidence intervals. As a consequence, these models will always identify a set of the most important predictors even if none or only some of them are significant.
To address this issue several recent papers propose techniques that help asses the importance of the selected predictors. Lockhart et al. (2013) developed a method that use a covariance test statistic approach to compute p-values for parameters obtained from a Lasso regression. With this method p-values can be calculated for all predictors in a data set if there are more samples than predictors, p < n. In the case of p > n it is not possible to use the covariance test without specifying an estimate of σ 2 , the error standard deviation.  presents another approach where the data is split into two groups. The Lasso is applied to one group, after which the variables selected by the Lasso are used as predictors to obtain p-values from an ordinary least squares (OLS) regression on the other group. Wu et al. (2009) suggest to first use the Lasso to select a set of relevant variables which are then fitted to a non-penalized model where from which the p-values can be calculated.
In applied sciences we find often that variable selection is used for screening to determine which predictors such as genes to focus on, in further (possibly costly) analyses. A useful tool in this setting would be a model that allowed us to perform variable selection and assign a p-value to evaluate the evidence of the most important predictors found from the variable selection procedure. We wish to propose an approach for variable selection and inference for the Lasso that works directly when p > n rather than choosing variables with Lasso and transferring these to an OLS domain for inference. Our approach uses randomization/resampling to infer the significance of the kth chosen predictors from a Lasso model. Thus, our focus is on using the Lasso to not only generate new (biological) hypotheses but also to evaluate the evidence for those hypotheses.
The paper is structured as follows: in the next section we present a method to both identify features and for computing p-values of those features obtained from a Lasso regression model. Potential problems and possible extensions are also discussed. The simulation section presents results from a series of simulation studies that show the power of the proposed method under various conditions and for situations both with and without correlated predictors. In addition we show how well the method identifies the most important of the predictors and apply the proposed method to a dataset on prostate cancer. Finally, the proposed method is discussed. Note that while we use the Lasso in the following the proposed procedure can essentially be applied in combination with any sparse feature selection approach (e.g., elastic net, ridge regression).

Methods
We consider the situation where we have a quantitative response vector, y ∈ R n and a set of p quantitative predictors x i1 , . . . , x ip for each observation i ∈ {1, . . . , n}. The number of predictors can be much larger than the number of observations, p n and we are interesting in identifying predictors that are associated with the response vector y.
Suppose that y = Xβ + where the noise is assumed to be Gaussian, ∼ N (0, σ 2 I). The Lasso is a penalized version of the multiple regression model where sparsity of the parameter vector β ∈ R p is achieved by adding a penalty term to solvê where λ ≥ 0 is the regularization parameter (Tibshirani, 1996). λ controls the amount of shrinkage ofβ such that λ = ∞ corresponds to setting all parameters to 0, while λ = 0 corresponds to an ordinary least squares multiple regression model with no restrictions on the parameter vector. The choice of λ will be discussed below.
The Lasso can be used for variable selection for high-dimensional data and produces a list of selected non-zero predictor variables. Meinshausen and Yu (2009) show that while the Lasso may not recover the full sparsity pattern when p n and when the irrepresentable condition is not fulfilled (e.g., if highly correlated predictor variables are present) it still distinguishes between important predictors (i.e., those with sufficiently large coefficients) and those which are zero with high probability under relaxed conditions. In many high-dimensional molecular genetic datasets it is reasonable to assume that there is just a small number of genes that influence the outcome while the vast majority of genes are irrelevant for the outcome. This common setup is also relevant in other situations and it forms the basis of the following. When the relative number of truly non-zero predictors is small then the results from Meinshausen and Yu (2009) also show that the Lasso selects the non-zero parameters as well as "not too many additional zero entries of β". Here, we seek to identify which of the selected predictors that we believe to be non-zero. The predictors found by Lasso are generally ranked by their importance, so that a high value for λ will include the most important predictors, decreasing λ will include other less important predictors (Efron et al., 2004;Hastie et al., 2005;Hesterberg et al., 2008).
We wish to determine which of the features identified by the Lasso that are indeed true positives. Let β (1) , . . . , β (k) be the ordered absolute coefficients of the k non-zero predictors that are selected by the Lasso. To ensure that the effects of the predictors are comparable across variables we assume that each predictor has been standardized by dividing by their standard deviation. This is not a restriction when determining the importance of selected variables as the internal structure of the predictors (and their pairwise correlations) is preserved (Efron et al., 2004). Essentially, this approach mimics the adaptive Lasso of Zou (2006) and ensures that the coefficients are equally penalized by the 1 penalty in (1). The variables can then be ordered according to their absolute size such that |β (1) | ≥ |β (2) | ≥ · · · ≥ |β (p) |.
We are interested in testing hypotheses of the form where β (k) is the kth most important feature. Note that contrary to classical hypothesis testing we are not testing hypotheses about specific predictors but we are testing whether the kth identified parameter is equal to zero. As a test statistic for the kth selected parameter we use the corresponding coefficient obtained from the Lasso, |β (k) |. In order to derive the distribution of the kth identified predictor we permute response vector y to remove any associations to the set of predictors while retaining the individual structure and correlations among the set of predictors (Manly, 2006). This randomization is undertaken a large number of times and for each randomization we run the Lasso on the permuted data to obtain a distribution of coefficients for the kth identified predictor. Note that this approach might result in different variables being selected for each permutation and this matches the null hypothesis (2) where the focus is on finding out whether the kth identified predictor is significant.
The algorithm for testing the null hypothesis (2) using a randomization approach can be summarized as follows: 1. Start by scaling the predictors so their effects are comparable, i.e., where X j is the jth column of the design matrix X.
3. Let B be the (large) number of randomizations to perform to determine the distribution of the coefficients under the null hypothesis. For each b ∈ B do the following: (a) Permute the response vector, y b , and fit a new Lasso model using y b as the response.

4.
For each feature, k, we can compare the size of the coefficient identified in the original dataset, |β (k) | to the distribution of the coefficients found for the kth feature for the permuted data, |β 1 (k) |, . . . , |β B (k) |. The p-value for the kth feature is then the fraction of coeffients under the null that are larger than or equal to |β (k) |: Note that by construction the p-value defined by (3) controls the error rate since we are simulating the distribution on the null hypothesis.

Feature selection and collinearity
In applications such as genetics, the number of predictors, p, is often several orders of magnitude larger than n and we are typically more concerned with identifying some associations rather than finding all associations since any relationships found will often be the focus of subsequent specific experiments to verify the genetic function. Thus, our interest is on hypothesis generation rather than testing a specific hypothesis: is it possible to identity one or a few potentially interesting or relevant predictors, in a scenario with little or no knowledge of the individual predictors. It is well-known that the Lasso has a weakness when dealing with correlated predictors: it will only select one of a group of collinear predictors to represent their effect on the response (Zou and Hastie, 2005) and the coefficient for the selected variable will have high variance (Meinshausen, 2008). Collinearity poses a problem if we are intersted in making inferences about specific predictors because the corresponding standard error becomes unstable. However, in the present setup collinearity among predictors means that while we may not be able to identify all predictors that are associated with the outcome, the size of the coefficients for the variable that are selected essentially represent the maximum effect size of the cluster of correlated predictors.
In particular, if p n then we may be interested in just finding one association between a predictor and the response in which case our primary focus is on the null hypothesis (4)

Choice of penalty parameter λ
The Lasso involves a penalty parameter, λ, that determines the amount of shrinkage that is applied to the parameters. In our approach, we recommend using the same procedure for estimating λ, that the reseacher would typically use together with a Lasso regularization model. Typically, λ is determined through some form of K-fold cross-validation where λ is chosen such that it minimizes the cross-validation error.
where x i is the set of covariates for individual i,f −κ(i) is the expected value from the Lasso regression based on the folds/parts of the data that does not contain observation i.
There are two considerations to consider here: First, we know that we are in a situation where the majority of the variables are unrelated to the outcome. Thus we want to ensure, that the majority (or possibly all) of the variables are shrunk to zero. This is particularly true under the null hypothesis where there is no association between the variables and the outcome due to randomization. Secondly, we want to ensure that when there is indeed an association between some of the variables and the outcome then we want λ to be small enough that the effect of the associated variables are not shrunk too much.
In the following we have worked with a 10-fold cross-validation using the mean absolute error as loss function since our analyses have shown that this gives good stable results. Using the mean absolute error instead of the traditional mean squared error makes the cross-validations less sensitive to spurious extreme fits which is often the case under the null, where none of the variables are associated with the outcome. However, other approaches would be directly applicable as well at the researchers discretion.
One possible approach here, that would substantially reduce the computation time would be to use the same λ for the randomization samples as was used in the original dataset. That ensures that we only have to do cross-validation once (for the original data) and not for each randomization. Also, the estimate of λ under the null hypohtesis (where the randomization approach assumes that none of the predictors are associated with the outcome) can be rather unstable since there really is no obvious minimum for the cross validation procedure to reach.

Including external predictors
In some situations it is of interest to use the Lasso to select predictors from among a subset of the predictors. For example, some predictors might be related to the design of the experiment (and we wish to force them to be part of the modeling) while the remaining predictors contains the variables we wish to identify/select from because we have no prior knowledge about them.
Thus, we consider two sets of predictors,X and X such that X = [X|X ] whereX are the predictors that we wish to force into the model while X are the predictors from which we wish to make a selection. If we apply the Lasso to X we will select variables from the full set of predictors which means that some of the potential confounders that we wish to include are disregarded in the modeling.
There are two obvious alternatives to just using the classical Lasso in this situation. One is to make a two-step procedure where we first fit a model using only the predictors inX, i.e., From (6) we extract the residuals, r = y −Xβ, and use the residuals as outcomes in combination with the procedure described above. This approach ensures that the (marginal) effects of the predictors inX are removed and and features that are subsequently found are conditional on these marginal effects. The disadvantage is that the effects of the predictors inX and X are assumed to be working independently of each other, which may not be realistic.
The adaptive (or weighted) Lasso of Zou (2006) uses a weighted penalty resembling (1) where w is a vector of non-negative weights for each predictor. Typically, the individual weights are set to w j = 1/|β j | ν , whereβ j is the univariate regression coefficient estimate of parameter j and ν > 0. If a weight is set to zero then the corresponding predictor will not be penalized. Thus if the weights of the parameters inX are set to zero then the corresponding variables enter the model without being shrunk towards zero.

Family-wise error rate for multiple inference results
The p-value obtained from (3) controls the error rate by construction as mentioned above. However, the error rate control is on a per-hypothesis basis so if we are only aiming on making inference for the "best" selected predictor -corresponding to the hypothesis (4) -then the proposed procedure yield the correct error level. However, in some situations it is of interest to extract inference on as many predictors as possible and simultaneously control the family-wise error rate. We can still use (3) to obtain individual p-values for the first feature, the second feature, etc., and Holm's step-down procedure can control the family-wise error rate in those situations (Holm, 1979). In its original form, Holm's procedure orders the p-values and makes sequential comparisons from the smallest p-value to the largest until the first occurrence of a null hypothesis that fails to be rejected. All other subsequent hypotheses are also not rejected.
Here we suggest a slightly different version of Holm's procedure. The p-value of the k'th selected feature is compared against where α is the overall significance level desired and m is the number of hypotheses tested. The significance level for each feature is identical to the level used by Holm's procedure but unlike that we do not order our p-values according to size but test them in the order that they are selected by our procedure. This ensures that we still control the family-wise error rate (by the exact same arguments as used by Holm (1979)) since it becomes more difficult to reject hypotheses by not ordering them according to the size of the p-value. Also, since we keep the order of the features it prevents us from ending with a result where, say, the first and third selected features are significant but the second selected feature is not.

Simulation studies
To examine the validity of our procedure, we performed simulation studies to assess the performance of the sensitivity and specificity. For each setting, we simulated 100 data sets with only 50 observations generated under the linear model, where ∼ N (0, I) and where X ij ∼ N (0, 1), i = 1, . . . , 50, j = 1, . . . , p. The unit variance is not really a restriction in this case as we start the analysis algorithm by standardizing each predictor (as outlined in the methods section above). The number of predictors were varied from 1000 to 250000 to represent various datasets. Initially we assume that there is just a single predictor that is associated with the response and we vary the corresponding regression coefficient, β, from 0 to 1.5. This corresponds to a partial correlation coefficient between the predictor and the outcome ranging from 0 to 0.83. With these data we follow the procedure described above where each combination of predictors, p, and associated coefficient, β, is run 100 times and for each combination we use 100 permutations to determine the power of the feature identified as the most important corresponding to the hypothesis β (1) = 0. In all computations a significance level of α = 0.05 was used. In order to see how collinearity influences the power we run simulations with the same association between a single predictor and the outcome but we let that predictor be part of a cluster of ten correlated predictors such that cor(X i , X i ) = ρ. Here, ρ = 0.5 or ρ = 0.95 to represent moderately and highly correlated predictors.
We first focus on two primary abilities of the model: the power to identify the first selected predictor and the impact of correlated predictors in the model. The simulation results are shown in Figure 1. The simulations show three clear results: 1) for moderate to high effect size (i.e., when β is 1-1.5) we obtain a high power even when the number of predictors is large, 2) when the causal gene is part of a correlated cluster of predictors then the power is higher than if the gene is independent, and 3) generally there is a fall in power as the number of predictors increase although this drop appears to stabilize and level off as the set of predictors increases.
The power is 100% for an effect size of 1 or 1.5 (the lines overlay each other in Figure 1) except for the independent predictors. That means that even when there is a ratio of predictors to observations, p/n, of 5000 then we are still able to identify a signal in the data even with just 50 observations. An effect size of 1 corresponds to an effect of 1 standard deviation so we are even able to identify the presence of a gene with realistic biogical effects.
For correlated data we see that the power is larger than the power observed from independent predictors. This is caused by the fact that the causal predictor is part of a cluster; with correlated predictors, then each of the predictors in the cluster has a probability of showing an improved association to the outcome just by chance. Thus, we essentially improve our power to detect one of the predictors in the cluster at the cost of perhaps not detecting the true one but at least one that is highly correlated to it. If the causal predictor was a singleton and not part of a cluster of correlated predictors then the power results resemble the results from the uncorrelated data (results not shown).
Initially the power drops for all situations as the number of predictors increase (making it harder to identify that there is in fact a true association among one of the predictors and the outcome) but the overall power seems fairly constant once the number of predictors reach around 50000 (of which just one is associated with the outcome). Not surprisingly, this drop is more noticeable when the true association has a moderate effect than when the effect is smaller (where the power is consistently low) or larger (where the power is consistently high). Figure 1 also shows that we are generally able to control the family-wise error rate at the desired significance level (0.05). Perhaps most surprisingly is the consistent high power for moderate to high effect sizes (β = 1 or β = 1.5) considering this is based on just 50 observations. Figure 1 focused on the evidence of the first/most important predictor.  Figure 1: Power to detect the first identified predictor selected by the Lasso for varying number of predictors and varying effect size of the predictor for a dataset containing 50 observations. Each point is the average from 100 simulations, each using 100 randomizatons to compute the p-value. The black lines correspond to completely independent predictors, the red lines are when there is some collinearity between a group of predictors while the blue lines represent the situation with a group of highly correlated predictors.
Once that has been identified we would like to determine the power to detect the second most important predictor and its power. In our simulations we assumed that there was always one causal predictor with a corresponding parameter of β 1 = 1.5 and we varied the effect of another predictor, β 2 , with values ranging from 0 to 1.5 as previously. Following the setup above we also allow for correlations and assume that the two predictors are actually part of the same cluster. : Power to detect the second identified predictor selected by the Lasso for varying number of predictors and varying effect size of the predictor for a dataset containing 50 observations. The dataset contains two predictors from the same group/cluster that are associated with the response, one of which is fixed with an effect size of 1.5. Each point is the average from 100 simulations, each using 100 randomizatons to compute the p-value. The black lines correspond to completely independent predictors, the red lines are when there is some collinearity between a group of predictors while the blue lines represent the situation with a group of highly correlated predictors. Figure 2 shows the power to detect the second most important variable when there are two potential causal variables from the same cluster. Overall, we see the same trends as we saw for the most important variable in Figure 1 except that the power is generally lower. Looking at the solid line corresponding to the largest effect of the second most important variable we see a marked decline in power as the number of predictors increase if the predictors are all independent. The decline is not very surprising as both of the two causal predictors have the same effect size (both 1.5) so the second most important variable will by design be the smallest of those two (after sampling error has been added). Thus, due to random variation, the estimated effect of the second is likely to be slightly smaller than the true effect (ie., biased downward) and contrary the effect of the most important variable will be slightly biased upward. However, the drop in power for the second most important variable is still substantial even for high effect sizes except when the predictors are correlated. Figure 2 also shows that the error rate is controlled around the 5% level for independent predictors when there is only one predictor that is truly associated to the response (black dotted line). As for the results from the first identified predictor, Figure 1, we get that correlated predictors increase the power to identify subsequent predictors.
As highlighted in the methods section, the proposed procedure computes the evidence for the identified features but does not directly provide significance inference for a particular predictor. In practice, however, it is also of interest how well the Lasso approach identifies the predictors, that are truly associated with the response. While this has been investigated in several papers (Efron et al., 2004;Hastie et al., 2005;Hesterberg et al., 2008;, we include results using the same simulation setup as described above for direct comparison with the simulation results shown in Figure 1. The results are shown in Figure 3 which clearly shows that the precision increases with increasing signal strength and decreases when the true predictor is part of a cluster of predictors. In the latter case, it is generally one of the the predictors from the correlated cluster that is identified, so while we may not identify the specific variable we do identify the cluster (results not shown).

Application to prostate cancer data
We apply our proposed method to the prostate cancer example from Lockhart et al. (2013), a subset of 67 samples and 8 predictors from a larger dataset. The outcome is the logarithm of a prostate-specific antigen and we want to determine the association between the outcome and any predictors. Data can be found at www-stat.stanford.edu/~tibs/ElemStatLearn/. The setup for this dataset is simpler than the situation mentioned in methods section since p < n so it is possible to analyze all predictors simultaneously by using, say, a classical multiple regression model. We compare the results from our proposed method with three other analyses approaches: simple multiple regression, using the Lasso in combination with the covariance test statistic of Lockhart et al. (2013)  q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q Figure 3: Feature identification precision for the Lasso to identify the single true underlying (most significant) predictor for varying number of predictors and effect sizes. Each point is the average from 100 simulations. The black lines correspond to completely independent predictors, the red lines are when there is some collinearity between a group of predictors while the blue lines represent the situation with a group of highly correlated predictors. cross-validation: First, Lasso regression is applied to a part of the dataset to select a list of predictors, and secondly an ordinary multiple regression (using the selected predictors) is applied to the remaining data to obtain p-values for the selected predictors.
Note that unlike our proposed approach, both the multiple regression, the Lasso-covariance test, and the multi-split method are all designed to test hypotheses about each specific predictor. However, the multi-split method is vulnerable to the selection obtained from the first split which gives rise to rather substantial variance of the p-values in this dataset. Splitting the sample repeatedly and getting a set of p-values has also been suggested by the authors, but "it is not obvious, though, how to combine and aggregate the results." . Here, we have just averaged the p-values obtained for each of the sets (with non-selected predictors getting a p-value of 1). Table 1 shows that the three methods that accommodate multiple predictors and test hypotheses about each specific predictor (OLS, multi-split and the covariance test) generally give the same results and all identify the same predictor, lcavol, as being the most important. The same result is obtained with our proposed method, where the first selected variable is highly significant (and turns out to be lcavol ). The simple marginal regression analyses show that virtually all predictors are associated with the response, but the other approaches reduce the number of significant variables partly due to correlation among the predictors. Our proposed randomization test identi-fies slightly more variables than the covariance test (and a few more than the multi-split procedure) and seems to lie somewhere between the ordinary multiple regression model and the covariance test.
It is only the covariance test that places any real emphasis on the lcp predictor in part because of a high degree of collinearity to lcavol (the correlation coefficient between lcavol and lcp is 0.692, which is the second largest among the predictors). The largest pairwise correlation is between pgg45 and gleason and is 0.757 but the association to the outcome is less for those two variables so the impact of their collinearity on the p-values is less noticeable.

Discussion
We have proposed an algorithm to aid in making inference and subsequently relevant hypotheses concerning data with (many) more predictors than samples. It greatly extends the results from shrinkage regression methods to be able to assign a p-value to findings from regularized regression methods that combine variable selection and estimation.
When the number of predictors p is larger than then sample size n, regularized regression methods can be used to identify a sparse model and to provide stable parameter estimates. The standard Lasso suffers from several problems in this regard, in particular that it is not consistent in cariable selection and that the limiting distribution of the estimates are non-standard and cannot be directly derived. To overcome these shortcomings Fan and Li (2001) and Zou (2006) have presented versions of regularized regression that not only have asymptotic oracle properties but also have consistency in variable selection and asymptotic normality of the estimators. However, inference based on these improved regularization methods for finite samples generally perform poorly even when the effects are large (Minnier et al., 2011).
An obvious difference between the p-values obtained from ordinary least squares or from other regularized regression inference approaches is that we pursue investigating a null hypothesis that is not concerned with a specific (set of) predictor(s) but is concerned solely with evaluating the evidence that the results obtained from regularized regression are stronger than what would be expected if none of the predictors were associated with the response. Classical OLS-style p-values are extremely useful but it can be argued that for the majority of problems in genomics -where there is often little or no prior information about any of the possible predictors -the focus is on hypothesis generation and variable selection and not on testing specific hypotheses. Hence our focus (and the proposed procedure) is on hypothesis generation and not on inferences about specific variables.
Our simulations show that -even with just 50 observations -the proposed procedure has substantial power to identify at least one associated predictor among a set of 50-250 thousand predictors without serious performance decline (Figure 1). This suggests that not only can we can identify relevant predictors within a large set of irrelevant predictors -we can also attach a level of significance so we can evaluate whether our findings are indeed likely to be true (and relevant) predictors, that are associated to the outcome. Our results extend to the situation where there are multiple causal variables (Figure 2) although the power declines slightly more rapidly with the number of predictors when testing the importance of subsequent features. The results regarding the second most important variable shown in Figure 2 was based on two causal variables in the same cluster. If we run the same analyzes where the two causal variables are in two different clusters we get essentially the same results as shown for the uncorrelated data in Figure 2 (results not shown).
We have run the same simulations with a reduced dataset of 30 observations instead of 50 observations and while the power obviously is lower we see the same overall trends as shown above. Thus, even with fairly small datasets we have decent power to identify a variable that truly is associated to the outcome.
It can be argued that for genetic data where many genes may follow a similar pattern of expression and thus be correlated, Lasso is not an obvious choice for variable selection. If the purpose of the selection is indeed to identify a whole cluster of co-expressed genes, other shrinkage algorithms could be better suited. However if the genes selected by the Lasso are seen as the most influential representative of a cluster there are numerous ways to identify others in the same cluster. Since the whole nature of our approach is not to identify specific variables this is not a problem per se. In fact, Figures 1 and 2 show that the power to detect something from a clustered set of predictors rise dramatically so clustered predictors will just increase our power to identify at least one of the predictors from the cluster.
When comparing methods applied to the prostate dataset, it was clear that all four methods (the proposed approach, ordinary least squares, the covariance test statistic, and the split method) are able to identify the variable lcavol as among the most important and a small p-value is assigned to this predictor. Note that while the four methods differ somewhat in their results they also test different versions of the null hypothesis. The split method consistenly assigns a small p-value to the lcavol predictor but the remaining seven predictors obtain p-values estimated with very large uncertainties. The randomization approach generally yields lowest p-values which is partly due to the fact that the variables are indeed mostly correlated with the outcome, and partly due to that the null hypothesis is different (in particular it assumes that none of the predictors are associated with the outcome).
We believe the proposed method could also be applied in for instance Genome-Wide Association Studies (GWAS), where Lasso is already widely used, but significance testing typically done outside the Lasso domain, as done by Wu et al. (2009).

Conclusion
We have presented a method that can be used to make inference about variable selection results from regularized regression models such as the Lasso. We show that it has high power to infer evidence that the selected features are not chance findings -even when the number of predictors is several orders of magnitude larger than the number of observations, i.e., when p > n. The method controls the family-wise error rate and can essentially be used with any regularization method. The proposed method is relevant for situations where regularized regression methods is used as part of the statistical modeling to identify features for subsequent analyses.