- : Ms Word, Ms Word Format
- : 70 Pages
- : ₦3,000 | $25 | ₵60 | Ksh 2720
- : 1-5 Chapters
- Click to DOWNLOAD Materials
A TALE OF TWO PARADIGMS: DISAMBIGUATING EXTRACTED ENTITIES WITH APPLICATIONS TO A DIGITAL LIBRARY AND THE WEB
Abstract
With the increasing wealth of information on the Web, information integration is ubiquitous as the same real-world entity may appear in a variety of forms extracted from different sources. This dissertation proposes supervised and unsupervised algorithms that are naturally integrated in a scalable framework to solve the entity resolution problem, which lies at the heart of the information integration process.
This dissertation focuses on two incarnations of the entity resolution problem that arise in the data mining and natural language processing areas. First, name disambiguation occurs when one is seeking a list of publications of an author in a digital library, who has used different name variations and when there are multiple other authors with the same name. We present an efficient integrative framework that disambiguates the extracted author metadata from paper headers in a divideand-conquer fashion: based on the metadata records extracted from paper headers, a blocking method retrieves candidate classes of authors with similar names and a density-based clustering method, DBSCAN, clusters the records by author. The distance metric between papers used for clustering is calculated by an online active selection Support Vector Machines algorithm LASVM. We prove that by recasting transitivity as density connectivity in DBSCAN, transitivity is guaranteed for core points. The method achieves high accuracy on a manually labeled dataset and readily disambiguates about a million author metadata records in CiteSeer, which paves the way for the fielded search by author name feature in CiteSeerX. Second, as a key step towards document understanding in natural language processing, we investigate the problem of cross document coreference (CDC), which aims to decipher the true reference of a named entity across the boundary of documents. This dissertation presents a novel cross document coreference approach that leverages the profiles of entities which are constructed by information extraction tools and reconciled using a within-document coreference module. We propose to match the profiles by using a learned ensemble distance function comprised of a suite of similarity specialists. We develop a kernelized soft relational clustering algorithm that makes use of the learned distance function to partition the entities into fuzzy sets of identities. Evaluation on a large benchmark collection shows that the proposed methods achieve competitive coreference results. We further discuss the details of the implementation of the CDC and web person search system.
This dissertation surveys the literature on author name disambiguation in citations and paper headers, citation matching and cross document coreference. Additionally, we explore the social networks of the disambiguated authors, performing a comprehensive study of the network and community level characteristics and proposing a stochastic model to predict collaborations of individuals.
Table of Contents
List of Figures viii
List of Tables x
List of Algorithms xi
Acknowledgments xii
Chapter 1
Introduction to Entity Resolution 1
1.1 Research Problems and Challenges . . . . . . . . . . . . . . . . . . 3
1.2 Contributions of This Dissertation . . . . . . . . . . . . . . . . . . . 4
1.3 Organization of the Dissertation . . . . . . . . . . . . . . . . . . . . 6
Chapter 2
Literature Review on The Entity Resolution Problem 8
2.1 Cross Document Coreference (CDC) . . . . . . . . . . . . . . . . . 9
2.2 Disambiguation in Digital Libraries . . . . . . . . . . . . . . . . . . 13
2.2.1 Disambiguation in Citations . . . . . . . . . . . . . . . . . . 13
2.2.1.1 Citation Matching . . . . . . . . . . . . . . . . . . 13
2.2.1.2 Author Name Disambiguation in Citations . . . . . 15
2.2.2 Header-Based Author Name Disambiguation . . . . . . . . . 17
2.2.2.1 Manual Header-Based Disambiguation . . . . . . . 18
2.2.2.2 Automatic Header-Based Disambiguation . . . . . 19
2.2.2.2.1 Header-Based Disambiguation in PubMed 19
2.2.2.2.2 Header-Based Disambiguation in CiteSeer 20
Chapter 3
Header-Based Author Name Disambiguation in A Large Scale
Digital Library 22
3.1 Introduction to Header-Based Author Name Disambiguation . . . . 22
3.2 Problem Formulation and Solution Overview . . . . . . . . . . . . . 27
3.3 Distance Function with Online SVM and Active Learning . . . . . . 28
3.4 DBSCAN Clustering . . . . . . . . . . . . . . . . . . . . . . . . . . 31
3.5 Experiments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
3.5.1 Experiments on SVM Based Distance Function . . . . . . . 37
3.5.2 Name Disambiguation Performance . . . . . . . . . . . . . . 41
3.5.3 Fielded Search by Author Name . . . . . . . . . . . . . . . . 43
3.6 Summary on Header-Based Author Name Disambiguation . . . . . 44
Chapter 4
Profile-based Cross Document Coreference 46
4.1 The Cross Document Coreference Problem . . . . . . . . . . . . . . 46
4.2 Document Level and Profile Based CDC . . . . . . . . . . . . . . . 50
4.3 CDC Using Fuzzy Relational Clustering . . . . . . . . . . . . . . . 52
4.3.1 Preliminaries . . . . . . . . . . . . . . . . . . . . . . . . . . 52
4.3.2 Kernelized Fuzzy Clustering . . . . . . . . . . . . . . . . . . 55
4.3.3 Cluster Validation . . . . . . . . . . . . . . . . . . . . . . . 57
4.4 Specialist Ensemble Learning of Relation Strengths between Entities 58
4.5 Remarks on Fuzzy Clustering . . . . . . . . . . . . . . . . . . . . . 60
4.6 Experiments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61
4.6.1 Evaluation Metrics . . . . . . . . . . . . . . . . . . . . . . . 61
4.6.2 Evaluation Dataset . . . . . . . . . . . . . . . . . . . . . . . 62
4.6.3 Information Extraction and Similarities . . . . . . . . . . . . 63
4.6.4 Evaluation Results with Fuzzy Clustering . . . . . . . . . . . 64
4.6.5 Experiments with Density Based Clustering Methods . . . . 67
4.7 Implementation of The Cross Document Coreference (CDC) System 69
4.8 Application to Web Person Search . . . . . . . . . . . . . . . . . . . 71
4.9 Summary on Cross Document Coreference . . . . . . . . . . . . . . 74
Chapter 5
Application: Analyzing the Social Networks of Disambiguated
Authors 76
5.1 Analyzing the Coauthorship Network of Disambiguated Authors in
CiteSeer . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 76
5.2 Related Studies on Large Scale Social Network Analysis . . . . . . . 78
5.3 Data Collection . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80
5.4 Characterizing Network Evolution . . . . . . . . . . . . . . . . . . . 83
5.4.1 More Collaboration in a Smaller World . . . . . . . . . . . . 83
5.4.2 Shrinking Assortativity and Reciprocity . . . . . . . . . . . 86
5.5 Collaboration at the Community Level . . . . . . . . . . . . . . . . 87
5.5.1 Component Structure Evolution . . . . . . . . . . . . . . . . 88
5.5.2 Collaboration in Topical Communities . . . . . . . . . . . . 90
5.6 Scientific Collaboration Between Individuals . . . . . . . . . . . . . 92
5.6.1 A Stochastic Poisson Model for Collaboration . . . . . . . . 93
5.6.2 The Optimal Tree for Estimating the Rate Function . . . . . 95
5.6.3 Remarks on the Optimization Tree Method . . . . . . . . . 97
5.6.4 Empirical Studies on the Collaboration Model . . . . . . . . 98
5.7 Summary and Discussions . . . . . . . . . . . . . . . . . . . . . . . 103
Chapter 6
Conclusions 104
6.1 Future Research Directions . . . . . . . . . . . . . . . . . . . . . . . 105
Bibliography 108
List of Figures
2.1 Relationships among evaluation tasks in MUC-6, adopted from [42] . 9
2.2 Relationship between within document coreference and cross document coreference, adopted from [7] . . . . . . . . . . . . . . . . . . . . . . 10
2.3 Disambiguation problems in a digital library and their relationships: citation matching problem (purple edges); author name disambiguation in citations (blue edges); header-based author name disambiguation (orange edges). Dotted bordered entities are external to the digital
| library. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.1 Examples of a variety of paper headers: single column (upper left) and double column (lower left) conference papers; journal articles with individual (upper right) and shared (lower right) contact |
14 |
| information. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . | 24 |
| 3.2 Logical illustration of header-based author name disambiguation. . | 24 |
| 3.3 Disambiguation system overview. . . . . . . . . . . . . . . . . . . .
3.4 Active Learning with SVM. The most informative sample among the unseen training samples is the one (in pink circle) closest to the |
28 |
| hyperplane (solid black line). . . . . . . . . . . . . . . . . . . . . . . | 29 |
| 3.5 The transitivity problem. . . . . . . . . . . . . . . . . . . . . . . . . | 32 |
| 3.6 Proof of Theorem 1. . . . . . . . . . . . . . . . . . . . . . . . . . .
3.7 Cross-validation on three-fold training datasets (from left to right: train[4,5] test[9] ; train[4,9] test[5] ; train[5,9] test[4] ). The optimal iteration number for early stopping is shown with a yellow horizontal line. The LIBSVM test error is indicated by a pink triangle and |
35 |
| the number of iterations refers to LASVM only. . . . . . . . . . . . | 38 |
| 3.8 Test errors in different iterations for test datasets 3, 6 and 10. . . . | 39 |
| 3.9 Name Disambiguation Prototype. . . . . . . . . . . . . . . . . . . . | 44 |
| 4.1 Architecture of the profile-based CDC approach. . . . . . . . . . . . | 52 |
| 4.2 Purity, inverse purity and F with different fuzzifiers. . . . . . . . . . | 66 |
| 4.3 CDC performance with different θ. . . . . . . . . . . . . . . . . . . | 66 |
4.4 Coreference performance for names with different number of real
world entities. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68
4.5 Coreference performance with different
| 4.6 | Architecture of the cross document coreference system (detailed | |
| implementation). . . . . . . . . . . . . . . . . . . . . . . . . . . . . | 70 | |
| 4.7 | Architecture of the cross document coreference system (detailed | |
| implementation). . . . . . . . . . . . . . . . . . . . . . . . . . . . . | 72 | |
| 4.8 | Web Person Search (WePS) system. . . . . . . . . . . . . . . . . . . | 74 |
| 5.1 | Left: number of authors and papers from 1980 to 2005. Right: the | |
| increasing trend of collaboration. . . . . . . . . . . . . . . . . . . . | 80 | |
| 5.2 | The average distance of the network gradually decreases over time, indicating that the collaboration “world” in fact gets smaller over | |
| time. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . | 83 | |
| 5.3 | The degree distribution of the CiteSeer co-authorship network in | |
| 2005. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . | 85 | |
| 5.4 | Assortativity and reciprocity are both shrinking over time. Note | |
| that assortativity dropped significantly. . . . . . . . . . . . . . . . . | 87 | |
| 5.5 | The largest component of G(2005), enlarged on the left, visually forms the core of the network shown in the bottom-right inset. Edges showing collaborations in different topics are rendered in different colors. Visualization is performed by the Large Graph | |
| Layout (LGL) package. . . . . . . . . . . . . . . . . . . . . . . . . . | 88 | |
| 5.6 | The evolution of component structure, shown as the fraction of vertices in components of different sizes. The middle region gradually lost ground as the giant components came into dominance. | |
| The percentages became constant after reaching a steady state. . . | 90 |
5.7 The database community (right) is more cohesive than the applications community (left), and its largest component forms a significantly
larger core in the network. . . . . . . . . . . . . . . . . . . . . . . 91
5.8 An example rule for distribution prediction. . . . . . . . . . . . . . 101
List of Tables
| 2.1 | Digital libraries and header based author name disambiguation. . . | 19 |
| 3.1 | Sampled author datasets. . . . . . . . . . . . . . . . . . . . . . . . . | 37 |
| 3.2 | SVM models testing results: LASVM vs LIBSVM. . . . . . . . . . . | 39 |
| 3.3 | Macro and micro error rates comparison of SVM models (LIBSVM and LASVM) vs. Random Forest models (lower is better). A cell | |
| is bolded to indicate the best result in that data set. . . . . . . . . | 40 | |
| 3.4 | Disambiguation accuracy in three sets of metrics for 10 author | |
| datasets. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . | 42 | |
| 3.5 | Most prolific authors in CiteSeer. . . . . . . . . . . . . . . . . . . . | 43 |
| 4.1 | Extraction results for named entity John Chambers. . . . . . . . . . | 47 |
| 4.2 | Comparison of cross document coreference performance (I. Purity | |
| denotes inverse purity). . . . . . . . . . . . . . . . . . . . . . . . . . | 64 | |
| 4.3 | Cross document coreference performance on subsets (I. Purity | |
| denotes inverse purity). . . . . . . . . . . . . . . . . . . . . . . . . . | 65 | |
| 5.1 | Comparison of the statistical properties of several coauthorship | |
| networks. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . | 81 | |
| 5.2 | Overview of the six topical datasets. . . . . . . . . . . . . . . . . . | 82 |
| 5.3 | Assortativity coefficient in Computer Science and other research | |
| domains. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . | 87 | |
| 5.4 | Summary statistics of the six topical communities. Cells with | |
| particularly high/low values are highlighted in bold font. . . . . . . | 91 | |
| 5.5 | Collaboration patterns of the six topical communities. Cells with | |
| particularly high/low values are highlighted in bold font. . . . . . . | 92 | |
| 5.6 | Features used for collaboration prediction. . . . . . . . . . . . . . . | 99 |
5.7 Comparison of prediction performance of Past Collaboration (baseline), Spot and SVR using 10-fold cross validation. . . . . . . . . . . . . 102
List of Algorithms
1 DBSCAN for disambiguation (after [38] ). . . . . . . . . . . . . . . . 33 2 The expandCluster function (after [38] ). . . . . . . . . . . . . . . . 34
- KARC Alternating Optimization . . . . . . . . . . . . . . . . . . . 57
- Specialist Exponentiated Gradient algorithm (after [39] ). . . . . . . 59
Chapter 1
Introduction to Entity Resolution
“On the road from the City of Skepticism,
I had to pass through the Valley of Ambiguity.”
Adam Smith
The explosive growth of web data offers users both the opportunity and the challenge to discover and integrate information from disparate sources. An automated process, consisting of focused crawling from the vast Web, information extraction from free text and entity resolution based on extracted data, can greatly facilitate information processing and integration. Such a process manifests significant machine intelligence in knowledge acquisition, where raw data are transformed to formatted information and eventually to usable knowledge.
This intelligent information integration process manifests itself in different forms spanning the spectrum from structured to semi-structured to free text and appearing in various research areas.
- In Artificial Intelligence (AI), the research problem of finding structural and semantic mappings between ontologies, known as ontology matching, emerges from building the de-centralized semantic web [32] . The solution to this problem is the cornerstone of ontology interoperability. A related research problem is calledtuple matching, where multiple tuples from multiple sources are determined if they refer to the same real-world entity [55] . In the database domain,schema matching and record linkage are similar problems [112, 36, 111] , which aim to consolidate heterogenous schema and duplicate records
respectively.
- Many web search engine users try to find and compare the same product offered by different online vendors. The product pages in these shopping sites usually contain similar information such as product descriptions and specifications, prices, etc, though they vary in page layouts, extent of details, presence/absence of customer reviews and so on. This gives rise to the development of comparison shopping engines [98] in the e-commerce context, whose key technology is the ability to disambiguate semi-structured text.
- In digital libraries, users are usually interested in collecting publication information of a particular author. Such information can be automatically extracted from the publications in its semi-structured representation [44] , similar to the way that product information can be extracted from product pages. However, person names are much more ambiguous than product names and the lack of unique identifiers lends author name disambiguation to significant research challenges.
- In a similar vain, person names account for a significant amount of search engine queries [58] . TheWeb Person Search (WePS) task [4] seeks to cluster web pages that correspond to the same individuals. Compared to the product and author search, personal web pages are in free text form and vary to a greater extent in terms of their content (e.g. professional vs. personal pages), styles of presentation and so on.
- In Natural Language Processing (NLP), the task of named entity coreference, which groups all references to the same entity into a coreference chain, is central to document understanding. To integrate and understand multiple documents, the task of cross document coreference (CDC) needs to infer the real identities of names scattered in separate documents. The CDC problem is deemed even more challenging, because it makes no simplifying assumption that each name has one identity in a document as in the WePS task (this will be elaborated later) and the names may refer to a broad range of types of entities such as people, organization, geographical locations.
1.1 Research Problems and Challenges
Due to its various origins as aforementioned, the disambiguation problem has been studied under various banners in several areas with particular emphases. As alluded to in the title, this work focuses on the disambiguation of semi-structured or free text with related but different paradigms, namely the header-based author name disambiguation problem and the cross document coreference problem.
Name references to real world entities is a difficult problem to resolve. Even if we work with ‘clean’ data where names and properties are free of typographical or other processing errors, we are still faced with two types of ambiguity. First, the same name appearance may reference multiple real world entities. By the same token, an entity may be referred to with different name variations. In [16] , these two problems are referred as thedisambiguation problem and the identification problem respectively. In our work, we aim to resolve these two problems simultaneously.
Hence we simply refer to the research problem as the disambiguation problem.
Real world data for disambiguation have two distinct characteristics. First, they are typically very noisy (particularly web data). For instance, legitimate variations of person names or typographical errors are challenges to identify disambiguation candidates. Since this work deals specifically with automatically extracted named entities, the system should be capable of handling these variations and robust to the inherent noise in data. Second, this work deals with large scale real world data. Specifically, in the header-based author name disambiguation problem, we deal with a million header records of authors in CiteSeer[1] . The underlying machine learning algorithms and the framework for disambiguation need to be very efficient to handle millions of data records.
1.2 Contributions of This Dissertation
With the exponential growth of online information, integrating information gathered from different sources has become increasingly more important for users to be able to access and consume it. Entity resolution is central to the solution of this information integration process. We highlight the following contributions of the dissertation that aim to address the two related yet different forms of the entity resolution problem and its challenges as mentioned earlier:
- In either the header-based author name disambiguation or the cross documentcoreference problem, we are faced with real world data that are large and noisy. This renders many elaborate and carefully tuned traditional classification methods inapplicable to such data due to the scalability and robustness issues. Purely unsupervised clustering methods are also unsuitable for not leveraging the small amount of labeled data samples available. We propose a hybrid framework to solve the entity resolution problem which integrates unsupervised and supervised methods and enables the strength of both types of methods, namely, scalability and robustness of the former and accuracy of the latter.
- Compared to traditional clustering methods which mainly deal with objectdata, our work on disambiguation handles purely relational data where only pairwise relationships between data points are defined. Special attention in this work has been paid to adapt and advance the research on relational clustering methods that are much called for in data mining. We propose to use a density based clustering method DBSCAN to create author clusters, for its simplicity in parameter setting, insensitivity to cluster shapes as well as efficiency and accuracy for relational data clustering. We also formally prove the transitivity property of DBSCAN for collective entity resolution. To address the inherent uncertainty nature of the cross document coreference problem, we propose a novel relational clustering algorithm KARC, which permits probabilistic membership assignment and takes advantage of the power of kernel for tackling relational clusters of complicated shapes.
- For the header-based author name disambiguation problem, we adopt thestate-of-the-art online Support Vector Machines algorithm LASVM as a learned distance function. To scale up learning and prediction, we employ techniques such as active learning and early stopping to derive sparse yet more accurate models. For the CDC problem, since usually only a partial list of attributes are available for each extracted entity, a linear and online specialist learning framework is adapted to properly predict the relation strength of entity pairs.
- The entity resolution work in this dissertation is a cornerstone for several realworld applications. The header-based author name disambiguation method is the backbone for the author search feature for digital libraries. We conduct a comprehensive study of the disambiguated author data which is among the largest scale social network analysis. Also, the cross document coreference techniques enable users to leverage state-of-the-art information extraction tools for integrated information analysis.
Finally, we point out that this work does not attempt to exhaustively resolve the entity resolution problem in general, which as we mentioned is a concept encompassing various research problems in different fields of computer science. We, however, focus on the solution of the problem for the extracted entities from the semi-structured text in a large publication repository and from the free text in web data. We believe that these are important steps for improving data quality and enabling and enhancing user access to vast amount of heterogenous data.
1.3 Organization of the Dissertation
The dissertation is organized as follows: in Chapter 2, we present the related work on the disambiguation problem, in particular the author name disambiguation in citations and headers, citation matching and cross document coreference problems that are closely related to this research. Chapter 3 presents the solution to the header-based author name disambiguation problem for the CiteSeer digital library.
A scalable framework is proposed to integrate a density based relational clustering algorithm DBSCAN and a supervised SVM distance function. In Chapter 4, we explore a related yet even more challenging research problem, i.e. coreferencing person named entities that are automatically extracted from web pages across the boundaries of documents. We investigate a different paradigm which accounts for the uncertainty in the disambiguation problem with soft clustering. We also discuss the details of implementing the cross document coreference system. We explore the coauthorship network which is the outcome of the author name disambiguation studies and further propose a stochastic model to predict the network evolution in Chapter 5. Concluding remarks and future research directions are outlined in Chapter 6.
A TALE OF TWO PARADIGMS: DISAMBIGUATING EXTRACTED ENTITIES WITH APPLICATIONS TO A DIGITAL LIBRARY AND THE WEB
