{'fraction_non_alphanumeric': 0.03342471530999578, 'fraction_numerical': 0.011703922395613665, 'mean_word_length': 4.694686280396278, 'pattern_counts': {'":': 0, '<': 9, '<?xml version=': 0, '>': 8, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 1, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
A Graph-Based Approach to Named Entity Categorization in Wikipedia Using Conditional Random Fields

This paper presents a method for categorizing named entities in Wikipedia. In Wikipedia, an anchor text is glossed in a linked HTML text. We formalize named entity categorization as a task of categorizing anchor texts with linked HTML texts which glosses a named entity. Using this representation, we introduce a graph structure in which anchor texts are regarded as nodes. In order to incorporate HTML structure on the graph, three types of cliques are defined based on the HTML tree structure. We propose a method with Conditional Random Fields (CRFs) to categorize the nodes on the graph. Since the defined graph may include cycles, the exact inference of CRFs is computationally expensive. We introduce an approximate inference method using Treebased Reparameterization (TRP) to reduce computational cost. In experiments, our proposed model obtained significant improvements compare to baseline models that use Support Vector Machines.


Introduction
Named and Numeric Entities (NEs) refer to proper nouns (e.g. PERSON, LOCATION and ORGANI-ZATION), time expressions, date expressions and so on. Since a large number of NEs exist in the world, unknown expressions appear frequently in texts, and they become hindrance to real-world text analysis. To cope with the problem, one effective ways to add a large number of NEs to gazetteers.
In recent years, NE extraction has been performed with machine learning based methods. However, such methods cannot cover all of NEs in texts. Therefore, it is necessary to extract NEs from existing resources and use them to identify more NEs. There are many useful resources on the Web. We focus on Wikipedia 1 as the resource for acquiring NEs. Wikipedia is a free multilingual online encyclopedia and a rapidly growing resource. In Wikipedia, a large number of NEs are described in titles of articles with useful information such as HTML tree structures and categories. Each article links to other related articles. According to these characteristics, they could be an appropriate resource for extracting NEs.
Since a specific entity or concept is glossed in a Wikipedia article, we can regard the NE extraction problem as a document classification problem of the Wikipedia article. In traditional approaches for document classification, in many cases, documents are classified independently. However, the Wikipedia articles are hypertexts and they have a rich structure that is useful for categorization. For example, hyperlinked mentions (we call them anchor texts) which are enumerated in a list tend to refer to the articles that describe other NEs belonging to the same class. It is expected that improved NE categorization is accomplished by capturing such dependencies.
We structure anchor texts and dependencies between them into a graph, and train graph-based CRFs to obtain probabilistic models to estimate categories for NEs in Wikipedia.
So far, several statistical models that can cap-ture dependencies between examples have been proposed. There are two types of classification methods that can capture dependencies: iterative classification methods (Neville and Jensen, 2000;Lu and Getoor, 2003b) and collective classification methods (Getoor et al., 2001;Taskar et al., 2002). In this paper, we use Conditional Random Fields (CRFs) (Lafferty et al., 2001) for NE categorization in Wikipedia. The rest of the paper is structured as follows. Section 2 describes the general framework of CRFs. Section 3 describes a graph-based CRFs for NE categorization in Wikipedia. In section 4, we show the experimental results. Section 5 describes related work. We conclude in section 6.

Conditional Random Fields
Conditional Random Fields (CRFs) (Lafferty et al., 2001) are undirected graphical models that give a conditional probability distribution p(y|x) in a form of exponential model.
CRFs are formalized as follows. Let G = {V, E} be an undirected graph over random variables y and x, where V is a set of vertices, and E is a set of edges in the graph G. When a set of cliques C = {{y c , x c }} are given, CRFs define the conditional probability of a state assignment given an observation set.
where Φ(x c , y c ) is a potential function defined over cliques, and Z(x) = y c∈C Φ(x c , y c ) is the partition function.
The potentials are factorized according to the set of features {f k }.
The original paper (Lafferty et al., 2001) focused on linear-chain CRFs, and applied them to part-of-speech tagging problem. McCallum et al. (2003), Sutton et al (2004) proposed Dynamic Conditional Random Fields (DCRFs), the generalization of linear-chain CRFs, that have complex graph structure (include cycles). Since DCRFs model structure contains cycles, it is necessary to use approximate inference methods to calculate marginal probability. Tree-based Reparameterization (TRP) (Wainwright et al., 2003), a schedule for loopy belief propagation, is used for approximate inference in these papers.

Graph-based CRFs for NE Categorization in Wikipedia
In this section we describe how to apply CRFs for NE categorization in Wikipedia. Each Wikipedia article describes a specific entity or concept by a heading word, a definition, and one or more categories. One possible approach is to classify each NE described in an article into an appropriate category by exploiting the definition of the article. This process can be done one by one without considering the relationship with other articles.
On the other hand, articles in Wikipedia are semi-structured texts. Especially lists (<UL> or <OL>) and tables (<TABLE>) have an important characteristics, that is, occurrence of elements in them have some sort of dependencies. Structural characteristics, such as lists (<UL> or <OL>) or tables (<TABLE>), are useful becase their elements have some sort of dependencies. Figure 2 shows an example of an HTML segment and the corresponding tree structure. The first anchor texts in each list tag (<LI>) tend to be in the same NE category. Such characteristics are useful feature for the categorization task. In this paper we focus on lists which appear frequently in Wikipedia.
Furthermore, there are anchor texts in articles. Anchor texts are glossed entity or concept described with links to other pages. With this in mind, our NE categorization problem can be regarded as NE category labeling problem for anchor texts in articles. Exploiting dependencies of anchor texts that are induced by the HTML structure is expected to improve categorization performance.
We use CRFs for categorization in which anchor texts correspond to random variables V in G and de- Figure 1: The definitions of sibling, cousin and relative cliques, where E S , E C , E R correspond to sets which consist of anchor text pairs that have sibling, cousin and relative relations respectively.
pendencies between anchor texts are treated as edges E in G. In the next section, we describe the concrete way to construct graphs.

Constructing a graph from an HTML tree
An HTML document is an ordered tree. We define a graph G = (V G , E G ) on an HTML tree T HT ML = (V T , E T ): the vertices V G are anchor texts in the HTML text; the edges E are limited to cliques of Sibling, Cousin, and Relative, which we will describe later in the section. These cliques are intended to encode a NE label dependency between anchor texts where the two NEs tend to be in the same or related class, or one NE affects the other NE label. Let us consider dependent anchor text pairs in Figure 2. First, "Dillard & Clark" and "country rock" have a sibling relation over the tree structure, and appearing the same element of the list. The latter element in this relation tends to be an attribute or a concept of the other element in the relation. Second, "Dillard & Clark" and "Carpenters" have a cousin relation over the tree structure, and they tend to have a common attribute such as "Artist". The elements in this relation tend to belong to the same class. Third, "Carpenters" and "Karen Carpenter" have a relation in which "Karen Carpenter" is a sibling's grandchild in relation to "Carpenters" over the tree structure. The latter elements in this relation tends to be a constituent part of the other element in the relation. We can say that the model can capture dependencies by dealing with anchor texts that depend on each other as cliques. Based on the observations as above, we treat a pair of anchor texts as cliques which satisfy the condtions in Figure 1.
Precise definitions of cliques, namely Sibling, Cousin, and Relative, are given in Figure 1. A set of cliques used in our graph-based CRFs are edges defined in Figure 1 and vertices, i.e.
Note that they are restricted to pairs of the nearest vertices to keep the graph simple.

Model
We introduce potential functions for cliques to define conditional probability distribution over CRFs. Conditional distribution over label set y given ob-servation set x is defined as: where Φ SCR (y i , y j ) is the potential over sibling, cousin and relative edges, Φ V (y i , x) is the potential over the nodes, and Z(x) is the partition function. The potentials Φ SCR (y i , y j ) and Φ V (y i , x) factorize according to the features f k and weights λ k as: where the last two terms are due to the Gaussian prior (Chen and Rosenfeld, 1999) used to reduce overfitting. Quasi-Newton methods, such as L-BFGS (Liu and Nocedal, 1989) can be used for maximizing the function.

Tree-based Reparameterization
Since the proposed model may include loops, it is necessary to introduce an approximation to calculate mariginal probabilities. For this, we use Tree-based Reparameterization (TRP) (Wainwright et al., 2003) for approximate inference. TRP enumerates a set of spanning trees from the graph. Then, inference is performed by applying an exact inference algorithm such as Belief Propagation to each of the spanning trees, and updates of marginal probabilities are continued until they converge.

Dataset
Our dataset is a random selection of 2300 articles from the Japanese version of Wikipedia as of October 2005. All anchor texts appearing under HTML <LI> tags are hand-annotated with NE class label. We use the Extended Named Entity Hierarchy (Sekine et al., 2002) as the NE class labeling guideline, but reduce the number of classes to 13 from the original 200+ by ignoring fine-grained categories and nearby categories in order to avoid data sparseness. We eliminate examples that consist of less than two nodes in the SCR model. There are 16136 anchor texts with 14285 NEs. The number of Sibling, Cousin and Relative edges in the dataset are |E S | = 4925, |E C | = 13134 and |E R | = 746 respectively.

Experimental settings
The aims of experiments are the two-fold. Firstly, we investigate the effect of each cliques. The several graphs are composed with the three sorts of edges. We also compare the graph-based models with a node-wise method -just MaxEnt method not using any edge dependency. Secondly, we compare the proposed method by CRFs with a baseline method by Support Vector Machines (SVMs) (Vapnik, 1998).
The experimental settings of CRFs and SVMs are as follows.
CRFs In order to investigate which type of clique boosts classification performance, we perform experiments on several CRFs models that are constructed from combinations of defined cliques. Re- sulting models of CRFs evaluated on this experiments are SCR, SC, SR, CR, S, C, R and I (independent). Figure 3 shows representative graphs of the eight models. When the graph are disconnected by reducing the edges, the classification is performed on each connected subgraph. We call it an example.  (Sutton, 2006) with TRP. We set the Gaussian Prior variances for weights as σ 2 = 10 in all models. SVMs We introduce two models by SVMs (model I and model P). In model I, each anchor text is classified independently. In model P, we ordered the anchor texts in a linear-chain sequence. Then, we perform a history-based classification along the sequence, in which j − 1-th classification result is used in j-th classification. We use TinySVM with a linear-kernel. One-versus-rest method is used for multi-class classification. To perform training and testing with SVMs, we use TinySVM 2 with a linearkernel, and one-versus-rest is used for multi-class classification. We used the cost of constraint violation C = 1.

Features for CRFs and SVMs
The features used in the classification with CRFs and SVMs are shown in Table 2. Japanese morphological analyzer MeCab 3 is used to obtain morphemes.

Evaluation
We evaluate the models by 5 fold cross-validation. Since the number of examples are different in each model, the datasets are divided taking the examples -namely, connected subgraphs -in SCR model. The size of divided five sub-data are roughly equal. We evaluate per-class and total extraction performance by F1-value. Table 3 shows the classification accuracy of each model. The second column "N" stands for the number of nodes in the gold data. The second last row "ALL" stands for the F1-value of all NE classes.   The last row "ALL (no article)" stands for the F1value of all NE classes which have no gloss texts in Wikipedia.

Results and discussion
Relational vs. Independent Among the models constructed by combination of defined cliques, the best F1-value is achieved by CR model, followed by SC, SCR, C, SR, S, R and I. We performed McNemar paired test on labeling disagreements between CR model of CRFs and I model of CRFs. The difference was significant (p < 0.01). These results show that considering dependencies work positively in obtaining better accuracy than classifying independently. The Cousin cliques provide the highest accuracy improvement among the three defined cliques. The reason may be that the Cousin cliques appear frequently in comparison with the other cliques, and also possess strong dependencies among anchor texts. As for PERSON, better accuracy is achieved in SC and SCR models. In fact, the PERSON-PERSON pairs frequently appear in Sibling cliques (435 out of 4925) and in Cousin cliques (2557 out of 13125) in the dataset. Also, as for PRODUCT and LOCATION, better accuracy is achieved in the models that contain Cousin cliques (C, CR, SC and SCR model). 1072 PRODUCT-PRODUCT pairs and 738 LOCATION-LOCATION pairs appear in Cousin cliques. "All (no article)" row in Table 3 shows the F1-value of nodes which have no gloss texts. The F1-value difference between CR and I model of CRF in "ALL (no article)" row is larger than the difference in "All" row. The fact means that the dependency information helps to extract NEs without gloss texts in Wikipedia. We attempted a different parameter tying in which the SCR potential functions are tied with a particular observation feature. This parameter tying is introduced by Ghamrawi and McCallum (2005). However, we did not get any improved accuracy.  EVENT and UNIT, models of SVMs achieve significantly better F1-values than models of CRFs.

Filtering NE Candidates using Marginal Probability
The precision-recall curve obtained by thresholding the marginal probability of the MAP estimation in the CR models is shown in Figure 4. The curve reaches a peak at 0.57 in recall, and the precision value at that point is 0.97. This precision and recall values mean that 57% of all NEs can be classified with approximately 97% accuracy on a particular thresholding of marginal probability. This results suggest that the extracted NE candidates can be filtered with fewer cost by exploiting the marginal probability.

Training Time
The total training times of all CRFs and SVMs models are shown in  vs. Java, differences of feature extraction modules, and so on. So, the comparing these two is not the important issue in this experiment.

Related Work
Wikipedia has become a popular resource for NLP. Bunescu (2006) for product information extraction from Web documents. TCRFs and HCRFs are similar to our approach described in section 4 in that the model structure is induced by page structure. However, the model structures of these models are different from our model.
There are statistical models that capture dependencies between examples. There are two types of classification approaches: iterative (Lu and Getoor, 2003b;Lu and Getoor, 2003a) or collective (Getoor et al., 2001;Taskar et al., 2002). Lu et al. (2003a;2003b) proposed link-based classification method based on logistic regression. This model iterates local classification until label assignments converge. The results vary from the ordering strategy of local classification. In contrast to iterative classification methods, collective classification methods directly estimate most likely assignments. Getoor et al. proposed Probabilistic Relational Models (PRMs) (2001) which are built upon Bayesian Networks. Since Bayesian Networks are directed graphical models, PRMs cannot model directly the cases where instantiated graph contains cycles. Taskar et al. proposed Relational Markov Networks (RMNs) (2002). RMNs are the special case of Conditional Markov Networks (or Conditional Random Fields) in which graph structure and parameter tying are determined by SQL-like form.
As for the marginal probability to use as a confidence measure shown in Figure 4, Peng et al. (2004) has applied linear-chain CRFs to Chinese word segmentation. It is calculated by constrained forwardbackward algorithm (Culotta and McCallum, 2004), and confident segments are added to the dictionary in order to improve segmentation accuracy.

Conclusion
In this paper, we proposed a method for categorizing NEs in Wikipedia. We defined three types of cliques that are constitute dependent anchor texts in construct CRFs graph structure, and introduced potential functions for them to reflect classification. The experimental results show that the effectiveness of capturing dependencies, and proposed CRFs model can achieve significant improvements compare to baseline methods with SVMs. The results also show that the dependency information from the HTML tree helps to categorize entities without gloss texts in Wikipedia. The marginal probability of MAP assignments can be used as confidence measure of the entity categorization. We can control the precision by filtering the confidence measure as PR curve in Figure 4. The measure can be also used as a confidence estimator in active learning in CRFs (Kim et al., 2006), where examples with the most uncertainty are selected for presentation to human annotators.
In future research, we plan to explore NE categorization with more fine-grained label set. For NLP applications such as QA, NE dictionary with finegrained label sets will be a useful resource. However, generally, classification with statistical methods becomes difficult in case that the label set is large, because of the insufficient positive examples. It is an issue to be resolved in the future.