Curating Covid-19 data in Links

Curated scientific databases play an important role in the scientific endeavour and support is needed for the significant effort that goes into their creation and maintenance. This demonstration and case study illustrate how curation support has been developed in the Links cross-tier programming language, a functional, strongly typed language with language-integrated query and support for temporal databases. The chosen case study uses weekly released Covid-19 fatality figures from the Scottish government which exhibit updates to previously released data. This data allows the capture and query of update provenance in our prototype. This demonstration will highlight the potential for language-integrated support for curation to simplify and streamline prototyping of web-applications in support of scientific databases

Introduction
Curated scientific databases take significant human effort to develop and then to maintain [2]. These databases are crucial in providing knowledge bases for science to proceed and users of the data need to be able to trust in their contents. One way to support this trust is for users to be able to review provenance information.
We consider update provenance [2] as a specific use case, based on the fact that regularly released datasets can include updates to previously released datasets, and our case study is based on data that has been released weekly by the Scottish government on Covid-19 deaths [8].
We are developing a prototype curation interface using Links 3 , a cross-tier programming language with language-integrated query that is being extended with experimental temporal database features [3].
Both the prototype and Links's temporal features are works-in-progress, and as we develop the interface, we are considering the more general issues that would apply to any curated scientific databases where update provenance is to be captured using temporal databases.

Links
Links is a cross-tier programming language developed at the University of Edinburgh [3]. It is cross-tier in the sense that it allows a developer to write a single type-checked program which that can then be executed efficiently on multi-tier Web architectures. Typically, a web application consists of three distinct applications coded in different languages: HTML and JavaScript for the browser, a different language for the application logic and SQL for the database queries, leading to complex coordinating issues. Links provides a single language in which to implement these three aspects, thus simplifying the development process. For our curation interface, the built-in translation to JavaScript completely abstracts away the details and there is no JavaScript code in the source Links program.
Furthermore, Links supports language-integrated query whereby database queries can be written in Links itself resulting in safe and efficient queries. In particular when writing database-related code, the support provided by type inference for row types in Links makes referring to the fields of interest in a table while abstracting from the others straightforward. This leads to compact and readable programming style. Links requires the types of the database tables to be declared explicitly in the program, which enables checking of language-integrated queries and supports the temporal query transformations. This adds some work at the beginning and if there is schema evolution, work is needed re-synchronize these declarations. Support for schema evolution in Links is a future area of research. Links currently supports PostgreSQL, MySQL 5.x and SQLite 3. Links covers a wide range of SQL but some aspects are ongoing research such as support for set and bag semantics [9].
In terms of use for curated scientific databases, IUPHAR/BPS Guide to PHARMA-COLOGY (GtoPdb) [1] has been reimplemented in Links as a case study to demonstrate that that Links is suitable for this task both in terms of functional correctness and performance [4]. However, because of its size and complexity, GtoPdb is not a good candidate for exploring the strengths and weaknesses of Links's new temporal support; instead in this demonstration we present the current Covid-19 curation prototype, which is the next step in developing curation functionality for this type of database in Links. We consider both the interface as the end product, and how the development of the interface is supporting by the features of Links.

Temporal databases
Temporal databases provide the ability to record when a row in a table is valid, either with respect to the database itself using a transaction time period, or with respect to the real world using a valid time period [5]. We can use this functionality to track the validity of the data items that are updated. Figure 1 illustrates how an update differs between a standard database on the left, and a temporal database on the right. In the former, the data is replaced and the previous values are lost. However, in the temporal case, additional columns to record the start and end of the time period of validity form part of the key and allow previous values to be recorded. The interpretation of the validity is dependent on the particular application.
Although temporal extensions to SQL have been standardized [6], many current popular relational database implementations have no built-in support for temporality, although it is possible to implement temporal tables by the use of explicit additional fields and complex hand-generated SQL queries [10]. In comparison, Links now pro- vides support for transaction-time tables and valid-time tables, allowing both sequenced (taking time period into account) and non-sequenced queries over these tables. This is achieved by interacting with a standard relational database such as PostgreSQL, using the approach currently provided by Links for generating standard queries and translating temporal queries into standard queries as described above [10], thereby avoided the need for the application developer to generate these complex SQL statements. An example is given in the next section.

Curation functionality
To investigate how to develop curation functionality in Links, we choose a dataset that raised questions of interest around updating of data. To set the context for discussion of the type of queries that can be considered, we first provide more information about the data we used in implementing the prototype.

The case study
We identified data that was released weekly by the Scottish Government through the National Records of Scotland website [8], as suitable and interesting for the prototype exploration. Each week, since early in the pandemic a spreadsheet (as a CSV file and Excel document) has been released (amongst other data) with counts of Covid-19 fatalities for individual weeks and data categories including sex, age, health board, local authority, and location. An example of a data category is "Location of death" and its subcategories are "Care Home", "Home/Non-institution", "Hospital" and "Other institution". Our application supports upload of this CSV data and its transformation into a temporal table as illustrated in Figure 2.

Provenance-based queries
One of the aims of this research is to identify the queries that are interesting for update provenance. An obvious query is how an individual data item has changed over time, but other potential queries include finding out whether one category of data has changed more often than another. Dependency is also relevant: are the changes of a data item associated or correlated with changes in other data. Examples of queries that the interface can support (or will support in the future): 1. What was the number of female fatalities in the week of 20 April 2020 when that data was first uploaded 2. What is the current number of female fatalities in the week of 20 April 2020? 3. What is the range of female fatalities in the week of 20 April 2020 over all uploads? 4. Which updates to female fatalities were rejected and when? 5. Have there been more updates to female fatalities or male fatalities considering all weeks? 6. Which health board has seen most updates in the first six months of the pandemic? 7. How are updates for the Lothian health board figures correlated with those for the local authority of Edinburgh?

The prototype curation interface
The interface has been developed using the Bootstrap HTML, CSS and JavaScript library. We present two screenshots illustrating the functionality of the prototype interface in Figure 3. The left-hand figure shows updates for a specific week that have arisen in a subsequent week. By grouping them together, a user is able to assess the consistency of this update 4 . These updates can be accepted or rejected together, or each can be considered individually in the context of other updates to that data item. The following shows the Links code which updates the main table of fatalities from a table of accepted updates for counts relating to the Lothian health board.
for ( x <--AcceptedUpdates ) [ update sequenced ( y <-v -CovidDeaths ) between ( valid_from_date , forever () ) where ( x . week == y . week && x . category == " Lothian " ) set ( count = x . new_value , file_id = x . new_id ) ]) ; The double arrows, <--and <-v-, indicate iteration over the rows of the named tables, with <-v-indicated that the table is a temporal table. The keyword sequenced indicates that this update should result in the modification of one record and the insertion of a new record as illustrated in Figure 1. To write this query in SQL for a non-temporal database would be more complex, requiring explicit updates and insertions.
The right-hand screenshot in Figure 3 shows a provenance query on a single data item. For the updates on this data item, it is possible to see the updates in the context of other updates that occurred in the same week. Other provenance queries can be done on data categories (such as queries 5, 6 and 7 above), and a similar approach can be applied to weeks. The final menu item allows for queries such as query 4.
The prototype has taken around 120 hours to develop to date, approximately 1 person month of effort by the first author, who was not previously familiar with Links. It consists of around 1800 lines of Links code, as well as supporting CSS and JavaScript code. Reuse of existing code will make the implementation of additional queries less time-consuming.

Conclusion
We have developed a prototype curation interface in Links to demonstrate and investigate curation functionality for a selected dataset with interesting features relating to data update. Links, as a cross-tier programming language, has provided a typed and functional language for implementing all of the appearance of the web interface (using the Bootstrap library), the logic of the interface and querying of the database.
By using Links, we have avoided the need to code temporal features in SQL for databases without temporal features, to transition to a database such as MariaDB [7] which has temporality, or to deal with the integration errors that occur during conventional web development using SQL.
Another option would be to use a temporal middleware/stratum translator that maps temporal SQL queries to plain ones [11]. This requires the same kind of information about the database schema that Links requires, but does not provide the advantages of language integration and type checking that we get from Links.
We have successfully created an interface that supports a number of queries and further work involves determining how to support the generation of a curation interface with an arbitrary database schema where selected tables have temporal features.


Feature Selection Tutorial with Python Examples

In Machine Learning, feature selection entails selecting a subset of the available features in a dataset to use for model development. There are many motivations for feature selection, it may result in better models, it may provide insight into the data and it may deliver economies in data gathering or data processing. For these reasons feature selection has received a lot of attention in data analytics research. In this paper we provide an overview of the main methods and present practical examples with Python implementations. While the main focus is on supervised feature selection techniques, we also cover some feature transformation methods.

Introduction
In data analysis, objects described using multiple features may sometimes be described using a subset of these features without loss of information. Identifying these feature subsets is termed feature selection, variable selection or feature subset selection and is a key process in data analysis. This paper provides a tutorial introduction to the main feature selection methods used in Machine Learning (ML). While excellent reviews and evaluations of feature selection methods already exist [11,23] our main contribution is to provide examples of these methods in operation along with links to Python notebooks that implement these methods.
Feature selection is important because it can deliver a number of benefits: • Better classifiers: The obvious benefit of feature selection is that it will improve accuracy because redundant or noisy features can damage accuracy. Perhaps surprisingly, improvements in accuracy can be quite limited because powerful ML techniques are designed to be robust against noise.
• Knowledge discovery: Perhaps the most enduring benefit of feature selection is the insight it provides. Identifying influential features and features that are not useful teaches us a lot about the data.
• Data Gathering: In domains where data comes at a cost (e.g. Medical Diagnosis, Manufacturing), identifying a minimal set of features for a classification task can save money.
• Computational Cost: Identifying minimal feature subsets will allow for simpler models that will cost less to set up and run.
• The Curse of Dimensionality: In theory, according to the Curse of Dimensionality, the amount of data required to build a classifier increases exponentially with the number of features.
Feature selection is most effective in the context of supervised machine learning (classification/regression) where the availability of labelled examples can drive the selection process. The methods we cover are summarised in Figure 1. Other surveys of feature selection [23,11] divide feature selection methods into three categories and we follow the same structure: • Wrappers are feature selection methods where the classifier is wrapped in the feature selection process. This wrapping allows classification performance to drive the feature selection process. This has the advantage of tying the feature selection to classifier performance but this comes with a significant computational cost as very many classifier variants will be evaluated during the selection. • Filters cover methods that use criteria other than classifier performance to guide feature selection. Typically a filter provides a feature ranking and then a selection policy uses this ranking to select a feature subset. • Embedded methods refer to any method where the feature selection emerges as a by-product of the classifier training process. For instance, training a decision tree will almost always select a subset of the available features to build a tree. For completeness we also cover some dimensionality reduction methods that transform the data into a reduced dimension space rather than select a subset of features. In section 7 we cover Principle Component Analysis (PCA) and Linear Discriminant Analysis (LDA) for projecting data into lower dimension spaces. These are not feature selection methods in the sense that the original feature representation is left behind.
Before working through the details of the Feature Selection methods the paper begins with a short discussion on the implications of The Curse of Dimensionality. Then the evaluation methodology used in the paper is presented in Section 3. The main material on Feature Selection methods is covered under the categories of Wrapper methods (Section 4), Filter strategies (Section 5) and Embedded methods (6). Section 7 provides a brief description of PCA and LDA as already mentioned.

The Curse of Dimensionality
Before proceeding it is worth briefly discussing the implications of the Curse of Dimensionality for ML. The term was coined by Richard Bellman in 1961 and refers to a number of phenomena associated with data described by many features [1]. For our purposes there are two theoretical issues.
The first is that the number of samples required to build a model may increase exponentially with the number of features (dimensions). The second is that the variation in distance between arbitrary points decreases as more dimensions are added.
The first of these issues is illustrated in Figure 2. This figure shows plots of 20 random data points in 1D, 2D and 3D. As the dimension increases the data gets more and more sparse. A consequence of this is that the number of samples required to cover a phenomenon increases exponentially with dimension. This is less of a problem in practice because real data is unlikely to occupy all of the space, instead it will occupy a lower dimension manifold in the space. So the intrinsic dimension of the data is likely to be considerably less than the full dimension [5]. The PCA example in Figure 18 also illustrates how the intrinsic dimension can be less than the number of features. Figure 2: 20 random data points in 1D, 2D and 3D space. These plots show how data becomes increasingly sparse as the dimension is increased.
The second issue is that, somewhat paradoxically, the more features used to describe the data the more similar everything appears. The box plots in Figure 3 illustrate this. The plots show the distribution of Cosine similarities between a probe point and 1,000 random points in 5D, 10D and 20D spaces. As the dimension increases the variation in similarity/distance decreases.
In addition to these theoretical problems with having more features than is absolutely necessary, there are also practical problems to be considered. For most ML algorithms, the computational cost will increase with the number of features. As will the cost of gathering the data in the first place. So if the number of features can be reduced then there are strong theoretical and practical reasons for doing so.

Methodology
The datasets used in the examples in this paper are summarised in Table 1. The Segmentation data set  is from the UCI repository 1 , the Penguins dataset was constructed from a larger dataset available on  GitHub 2 and the Harry Potter dataset was constructed by the authors based on the popular Top Trumps  game 3 to illustrate PCA in operation. The Segmentation data comes from an image segmentation task on outdoor images. The ground truth segments the images into seven classes and the instances are represented by 19 features. This is a good dataset for feature selection as there is some redundancy in the data. The Penguins dataset is a three class dataset described by four features [10]. The features are physical parameters (e.g. bill and flipper dimensions) and are strongly correlated so there is some redundancy. If we wish to get an assessment of generalisation performance for an ML system that might be deployed then we need to hold back some data for testing (option (b) in Figure 4). If we wish to assess a few different feature selection alternatives as part of the model development then these should be tested within the confines of training data and cross validation is the most effective way to do this (option (c)). Most of the testing reported in this paper follows this pattern. Indeed, the evaluation testing may involve two levels of cross validation -this strategy is not used here. It should be remembered that if the objective is to perform feature selection as part of the deployment of an ML system then all the available data can be used for feature selection (option (a) in Figure 4). Unless otherwise stated, the classifier used in the evaluations in k-Nearest Neighbour (k-NN) [5]. k-NN is used because it is probably the classifier in popular use most susceptible to noisy or redundant features. So the impact of feature selection will be most evident when it is used in evaluations.
Before proceeding we need to introduce the notation that will be used throughout the paper. Assume we have a dataset D made up of n data samples. D = X, y where y are the class labels. The examples are described by a set of features F where p = |F | so there are n objects described by p features. So the dimensions are X n×p and y p . The objective is to identify a subset S ⊂ F that captures the important information in the dataset. In supervised ML the classifiers would work with data represented by a reduced set of features X n×k , y where k = |S|.

Feature Selection using Wrappers
So the objective with feature selection is to identify a feature subset S ⊂ F to represent the data.
If |F | is small we could in theory try out all possible subsets of features and select the best subset. In this case 'try out' would mean training and testing a classifier using the feature subset. This would follow the protocol presented in Figure 4 (c) where cross-validation on the training data would identify a good feature subset and then this could be tested on the test data. However the number of possibilities is 2 p so exhaustive search quickly becomes impossible.
Nevertheless this is how a Wrapper feature selection strategy works with the important modification that the search can be greedy or stochastic rather than exhaustive. The general idea is shown in Figure  5(a), the classifier is wrapped in the feature selection process, i.e. classifiers trained using the feature subsets are used in the search process. The feature subsets will be evaluated using hold-out testing or cross-validation testing on classifiers built using the data. The main search strategies used with Wrappers are: • Exhaustive Search evaluates every possible feature subset. If the number of features to be considered is small it will be possible to consider all feature combinations. However, if p > 20 there will be millions of feature subsets to considered and an exhaustive search will not be practical.
• Sequential Forward Selection (SFS) starts with no features selected and all classifiers incorporating a single feature are considered (see Figure 6 (a)). The best of these is selected and then two feature combinations including this feature are evaluated. This process proceeds, adding the winning feature at each step, until no further improvements can be made.
• Backward Elimination (BE) proceeds in the opposite direction to FSS, it starts with all features selected, considers the options with one feature deleted, selects the best of these and continues to eliminate features. Again, the process is terminated when no improvements can be made.
• Stochastic Search methods such as genetic algorithms or simulated annealing can readily be applied to Wrapper feature selection. Each state can be defined by a feature mask on which crossover and mutation can be performed [22]. Given this convenient representation, the use of a stochastic search for feature selection is quite straightforward although the evaluation of the fitness function (classifier accuracy as measured by cross-validation) is expensive.
Our exploration of Wrappers will focus on SFS and BE. These are greedy strategies that explore the search space of possible feature subsets as shown in Figure 6. SFS starts with an empty set and proceeds forward considering classifiers built on single features. The best of these is selected and then pairs of features incorporating this feature are considered. The process could terminate when the addition of a new feature doesn't result in any improvement. As the name suggests, Backward Elimination works in the opposite direction. It starts with a full set of features ( Figure 6 (b)) and eliminates the least useful feature at each step. For both SFS and BE, the feature subsets are evaluated using cross-validation on the training data. As stated in Section 3, the classifier used is k-NN.
Both methods have their own advantages and disadvantages. SFS is inclined to require less computation as the models being evaluated are smaller, typically a classifier with a small number of features will take less time to train and test. SFS is inclined to select less features; this parsinomy is typically an advantage. On the other hand, because BE starts with larger feature sets, it can do a better job of assessing how features work in combination.
In the Appendix a link is provided to code to run SFS and BE in Python. The evaluation is on the Segmentation dataset and the results are shown in Figure 7. On the left we see a plot of accuracy on the training set as the SFS proceeds. In this case the search is allowed to run to the end but it is evident that accuracy stops improving after seven features.
The overall results for SFS and BE are shown in Figure 7 (b). SFS selects seven features and 11 are selected by BE. Both feature subsets result in improved accuracy on the training data but only the SFS subset results in better accuracy on the test data. Indeed the gap between train and test accuracy for BE is evidence of overfitting -the selection process has fitted too closely to the characteristics of the training data at the cost of generalisation accuracy. Indeed overfitting is recognised to be a problem with Wrapper-based feature selection [22].

Filter Strategies
Figure 5 (a) shows how Wrapper strategies use the classification algorithm in the feature selection process. Figure 5 (b) shows that Filter strategies do not use the classifier for feature selection, instead a separate evaluation function is used. The fact that Filters are independent of the classifier is a mixed blessing. It means that Filters can be much faster than Wrappers but the selected features may not be in tune with the inductive bias of the classifier.
In the next subsection we provide some detail on the operation of a basic Filter strategy. Then we cover the Relief Algorithm and Correlation-Based Feature Selection, two Filter strategies that have received a lot of attention in recent years.

Basic Filters
A basic Filter will entail a feature scoring mechanism and then a selection strategy based on these scores. The scoring mechanism needs to quantify how much information the feature has about the outcome. The selection strategy might be: • Select the top ranked k features, • Select top 50%, • Select features with scores > 50% of the maximum score, • Select features with non-zero scores.
In this analysis we consider the Chi-square statistic and information gain for scoring. The Chi-square statistic is a measure of independence between a feature and the class label. If samples are organised into a contingency table as shown in Figure 8, how different are the cell counts to what would be observed by chance? The data in Figure 8 (a) suggests that handedness is independent of gender because the proportions are the same. The data in (b) suggests that gender is predictive of handedness. The Chi-square statistic allows us to quantify this: The statistic is a sum over the m cells. For each cell we consider the difference between the observed count O i and the expected count E i if the feature and the class were independent. In Figure 8 (a) this difference would be zero because the feature and the class are independent. In (b) there would be a difference so the statistic would be positive. In general, the greater the dependence the larger the statistic. If the feature values are numeric rather than categorical then the feature values can be binned to enable the construction of the contingency table [15]. Information gain is an alternative information-theoretic measure quantifying the information a feature contains about a class [16]. In Figure 8 (b) by knowing the gender we gain information about handedness. In a binary classification scenario, let's assume the probability of a positive and negative outcomes are respectively p and q. Then the entropy of a dataset based on these proportions is: then the information gain for any feature f in the dataset in terms of the class label is: As with the Chi-square statistic, information gain (I-Gain) allows us to rank features for the purpose of feature selection. This is illustrated in Figure 9 (a). This shows the Segmentation features ranked by both measures. A link for this code is provided in the Appendix. The plot shows the scores sorted by I-Gain score. It is clear that the scores are well correlated (Pearson correlation score of 0.86) so feature subsets selected based on these scores should be reasonably similar.
This does prove to be the case when we look at the performance of classifiers built with feature subsets based on these rankings. In Figure 9 (b) we see the results of a range of top k selection policies (k = 3, 6, 10, 15). At k = 10 both scores select a feature subset that produces accuracy on the test set equivalent to that obtained with the full feature set. The evaluation strategy here conforms to pattern (b) in Figure 4, the feature scoring is done using the training data and then tested on the test set.

Combining Filters and Wrappers
The results in Figure 9 show that initially performance improves as features are added based on the ranking generated by the filters. However, this improvement tails off and eventually no improvement results from the addition of 'poorer' features. Indeed these features may damage performance. This suggests a hybrid Filter/Wrapper strategy whereby a Filter is used to rank the features and then a Wrapper is used to identify the optimum feature subset.
This hybrid strategy is shown in operation in Figure 10. The dataset has been split into train and test sets of equal size. The training set is used to estimate I-Gain scores for all features, these are shown in blue. Then classifiers are trained with feature sets of increasing size. The performance of these feature subsets are scored on the training set using cross validation and on the test set using hold-out testing. After the addition of nine features the performance on the training set stops improving (indicated with a green X). This hybrid strategy would select this as the optimum feature subset.

Relief Algorithm and Variants
The Relief family of algorithms deserve mention because, as Filter methods, they have the advantage of speed while scoring features in the context of other features [17,18]. Relief algorithms belong to the k-NN paradigm in ML. A k-NN analysis is used to score or weight features. The idea is to take each sample in the dataset (or a subset) and find its nearest neighbour of the same class and nearest unlike neighbour -these are termed the nearHit and the nearMiss. Then the general principle is: • For the nearMiss (nM ) increment the feature weights; weights for unmatching features will be incremented more.
• For the nearHit (nH) decrement the feature weights; weights for unmatching features will be decremented more.
The idea is that this will pull matching instances closer together and push unmatching instances apart. This is illustrated in the 2D example shown in Figure 11. The weights should be adjusted to bring x and nH closer together while pushing nM away. Comparing x and nM , they match more on f2 than on f1 so the weight for f1 will be incremented more. Considering x and nH the opposite happens, f2 is decremented more than f1, so the overall effect is that f1 scores better than f2. This is achieved with the following update function where x is the query, nM is the nearMiss, nH is the nearHit and w f is the weight for feature f .
This achieves what we want because the feature value differences for matching features will be smaller than those for unmatching features. Figure 11: An illustration of the principles underlying Relief in a 2D space. x is the query, nM is the is the nearMiss, nH is the nearHit. f1 should be preferred over f2.
This process is repeated multiple times to produce a set of feature weights with 'good' features having high weights. Implementation details of the Relief family of algorithms are provided by Urbanowicz et al. [25]. A link to sample code for running Relief is provided in the Appendix. The results are summarised in Figure 12. On the left we see Relief scores for the segmentation dataset compared with I-Gain scores. The Spearman correlation is 0.91 so both scores are well correlated as is evident from the plot. The plot suggests that there is a clear partition between the first 11 features and the remainder so we test the accuracy of a classifier built using just these 11 features. The results on the right show that this does result in a small improvement in accuracy compared with using all features.

Correlation-Based Feature Selection
Correlation Based feature selection (CFS) is a filter strategy that relies on the principle that "A good feature subset is one that contains features highly correlated with (predictive of) the class, yet uncorrelated with (not predictive of) each other" [12]. The feature-class correlation indicates how representative of the class that feature is while the feature-feature correlation indicates any redundancies between the features. CFS works by assigning a merit value based on feature-class and feature-feature correlations to each feature subset which becomes the measure by which subsets are evaluated. The merit score for a feature subset S is: where k = |S|, r f f is the average correlation between the features values in the subset (f ∈ S) and r cf is the average correlation between the values for the selected features and the class label.
The correlations can be measured using techniques such as symmetrical uncertainty based on information gain, feature weighting based on the Gini-index, or by using the minimum description length (MDL) principle [12]. Information gain based methods work well and hence the symmetrical uncertainty score is commonly used in CFS implementations.
CFS can work with any search strategy in a similar way to wrapper strategies, but rather than evaluating based on accuracy as in Section 4, the evaluation will be based on the merit score. For example, when using sequential forward selection, all single features merit will be evaluated from which the best will be selected. All two feature combinations which include this first feature will then be evaluated using the merit score and so on until there is no more improvement in the merit score.
CFS shows a tendency to favour small subsets with moderate accuracy. The CFS implementation provided by [20] utilises a Best First search which continues the search until five consecutive nonimproving feature subsets are found. Therefore, even after the merit starts decreasing, the search continues. Figure 13 shows the benefit of this as it can be seen that for both the segmentation and the penguin datasets, the hold-out accuracy from using the extra features improves in comparison to evaluating the performance at the point where merit score is highest. In both datasets, CFS has led to a drop in the hold-out accuracy compared to using the full feature subset, however has selected a smaller subset than other techniques such as Relief-F. Hence CFS may be a good technique for feature reduction. A link to sample code for running CFS is provided in the Appendix.

Embedded Methods
In this section we cover feature selection methods that emerge naturally from the classification algorithm or arise as a side effect of the algorithm. We will see that with Decision Trees and Logistic Regression feature selection can be an integrated part of the model building process. Then with Random Forest, we will see how feature importance scores can easily be generated from the model.

Decision Trees
The construction of a Decision Tree from a data set will very often entail feature selection as some of the features will not appear in the tree. Features not included in the tree are effectively selected out. We show an example of this on the Penguins dataset in Figure 14.
In this example the dataset has been divided 50:50 into train and test sets. This tree has been trained on the training data and has 93% accuracy on the test data (see links in Appendix). This dataset has four features, flipper_length, bill_length, bill_depth and body_mass. It is clear from the tree in Figure 14 that three of the four features are selected, body_mass is not selected.
This tree has been constructed with the default scikit-learn parameters so there is no pruning. It is normal in Decision Tree learning to constrain (i.e. prune) the size of the tree to prevent overfitting. The use of pruning to prevent overfitting will push the feature selection further as even less features will be selected in smaller trees.

Logistic Regression: Lasso
In multivariate linear models such as linear regression or logistic regression, feature selection can be achieved as a side effect of regularization. In ML regularization refers to mechanisms designed to simplify models in order to prevent overfitting. Thus regularization can cause features to be deselected. Elastic net and Lasso are popular regularization methods for linear models. Here we will provide an overview of how Lasso works [24] and present examples of Lasso in operation. Starting Figure 14: A decision tree for the Penguins dataset. While the data is described by four features only three are selected.
with the basics, a multivariate regression model works as follows: The dependent variable y is a linear function of the input features; for each feature x i the weight of that feature is determined by the corresponding β i parameter. For binary classification problems ([0,1] labels) we can use logistic regression where the dependent variable is the log odds that an outcome variable is 1. If pr is the probability that the label is 1 then pr 1−pr is the odds.
So logistic regression provides a class probability: Regularization prevents overfitting by limiting model capacity; this is done by limiting the size of weights. The two options are L 1 or L 2 regularization: So the β parameters in (8) are fitted to the training data subject to the constraints in (9) or in (10). It transpires that when an L 1 regularization is used the weaker weights will go to zero, i.e. those features will be deselected. There is an excellent explanation of why this happens in the original Lasso paper by Tibshirani [24].
To demonstrate this on our sample datasets we reduce them to binary classification problems to make the overall process more transparent. However, feature selection using Lasso also works with multiclass problems. The results are shown in Figures 15 and 16. Because the datasets have been reduced to just two classes (Cement and Window for Segmentation and Adelie and Chinstrap for Penguins) the accuracies are higher than for the multi-class scenario. The extent of the feature reduction with Lasso is controlled by the regularization parameter C. Results are included for two levels of regularization, C=10 and C=1. C=10 results in less regularization so more features are retained. In both cases the default regularization results in too much feature reduction and generalization accuracy is reduced. For the Penguins dataset just two features are retained while three are retained in the Segmentation dataset (see Figure 15). The milder regularization retains more features resulting in no loss of generalization accuracy.

Random Forest Feature Importance
Ensembles, the idea that a committee of classifiers will be more accurate than a single classifier, are central to modern ML. It has been known for hundreds of years that a committee of decision makers will be better than an individual [6]. In ML an ensemble of classifiers voting on an outcome will be more accurate than a single classifier provided some conditions are met. Two ensemble methods, gradient boosting [8] and random forests [3] represent the state of the art in supervised ML. Breiman [3] has shown that, as a supplementary benefit of the effort required to build the random forest, the ensemble offers estimates of generalisation accuracy and feature importance. In order to explain how these estimates of feature importance work we need to go into some detail on how random forests work. In order for an ensemble to be effective, there needs to be some diversity among the ensemble members. If not the ensemble will be no better than the individual members (classifiers). If we have a dataset X n×p of n samples described by p features with class labels y p then we have two basic strategies for training diverse classifiers: • Bagging: We can train each classifier with different training sets drawn at random with replacement from the available data. If these 'bagged' training sets are of size n then some samples will be selected multiple times and some not at all. For each training set, roughly 37% of samples will not be selected, i.e. out-of-bag (OOB). • Random Subspacing: The other strategy for ensuring diversity is to work with subsets of features rather than subsets of samples. With random forest, only a subset of features are available for consideration at each split point in the construction of a tree. This subset might be quite small, for instance √ p.
Random forest (RF) uses both of these strategies together to ensure diversity. A typical RF could contain 1,000 trees. The samples that are OOB in these trees can be used to get an estimate of generalisation accuracy for the RF without the need to hold back test data from the training process. These OOB samples can be used to generate feature importance scores. For each of the p features in the OOB samples for a given tree, the values for that feature can be randomly permuted and the revised classifications for those samples can be saved. Then, for the whole ensemble, the impact of this feature value shuffling can be assessed.
If a feature is not important, then the impact of this shuffling will be minimal. For predictive features this shuffling will have a significant impact. Furthermore, and this is important for feature selection, this feature importance is being assessed in the context of other features. This contrasts with the basic filter methods described in section 5.1 where features are scored in isolation.
RF feature importance scores for the Penguin and Segmentation datasets are shown in Figure 17. I-Gain scores are also shown and these correlate well with the RF scores (0.8 for Penguins and 0.92 for Segmentation). For the Penguins dataset, the RF score ranks flipper_length highest. Because RF feature importance considers features in context, this may indicate that this feature contains information not available in the other features. The same may be true for the HUE_MEAN and EXGREEN_MEAN features in the Segmentation data which are also given higher rankings.

Feature Transformations
So far we have focused on feature ranking and feature subset selection methods as that is the main focus of the paper. However, it is also worth mentioning feature transformation methods such as Principal Component Analysis (PCA) as these methods are also used for dimension reduction.
The dominant feature transformation technique is Principal Components Analysis (PCA) that transforms the data into a reduced space that captures most of the variance in the data. PCA is an unsupervised technique in that it does not take class labels into account. By contrast Linear Discriminant Analysis (LDA) seeks a transformation that maximises between-class separation (Section 7.2).
As with feature selection we are concerned with datasets of n objects described by p features. Unfortunately, with feature transformation methods, it is not unusual to represent the data as a featureobject matrix X p×n where each column represents an object. This contrasts with the object-feature format X n×p popular in supervised ML where each row is an object. For consistency with the rest of this paper we will stick with the object-feature format X n×p . The objective with Feature Transformation is to transform the data into another set of features F where k = |F | and k < p, i.e. X n×p is transformed to X n×k . Typically this is a linear transformation W p×k that will transform each x i to x i in k dimensions.

Principal Component Analysis
In PCA the transformation described in Equation 11 is achieved so that feature f 1 is in the dimension in which the variance on the data is maximum, f 2 is in an orthogonal dimension where the remaining variance is maximum and so on. Central to the whole PCA idea is the covariance matrix of the data [13]. The diagonal terms in C capture the variance in the individual features and the off-diagonal terms quantify the covariance between the corresponding pairs of features. The objective with PCA is to transform the data so that the covariance terms are zero, i.e. the new dimensions are independent. The overall process is as follows: 1. Calculate the means of the columns of X.
2. Subtract the column means from each row of X to create the centred matrix Z.
3. Calculate the covariance matrix C = 1 n−1 Z T Z. 4. Calculate the eigenvectors and eigenvalues of the covariance matrix C.
5. Examine the eigenvalues in descending order to determine the number of dimensions k to be retained -this is the number of principle components.
6. The top k eigenvectors make up the columns of the transformation matrix P which has dimension (p × k).
7. The data is transformed by X = ZP where X has dimension (n × k).
The i th diagonal entry in C quantifies the variance of the data in the direction of the corresponding principal component. Dimension reduction is achieved by discarding the lesser principal components, i.e. P has dimension (p × k) where k is the number of principal components retained.
We illustrate PCA in operation with the example shown in Table 2 and Figure 18. The code for this is linked in the Appendix. This example is based on the Top Trump childrens' game. Each object is a card representing a Harry Potter character described by five features. In this dataset there are 22 cards so n = 22 and p = 5. Figure 18(a) shows the variance in the data captured by the first four principal components (PCs). The first two PCs together account for 81% of the variance in the data so when in Figure 18(b) we plot the data in terms of these two PCs most of the variance in the data is retained.
While PCA is the established method for unsupervised dimension reduction there are other methods also in use. Singular Value Decomposition (SVD), a closely related matrix factorization method, is popular in text analytics [4] and Latent Dirichlet Allocation [2] is popular for topic modelling.  Figure 18: PCA on the Harry Potter dataset shown in Table 2. (a) The variance explained by the first four principal components (original data has five features). (b) A 2D plot of the data in the first two principal components.

Linear Discriminant Analysis
PCA on the Penguins dataset is shown in Figure 19(a). Given that PCA is designed to project the data into dimensions that capture the variance in the data it should not be surprising that it does not do a great job of separating the classes. Figure 19(b) shows Linear Discriminant Analysis (LDA) on the same dataset. LDA takes the class labels into account and seeks a projection that maximises the separation between the classes. The objective is to uncover a transformation that will maximise between-class separation and minimise within-class separation. To do this we define two scatter matrices, S B for between-class separation and S W for within-class separation: where n c is the number of objects in class c, µ is the mean of all examples and µ c is the mean of all examples in class c: The components within these summations µ, µ c , x j are vectors of dimension p so S B and S W are matrices of dimension p × p. The objectives of maximising between-class separation and minimising within-class separation can be combined into a single maximisation called the Fisher criterion [7,9]: i.e. find W ∈ R p×k so that this fraction is maximised (|A| denotes the determinant of matrix A). This matrix W LDA provides the transformation described in equation 11. While the choice of k is again open to question it is sometimes selected to be k = |C| − 1, i.e. one less than the number of classes in the data. Solving the optimization problem presented in equation 15 is a research topic in its own right [21,14] so we won't explore it in more detail here.
In addition to projecting the data into a reduced dimension space LDA can also be used for classification. In the LDA space each class c ∈ C is modelled by a multivariate Gaussian distribution P (X|y = c). So a query sample x i can be assigned to the class c LDA for which the probability P (y i = c|x i ) is largest. This is effectively a Naive Bayes classifier: In the code linked in the Appendix, LDA has 97% accuracy on the hold-out set. Half the Penguins data is used to build the LDA model shown in Figure 19 and the other half is used for testing.

Discussion & Recommended Strategies
If the objective is to identify an effective feature selection strategy then there are many methods to choose from. Even though these methods have different inductive biases we generally see good correlations between the feature rankings on the two datasets we consider. This shows that all these methods have some merit in identifying good features. Our objective is not to identify a single best strategy as this will depend to some extent on the data. Given this, we propose the following methodology for feature selection on a new dataset.
1. Preliminary Analysis: Use RF feature importance to rank all features (e.g. as shown in Figure 17). This will provide some insight into what features are important and it may also indicate features that can be dropped from further consideration. We recommend the RF method as it considers features in context. If the objective of the exercise is to gain an insight into the data then the analysis may stop at this point. 2. Subset Selection: If the objective is to identify an effective subset for classification then a subset selection strategy is required. The main argument against a Wrapper strategy is the computational cost. With advances in computing resources this is now less of an issue so we recommend a Wrapper strategy as described in Section 4. If the number of features still in consideration is not high then BE should be considered. If the set of possible features is large then SFS may be the pragmatic choice. The hybrid strategy described in Section 5.1.1 could also be considered.
So our overall recommendation for feature subset selection is to use a Wrapper strategy. This would be in tune with the current model selection protocols in ML [19]. However, the recommendation for Preliminary Analysis is also important. Early in the analysis of new data it will be helpful to use a Filter strategy to gain some insight into the data. This Filter analysis will be independent of any specific classifier models that might be used subsequently.

Conclusions
The objective for this tutorial paper was to provide an overview of popular feature selection methods, describing how they work and providing links to Python implementations. It was not our intention to offer a comparative evaluation to identify the best methods; that is done very well elsewhere [11,23]. Instead, our objective was to provide a stepping stone to help researchers get started with feature selection on their own datasets.
In the Introduction we listed objectives for feature selection other that to improve classifier performance. Indeed, the examples in this paper suggest that feature subset selection may not have a big impact on classifier performance -this is borne out by other studies [11]. Instead feature selection can deliver other benefits through savings in data gathering an model execution. Perhaps, the biggest benefit of feature selection is the insight it offers into what is important in the data under analysis.


Structured Prediction in NLP -- A survey

Over the last several years, the field of Structured prediction in NLP has had seen huge advancements with sophisticated probabilistic graphical models, energy-based networks, and its combination with deep learning-based approaches. This survey provides a brief of major techniques in structured prediction and its applications in the NLP domains like parsing, sequence labeling, text generation, and sequence to sequence tasks. We also deep-dived into energy-based and attention-based techniques in structured prediction, identified some relevant open issues and gaps in the current state-of-the-art research, and have come up with some detailed ideas for future research in these fields.

Introduction
In structured prediction, we seek to predict structured outputs, which are essentially anything other than a scalar or categorical quantity. Many prediction problems in natural language processing, such as tagging, parsing, coreference resolution, and machine translation, require the prediction of outputs that are structured. For example, predicting a sequence of part-of-speech labels, a parse tree, a partition of a document's noun phrases, or a well-formed sentence, respectively. Intuitively, these sorts of predictions differ from those made in multi-class classification, in that the objects being predicted have an internal structure (unlike the discrete labels multi-class classification problems). This structured output is often found to be a useful intermediate representation for other applications. For example, downstream reasoning about the content of a news article may require predicting relational data about the individuals and events discussed in the text. The number of possible outputs for a particular input x also tends to be exponential in the size of x, which makes the problem challenging. Another major challenge in structured prediction is that often the inference becomes intractable.

HMMs, MEMMs, CRFs and Structured Perceptron
Hidden Markov Models [1] is a probabilistic graphical model which uses first order markov chain assumption and dependence of observed data only on emission states. HMM allows us to talk about both observed events and hidden events in our probabilistic model. The probability of a sequence(length=T ) is modeled as follows: p(y|x, θ) ∝ p(x, y, θ) = p(y 1 ) The forward algorithm allows to efficiently calculate the MLE or MAP estimate and Viterbi-style dynamic programming algorithm [2] can be used for inference. A clear drawback is that transition probabilities and emission probabilities do not encode any information other than the previous tag and also HMMs suffer from exposure bias problem and hence are often found to be quite inefficient.
Maximum Entropy Markov Models (MEMMs) [3] define a probabilistic model of sequences y ∈ Y = V T given an input sequence x, also of length T . The probability of a sequence is modeled as the product of locally normalized per-label distributions, as follows: MMEMs assume a first-order Markov assumption which means it assumes that the label y t given label y t−1 is independent of all the previous labels. This independence assumption allows for the arg max sequence to be calculated exactly with a Viterbi-style dynamic programming algorithm, similar to the inference in Hidden Markov Models. Also, this independence assumption gives features which only depend on x t , y t , and y t−1 for each t. As is evident from probability of sequence equation, the probability of a sequence y for an input x is the product of locally-normalized per-label probabilities. This leads to a problem known as label bias. [4] which uses global normalization and specifies the conditional distribution of a random variable Y given a random variable X with respect to the factorization implied by an undirected graphical model over X, Y . Distribution in a CRF following first-order markov property can be written as follows:

Condition Random Fields
Unlike MEMMs, the distribution p(y|x) is not the product of locally normalized distributions. It is rather globally normalized, using the partition function, and so this model does not suffer from label bias. Given the Markov assumptions implicit in the model above, we may again find the arg max sequence using a Viterbi-style algorithm. [5] has explained that computing the arg max, marginals or the partition function is usually not algorithmically efficient. Structured Perceptron [6] and structured SVM [7] based approaches only require efficiently compute the arg max, unlike CRFs which require computing many other marginals and partition function. These approaches are non-probabilistic, and they utilize a simple form for the score: Structured Perceptron and structured SVM are trained through gradient based approaches using margin and slack rescaling losses. These approaches do not suffer from exposure bias and label bias problem.

Structured Prediction Energy Networks
Energy based approaches rely on the principle that there is an energy function which assign values to each output y given an input x such that the most compatible y has the minimum energy. Additive nature of energy makes it straightforward to incorporate domain knowledge and hard constraints in the model. Probability based approaches are a subset where probabilities can be thought as normalised energy. Most of the previous approaches assumed a particular graphical models for energy E x (.) which results in an excessively strict inductive bias. Structured prediction energy networks (SPENs) was introduced in [8] as the first framework for structured prediction in which energy is defined using neural networks over possible outputs and gradient based approaches for energy minimization is used for inference. SPENs were found to be very well suited to multi-label classification problems in the NLP domain. The neural network consist of two arbitrary neural network F (x) (feature network) and E(F (x),ȳ) (energy network). Energy network is sum of two terms, E x (ȳ) = E local The SSVM (structured support vector machine) technique is used for training and the loss is :- Where ∆(y i , y) is a error function between prediction and ground truth label and [.] + = max(0, .). Subgradient computation requires loss-augmented inference: y p = arg min y (−∆(y i , y) + E x i (y)) for every training example. SPENs are more expressive and scalable while being less vulnerable to overfitting and performing competitively to previous energy-based approaches. Like most energy networks, the inference involves optimization of E x (y) w.r.t y which limits the practical use of model to an extent. Also, non-convexity of E x (.) or relaxation used to getȳ from y can affect the model performance and convergence. Some of these can be tackled using techniques like inference network [9] and Input Convex Neural Networks [10].
Deep value networks(DVN), introduced in [11], are similar to SPENs but are much easier to train and works even when ∆(y, y * ) is non-continuous and require no convexity constraints. The key idea is that the loss function in every structured prediction problem can be used to define a quantitative value for a configuration as v(x, y) ≈ −∆(y, y * ). The deep network will model v(., .) and hence learn to mimic the loss function. Instead of using max-margin surrogate objective (SSVM) [8] or other complex approaches, this method just do a simple regression during training and has better performance than [8]. Training data ((x, y, v(x, y)) tuples) can be generated via random sampling, generating adversarial tuple, or samples generated during train-time inference. Therefore it needs lesser number of (x, y * ) ground truth pairs for training. Gradient based inference (deep dreaming) is found to iteratively refine prediction. SPEN objective (Eq. (1)) optimisation requires loss augmented inference which may fail to discover margin violations if exact energy minimisation is intractable. This can be tackled using End-to-End learning for SPENs, introduced in [12] where the energy function is discriminatively trained by back-propagating through gradient-based prediction. These are more accurate and allows non-convex energy. The idea is not to do exact energy minimization and instead assume a particular approximate minimisation algorithm and optimize performance of this algorithm. Suppose we chose T step gradient descent as our algorithm for minimization where T is some hyper-parameter. Then, the model's output is y T given by, The energy function is defined identically to the original SPEN paper. However, energy funciton must be twice sub-differentiable and it is not straightforward to implement this model using standard learning libraries. The model loss can be defined as, T −t+1 . Unlike in DVNs, here explicit energy function provides interpretability. Another benefit is that the model outputs inference procedure along with the energy function. The inference procedure has fixed T meaning that the inference time complexity is independent of x. Although it is worth noting that the learned energy may be such that the energy minima doesn't actually represents the best output as our model is learning just to optimise the inference procedure which may not be converging to minima.
The approaches used till now for training SPENs were supervised and required labeled data which are expensive to collect in many problems, so we are now exploring the space of semi-supervised learning where we use domain knowledge in form of reward functions and ranking based supervision. The first approach introduced in [13] is to rank every pair of consecutive candidates obtained from training time gradient-descent inference on y; and update energy network parameters by optimising an objective function if the energy values are not consistent with domain knowledge based ranking. In the above approach we collect training pairs from gradient descent based inference on energy functions, but it has several problems such as not able to get relevant pairwise rank violations, not reaching to a region of high reward or if we have plateaus in our energy functions. To overcome these issues, [14] introduced a new approach where for each example we start with a gradient descent inference output, and then use a randomized search procedure for iteratively selecting a random output variable, if the reward increases more than the margin we return the new sample or else we begin sampling again.
Graph Structured Prediction Energy Networks (GSPEN) [15] was introduced as a combination of classical structured prediction models and SPENs to score an entire set of predictions jointly which allows to both model explicit local and implicit higher-order correlations while maintaining tractability of inference. Inference in GSPENs is a maximization of a generally non-concave function with respect to structural constraints which is an approach inspired by [16]. GSPENs use Frank-Wolfe Inference as its objectives are non-linear while the constraints are linear and use Structured Entropic Mirror Descent for optimization, an approach similar to SPEN optimization with some additional entropy-based constraints. GSPENs are found to outperform SPENs and other baselines on multilabel classification and named entity recognition.

Structured Attention networks
Attention networks are now a standard part of the deep learning toolkit and are found effective approach for embedding categorical inference but they often fail to model richer structural dependencies in end-to-end training. Structured Attention networks [17] was proposed as a simple extension of the basic attention procedure which allow for extending attention to partial segmentations or to subtrees. They explain how they can implement a linear-chain conditional random field and a graph-based parsing model as classes of structured attention networks, which are equivalent to neural network layers. It is shown that provide a structural bias by modelling structural dependencies at the final output layer, most notably in seminal work on graph-based neural architectures [18], [19].
In the structured attention model, the attention distribution p(z|x, q) is defined as conditional random field (CRF) or other graph based model to specify independent structure of z: a vector of discrete latent variables. The CRF is parameterized with clique log-potentials θ C (z C ) ∈ R where the z C indicates subset of z given by clique C, and attention probability is p(z|x, q; θ) = softmax( C θ C (z C )) where x is the input sequence and q is the query. In practice we use a neural CRF, where θ comes from a deep model over x, q. Here also, it is assumed that annotation function f factors into clique annotation functions f (x, z) = C f C (x, z C ) and the context is defined as In short,the attention mechanism is taking expectation of an annotation function f (x, z) with respect to a latent variable z ∼ p, where p is parameterized as function of x and q. Instead of linear-chain CRF, syntactic tree-based attention can also be used for modelling richer structural dependencies using similar approach. Also, unlike previous approaches which add Graphical models as the final layer, they proposes that these can be added within deep networks in place of simple attention layers.
Using the two ways mentioned for structured attention, they experiment on a variety of synthetic and real tasks: neural machine translation, question answering, and natural language inference and found that it outperformed baseline attention models. They also conclude that structured attention leads to learning interesting unsupervised hidden representations that generalize simple attention. Structural attention network for graph [20] is a novel approach to learn node representations for graph modelling. It uses a graph-based attention network, to pay attention to the topology of the graph.
Graph classification is a problem with many practical applications and an approach [21] using structural attention was proposed recently. It's the first model to uses attention to learn representations for general attributed graphs. A major problem in graph-based classification was that graphs are mostly noisy and large and processing the entire graph can inadvertently caused noise to be introduced into the calculated feature and also computationally inefficient which increased the need for structured attention in graphs. The approach used an RNN based model that processes only a portion of the graph by adaptively selecting a sequence of "informative" nodes. Furthermore, the attention-guided walk mechanism relies only on local information from the graph which keeps computation costs low since there is no need to load the entire graph into memory. With various experiments on real-world datasets, they concluded that the proposed method is competitive against various well-known methods in graph classification even though our method is limited to only a portion of the graph.

Tree LSTM
Tree LSTMs [22] were proposed to generalize LSTMs (chain-structured) to tree-structured network topologies and they were found to outform all LSTM baselines on predicting semantic relatedness of two sentences and sentiment classification and hence found superior for representing sentence meaning. Tree-LSTM, composes its hidden state from an input vector and the hidden states of arbitrarily many child units unlike hidden state of previous time step in normal LSTM.
Recently, Tree-LSTMs have been widely applied in structured prediction tasks like dependency and constituency parsing. Works on Recursive LSTM Tree have been proposed for feature Representation of parse trees in dependency and constituency parsing [23], [24], [25]. These approaches have removed the need of handcrafted structural features and have shown better performance as well.
Recently, many works in the community have tried to improve Tree-LSTMs [26] proposed encoding variants of decomposable attention inside a Tree-LSTM cell for dependency and constituency trees. To avoid the bias problem of the root node dominance, capsule tree-LSTM [27] was proposed, which uses dynamic routing algorithm to build sentence representation by assigning different weights to nodes according to their contributions to prediction.

NER, POS and other Sequence Labelling tasks
Linguistic sequence labeling tasks like POS tagging and named entity recognition (NER), are one of the first stages in language understanding and its importance has been well recognized. Many NLP systems like coreference resolution and syntactic parsing are becoming more sophisticated by utilizing output information of POS tagging or NER.
Linear statistical models like HMMs, MEMMs and CRFs give high performance on such sequence labelling tasks by using hand-crafted features and task-specific resources like English POS taggers benefit from carefully designed word spelling features. However, such task-specific knowledge is costly to develop. Due to this, deep-learning based approaches which use word embeddings as features are being applied to these tasks and are giving great results. Several RNN together with its variants such as long-short term memory (LSTM) [28] and gated recurrent unit (GRU) [29] have been proposed to solve sequence labeling tasks like POS tagging [30] and NER [31], [32]. As these models depend a lot on neural embeddings, often its performance drops rapidly and so new approaches combining linear statistical models on top of RNN-based models. Approaches like [33], [34] combine character and word-level representations, feed them into a BiLSTM and then use a CRF on top of it to jointly decode labels for the whole sentence and they give great accuracies in sequence labelling tasks. Hierarchical RNN based encoders along with CRFs have also been used for sequence labelling [35]

Semantic Parsing and Semantic analysis
Semantic Processing involves the understanding the meaning of phrases, sentence or documents. Research have directed attention towards learning word representation methods from a large unlabeled corpus and claim to capture the meaning of words such as Word Embedding [36] and GloVe [37].
Research have also shown that [38] semantic structures helps in defining effective word embedding. SENSE [38] uses hierarchically organized data that could be used in generating semantic structures to exploit the semantic relationship such as parent, brother and child semantic attributes to learn effective embedding. This explicitly uses the external semantic structured information to learn the word representations by optimizing the prediction ability between target word and context. Semantic Parsing is task of mapping the natural language to logical representation on which we can support various application such as machine translation, question answering, etc. Semantic role labeling, a second-order structured prediction task is one such application of semantic parsing also known as Shallow semantic parsing, in which we are concerned with labelling phrases of sentences with its corresponding semantic roles, but not encovering deeper compositional semantics of text. Approached based on contextualized embeddings, such as ELMo [39], BERT [40], XLM-R [41] have been emerged as state-of-the-art for various structured prediction tasks such as semantic role labelling, chunking etc. Research have also showed that word representation based on the ensembling or concatenation of multiple pretrained embedding and non-contextual embedding can further improve the performance of structured prediction tasks [42].

Structured Prediction in Dependency Parsing
In recent year, there have been more focus transition-based approaches for parsing, which generates one parse tree. Arc-standard parsing starts with the an empty stack and a queue consisting of whole input sequence. At each step, a word input is consumed and corresponding stack operations are applied. At the end whole sentence is consumed and stack contain only ROOT label. Transition based methods have been giving top accuracies for dependency parsing [43] [44] [45]. Neural parsing with global learning and beam search have also come out to be start-of-the-art transition-based parsers [46], which also leverages structured-prediction model to optimize whole sequence of stack actions [44] instead of using local classifier that optimizes each action. There have been efforts in proposing structured prediction model for probabilistic dependency parsing [47], which maximizes the likelihood of arc-standard based action sequence instead of individual actions.
The probability of the action sequence y i is given by above equation. Here o(x, y i , k, a k ) denotes the neural network score for the action a k given x, y i . The probability captures the likelihood of all action sequence instead of individual actions. Results showed that this model outperformed greedy dependency parsers, and also able to have comparable results with small parameter size.

Text generation
The importance of global normalization for text generation was emphasized by [48] which has led to introduction of statistical models like CRFs combined with neural network architectures in text generation domain. Sequential autoregressive models which predict make predictions based on past predictions are the predominant architecture for text generation in a maximum likelihood setup but MLE based training leads to teacher forcing and exposure bias. Feedback loops have been used to overcome this issue where one provides the last predicted token as a feature to the computation of the next state. Recently, [49] proposed modeling temporal correlations as part of the observation model by a neural CRF observation model that leverages word-embeddings to explain local word correlations in a global sequence score. The resultant autoregressive model kept hidden state evolution less affected by observation noise while generating coherent word sequences.
Fully-autoregressive models are state-of-the-art in text generation but beam-searching can not be parallelized, to speedup decoding using parallel generation models assumes independence of output words which leads to problems like repetitions. Markov Transformers [50] proposed a slightly different architecture for modern autoregressive models such that they can parameterize hierarchical CRFs, on which we use refinement based decoding procedures which are parallelizable. Such models are partially-autoregressive, and has trade off between speedup and autoregressive nature of the model which requires finding a best configuration with speedup and performance. With distillation and good configuration this model performs comparable to other parallel decoding models, has good candidate search, and less problem of repetition.
Modeling language as a sequence of discrete tokens is a widely used approach, which is only constraint to sequence dynamics. Recently, syntax driven approach [51] is proposed, where token generation is driven by dependency parse tree with iterative generation procedure. Iterative Expansion Language Models, given a level of dependency parse tree produces tokens for next level of dependency parse tree with expansion placeholders (non-terminal tokens which can be expanded to multiple tokens for next iteration), inference is done by starting from fix root token as first level of dependency parse tree and iteratively generating all levels till terminals are generated, requiring only few iterations and beam-search can be used across iterations. This iterative non-autoregressive model generates text with diversity quality between LSTM and transformers. 7 Future Directions 1. Structured Attention networks [17] proposed an approach to add graphical models anywhere within deep networks in place of simple attention layers. Also, we read about SPENs [8] used as output layers for structured prediction in energy-based models and it may be interesting to explore how to use SPEN layer as as internal neural network layers in the form of attention-based modules (replace CRF based attention module with SPEN based module), using approximate inference methods and end-to-end training mechanism mentioned in [17], [12], and [10]. We may try finding alternatives to ICNN [10] approach which is less restrictive for enforcing convexity or employ a regularization method that enforces convexity as a soft constraint. Also, GLOM [52] mentioned about consensus based attention mechanism which can be modelled using linear-chain CRF with pairwise dependencies. 2. Much work has not been done in the field of seq-to-seq models and Natural language inference using structured prediction based techniques and recently it has been found that transformers [53] give great accuracy on these tasks but it was found in TaxiNLI [54] that many taxonomic categories were found to be difficult to be predicted accurately by transformers in Natural Language inference and question answering. We want to experiment by adding structured prediction based methods on top of the output layer in such seq-to-seq tasks and see which are more robust to all taxonomic categories. Also, we would like to experiment how transformer would work if we replace its normal soft attention layer by structured attention layer. 3. Recent structured prediction approaches that we surveyed like SPENs, DVNs and TreeLSTMs are being applied to a very small set of tasks which are simpler than majority of structured prediction tasks. We would like to extend these ideas to other language understanding tasks where we have to predict a structured output and see if these techniques improve the baselines. There may be some problems in making the model tractable but the end-to-end training mechanisms of these individual methods or application of certain restrictions suggested in ICNNs [10] would make the model training work properly. 4. Many natural language understanding datasets contain annotation artifacts or biases and we would like to explore how various NLP approaches are robust to dataset biases. We believe structured prediction techniques would result in more robust models. We would further like to work on making the models even more robust, come up with new training methods to combat bias, and extending the ideas to other language understanding tasks.

Conclusion
This survey has explored a wide variety of methods of Structured Prediction and its applications in NLP. Our goal has been to study the general usefulness of statistical, graphical, energy-based and attention-based methods to model the structural dependencies in structured prediction tasks with more focus towards such tasks in NLP domain like POS tagging, Named Entity Recognition, Semantic Role labelling and analysis, Dependency and Semantic Parsing and Text generation. Linear statistical and graphical methods like CRFs are effective but output dependencies are modeled by hand, and has significant inductive bias SPENs are its further recent work is a great contribution in the step towards incorporating deep networks and energy-based approaches in structured prediction resulting in more expressive models, and have huge potential for future work in its scalability and application to more complex tasks. Structured Attention is a great approach of adding statistical models in between neural network layers and should be explored with other structured prediction based techniques as well. TreeLSTMs are found to give good accuracy on Dependency and semantic parsing and they should be used in other NLP domains as well like seq-to-seq models using hierarchical encoders and decoders made of TreeLSTMs . Structured prediction methods may have great potential when combined with Transformer [53] which are the current SOTA in most of the NLP tasks.