---
abstract: 'In this article, I present the questions that I seek to answer in my PhD research. I posit to analyze natural language text with the help of semantic annotations and mine important events for navigating large text corpora. Semantic annotations such as named entities, geographic locations, and temporal expressions can help us mine events from the given corpora. These events thus provide us with useful means to discover the locked knowledge in them. I pose three problems that can help unlock this knowledge vault in semantically annotated text corpora: *i.* identifying important events; *ii.* semantic search; and *iii.* event analytics.'
author:
- |
    Dhruv Gupta\
    \
    \
subtitle: 'Detecting Events in Semantically Annotated Corpora for Search & Analytics'
title: Event Search and Analytics
---

Introduction
============

Information retrieval systems have largely relied on word statistics in text corpora to satisfy information needs of users by retrieving documents with high relevance for a given keyword query. In my PhD research I hypothesize that information needs of users can be satisfied to a greater extent by using *events* as a means of navigating text corpora. Events in our context would be an act performed by certain actor(s) at a specific location during a specific time interval. An example would be : *Usain Bolt won the gold medal at the 2008 summer Olympics in Bejing*. With the availability of annotators that can provide us with accurate semantic annotations in form of named entities, geographic locations, and temporal expressions; we can leverage the growing number of knowledge resources such as Wikipedia [@wiki] and ontologies such as Freebase [@freebase] to understand natural language text and mine important events. Formally the central hypothesis can be stated as follows:

As a toy example consider the following text snippet [^1] with demonstrative semantic annotations in Figure \[fig:text\] :

In the text snippet (Figure \[fig:text\]), we obtain the named entity whose mention has been identified and disambiguated to point to an external knowledge source. Also identified is a geographical location - , which is disambiguated and resolved to its geographical coordinates. Likewise the temporal expression has also been resolved to time range. Having these semantic annotations we can now devise algorithms that can deduce that the event is that of Usain Bolt winning Olympic competition in Beijing, China.

The goal of the proposed research is to leverage the semantic annotations for mining important events and use them to navigate text corpora. The research will find application in many domains of research such as *digital humanities*, in which social scientists are interested in computational history in large digital-born text collections. Anthropologists are interested in cultural and linguistic shifts that occur in such collections. Collectively we can allow *computational culturomics* [@culturomics] on corpora to study cultural trends. Events can also be used to link information in multiple and diverse text collections. In short, important events provide a way to create a gist from semantically annotated corpora, which otherwise is not possible through manual human effort.

**Outline**. The article consists of:

-   a literature survey (Section \[sec:background\]);

-   an overview of the research problems (Section \[sec:problem\]);

-   available corpora, test sources and evaluation measures for research (Section \[sec:evaluation\]);

-   discussion of few open technical problems (Section \[sec:discussion\]).

Related Work
============

 \[sec:background\]

In this section I discuss the progress already made in the area of analyzing different semantic annotations in isolation as well as in conjunction for some of the problems proposed.

**Temporal Information Retrieval and Extraction**. Researchers have considered only temporal annotations in text corpora to improve retrieval effectiveness by analyzing the time sensitivity of keyword queries and incorporating the time dimension in retrieval models. Some methods of analysis of time-sensitive queries rely on publication dates of documents [@diaz_profile; @nattiya_2010], while others also look at the temporal expressions in document contents [@dhruv_2014]. Several works also take into account the time dimension for re-ranking documents [@klaus_2010] and diversifying them along time [@klaus_2013; @nattiya_2014]. One of the seminal works in extracting temporal events was by Ling and Weld [@ling_tie]. They outline a probabilistic model to solve the problem of extracting relations from text with temporal constraints.

**Important Events in Annotated Corpora**. One of the most important seminal works in identifying existing and emerging events were the various tasks in *Topic Detection and Tracking* (TDT) [@tdt_book]. The TDT program aimed to “search, organize and structure” broadcast news media from multiple sources. The five tasks laid within the ambit of TDT where topic tracking, link detection, topic detection, first story detection, and story segmentation. The task of topic tracking required to build a system to detect *on topic stories* from an evaluation corpus after being trained on a set *on topic* stories. The link detection task involved answering a boolean query to whether two given *stories* are related by a common topic. The topic detection task comprised of declaring new *topics* from incoming *stories* which had not been presented to the system. First story detection was another boolean decision task of determining whether the given *story* is a seed story (first-story) to create a new *topic* cluster. Story segmentation task required segmentation of an incoming stream of text into *stories*.

Focusing specifically on extracting and summarizing events in the future, Jatowt and Yeung [@adam_cikm11] present a model-based clustering algorithm. The clustering considers both textual and temporal similarities. For computing temporal similarity, the authors model time as a probability distribution by utilizing different family of distributions based on whether its is singular time point, starting date or and ending date. The similarity is then computed using KL-divergence.

Radinsky et al. [@kira_jair] present an algorithm *Pundit*, which based on the past events in text is able to predict a future event given a query to the system. The events are represented as multidimensional attributes such as time, geographic location and participating entities. The algorithm derives these events from external text collection and builds an *abstraction tree*, which is the result from hierarchical agglomerative clustering. In order to predict the future *Pundit* is trained to select the most similar cluster from the *abstraction tree* and produce an event representation.

The work by Yeung and Jatowt [@yeung_cikm11] tackles the problem of analysis of historical events in multiple large document collections. They utilize *latent Dirichlet allocation* to identify *topic* distributions along time. Thereafter they perform analytics to answer questions such as *i.* significant years and topics, *ii.* triggers that caused remembrance of the past and *iii.* historical similarity of countries.

Most recently, Abujabal and Berberich [@mppf] present a system which identifies important events in text collections by counting frequent itemsets of sentences containing named entities and temporal expressions. For evaluation they resort to *Wikipedia’s* event directory as a ground truth.

**Semantic Search**. Summarizing text collections in a timeline visualization is a natural choice. Swan and Allan [@swan_timeline] present an approach for producing a timeline that depicts most important topics and events closely modeled on the *Topic Detection and Tracking* task. The algorithms analyzes features based on named entities and noun phrases. The analysis involves construction of $2 \times 2$ contingency table on presence or absence of features, and subsequent measurement of $\chi^2$ statistic for measuring significance of co-occurrence of a pair of features.

The seminal work by Baeza-Yates [@yates_future] proposed a *future retrieval* (FR) system. The FR system considers both text and temporal expressions to identify future events that might be relevant to an input query. Baeza-Yates outlined the components of a FR system to be composed of an *information extraction* (IE) module, *information retrieval* (IR) module, and a *text mining* (TM) module. The IE module would act as a temporal annotator; identify temporal expressions and normalize them. The IR system is designed to incorporate the time dimension in an index; thus retrieving documents with text and time similarity. The TM module would identify the most relevant topics given a time period. He presented a retrieval model, in which each document consists of a multiple temporal events. A temporal event consists of a time segment and its associated likelihood of occurring. The score of the document is thus obtained by its textual similarity and the maximum likelihood of all the temporal events in that document.

Bast and Buchhold [@bast_index] outline a joint index structure over ontologies and text. Which allows for fast semantic search and provide context sensitive auto-complete suggestions.

Events as a means of search document collections has also been explored by Strötgen and Gertz [@jannik_event]. Events were modeled by the geographic location and time of their occurrence. For temporal queries expressed in simple natural language they outline an extended Backus-Naur form (EBNF) language that incorporates time intervals with standard boolean operations. Geographical queries are also modeled as EBNF language, however the input for them is a minimum bounding rectangle (MBR). Using this multidimensional querying model the user is able to visualize search results in form of events; which are additionally represented on a map.

Giving special attention to geographical information retrieval, Samet et al. [@samet_news] present a system *NewsStand*, that is able to resolve and pinpoint a news article based on the geographic information present in its content. They discuss various methods for toponymn resolution, which is in essence disambiguating the geographic location based on its surface form in the news content. The system involves a streaming clustering algorithm that can keep track of emerging news in new locations and present them in a map-based interface.

[l|p[4cm]{}p[4cm]{}p[4cm]{}]{}

\

**Event** & $c_1$ & $c_2$ & $c_3$\

**Words** & micheal, phelps, bejing, china, tibet & london, usain, bolt, england, badminton & rio, brazil,copacabana, deodoro, maracanã\
**Time** &$[08-08-2008, 24-08-2008]$ & $[27-07-2012, 12-08-2012]$ & $[05-08-2016, 21-08-2016]$\
**Location** & $\langle Beijing, China \rangle$ & $\langle London, England \rangle$ & $\langle Rio de Janeiro, Brazil \rangle$\
**Entities** & $\langle China \rangle$, $\langle Micheal\_Phelps \rangle$ & $\langle England \rangle$, $\langle Badminton \rangle$ & $\langle Brazil \rangle$, $\langle Copacabana \rangle$\

**Event Analytics**. By disambiguating and linking named entities to ontologies, Hoffart et al. [@aesthetics; @stics] provide a framework for semantic search and performing analytics on them. They provide features for giving auto-complete suggestions in the form of similar entities for the input named-entity. In [@aesthetics] they provide analytics that leverage accurate entity counts and provide entity co-occurrence statistics which is helpful in analyzing semantically similar named-entities.

Research Objectives
===================

 \[sec:problem\] Given the text corpora with semantic annotations, I describe three important research problems in this section: *i.* identifying important events; *ii.* using identified events for improving retrieval effectiveness; and *iii.* using identified events for analytics.

Notation
--------

Let us consider multiple corpora for the purpose of analysis. This allows us to capture frequently occurring events as well as link similar events across corpus. Given corpora $$D = \bigcup_{k=1}^{N} D_k,$$ where each document $d \in D$ consists of word sequence $x$ at appropriate granularity (e.g. paragraph or sentence): $$d = \bigcup_{i=1}^{n} x_i.$$ Further each $x \in d$ contains semantic annotations in form of *i.* named entities ($e$), *ii.* geographical location ($g$), and *iii.* temporal expressions ($t$). Additionally $x$ also consists of the a bag of words $\mathcal{W}$ drawn from a vocabulary $\mathcal{V}$. Formally represented as: $$x = \langle \mathcal{E}, g, t, \mathcal{W} \rangle$$

Problem Definition
------------------

The objective is to design a family of algorithms: $$\textsc{Event*}(X,Q,\alpha)$$

where $X = \bigcup x$, $Q$ represents an input query and $\alpha \in \mathds{R}^m$, where $\alpha$ is set of parameters.

The input query $Q$ can be a combination of following input components: *i.* keyword query $q$, *ii.* time $q_{time}$, *iii.* geographical location $q_{geo}$, and *iv.* named entity $q_{entity}$.

Given the input, we need to design the algorithms $\textsc{Event*}$ according to the different problems. We discuss the design objectives for the three different purposes in this section.

**Identifying Important Events**. *Events* are the proposed building blocks for further text analysis. An *event* in our context is defined to be an activity or an act involving named entities that happens in a specific geographical location anchored to a specific time interval. Mathematically, given a multidimensional query : $$Q = \langle q, q_{time}, q_{geo}, g_{entity} \rangle,$$ and a subset of highly relevant documents $R \subseteq D$, the algorithm for this purpose $\textsc{EventDetect}$ should produce a set of ordered events : $$\mathcal{C} = \{ c_1, c_2, \ldots, c_k \},$$

where, $c = \langle \mathcal{E}, g, t, \mathcal{W} \rangle$. The event $c$ is hence described by the participating named entities $\mathcal{E}$, its location $g$, its time of occurrence $t$, and frequently occurring contextual terms around these semantic annotations $\mathcal{W}$. This requires proposing a probability mass function, $P(\mathcal{C}, R)$, using which we can impose a total order on $\mathcal{C}$.

As an example consider the keyword-only query `summer olympics` to the processed corpora of news articles. The designed algorithm shall then identify the important events as in Figure \[fig:event\].

**Diversifying and Summarizing Search Results** are retrieval tasks that try to address the information need underlying an ambiguous query at different levels of textual granularity. Each task tries to maximize the coverage of different information needs underlying the given ambiguous query. As information intents, we propose to use the mined set of *events*. Accomplishing these tasks would allow for automatic creation of *event timelines* or *entity biographies*. We briefly discuss an intuition of achieving the same.

When diversifying search results we would like to present users with *documents* such that the user finds *at least* one document that satisfies her information intent. For this we need to devise an algorithm $\textsc{EventDiverse}$ which considers as an input $Q$ and $R \subseteq D$. As an output it returns a set of documents $S \subset R$ which cover all events in $\mathcal{C}$.

Summarizing search results would require us to construct an algorithm $\textsc{EventSummary}$ to piece together, *sentences* $\hat{S} = \bigcup x$, such that the text summary covers all events in $\mathcal{C}$.

**Semantic Search and Analytics**. The mined set of *events* can further be utilized for search and analytics. For this purpose we can utilize inherent hierarchy in the semantic annotations. For example a given year can be broken down to different months and subsequently days in those months. Similarly, we can utilize the *type hierarchies* in named entities. Such as and are subtypes of . This can jointly be modeled by using the concept of a *data cube* [@han_dm] as shown in Figure \[fig:data\_cube\].

Formally, given a query $Q$, the objective would to first model the mined set of events as a *data cube* and subsequently provide *data cube operations* [@han_dm]:

-   roll ($\bigcirc$),

-   slice ($\ominus$),

-   dice ($\oplus$),

-   drill up ($\bigtriangleup$),

-   drill down ($\bigtriangledown$).

![Example data cube based on set of events $\mathcal{C}$[]{data-label="fig:data_cube"}](cube.pdf)

![Example data cube operations for the query `all races won during 2008 by usain bolt in china` []{data-label="fig:cube_opr"}](cubeopr.pdf)

As a concrete example consider the query `all races won during 2008 by usain bolt in china`. To produce an appropriate result the sequence of operations would be: first a slice on the entity ; second dice on ; and finally drill up to year (see Figure \[fig:cube\_opr\]).

Data
====

**Corpora**. There are several readily available massive data sets. They are available from news corporation such as the *New York Times* [@nyt], *English Gigaword* [@gigaword]. These corpora have the benefit of being available with reliable publication dates and grammatically well-formed text. On larger scale are Web collections such as *ClueWeb’09* [@clueweb09]/’12 [@clueweb12], which are not always accompanied by reliable creation dates and many are ill-formed documents.

**Semantic Annotations**. The text corpora next need to be annotated for text mining. I explain how to obtain the different semantic annotations in the following paragraphs.

**Named Entities**. For disambiguating and linking named entities in text to an external knowledge source such as *Wikipedia* [@wiki] or an ontology such as YAGO [@yago] or Freebase [@freebase]; I use the AIDA system [@aida]. The AIDA system does named entity disambiguation and linking by leveraging contexts extracted from ontologies such as YAGO. For Web collections such ClueWeb’09/’12 the entity disambiguation and linking has been released as *facc1 : Freebase annotation of ClueWeb Corpora* [@facc].

**Geographical Locations** can be obtained by utilizing *geographic* named entities such as those known to be cities, countries, or continents. Geographical relations stored in an ontology can be used to resolve these locations to its geographical coordinates. Having obtained a set of coordinates, we can subsequently construct a geographical representation such as a *minimum bounding rectangle* over the coordinates.

**Temporal Expressions**, both implicit and explicit, can be extracted and normalized from text by using *temporal taggers* such as HeidelTime [@heideltime] or SUTime [@sutime].

Evaluation
==========

 \[sec:evaluation\]

To test our approach we need to construct query sets that contain an event description associated with the query; along with participating named entities, geographical locations where the event took place and relevant time interval associated with it. I describe a tentative approach to achieve this here.

**Test Data**. To evaluate the correctness of the various algorithms, I plan to use reliable encyclopedic resources on the Web such as *Wikipedia* [@wiki] or other curated knowledge sources. For an objective evaluation, I propose the following different sources depending on the algorithm under evaluation.

-   Identify important events

    -   Events in a particular year/decade etc. pages available on *Wikipedia* [@wiki_year].

    -   Testing of past events can be done by extracting important topics from *Category* pages on various historical topics on *Wikipedia* [@wiki_past].

    -   Events in the future can be evaluated by using important infrastructure projects, engineering projects etc. These can be extracted from *Wikipedia* and other sources on the Internet.

    -   Current events extracted from *Wikipedia* [@wiki_current].

    -   Alternatively, we can manually construct a list of prominent events and extract relevant information such as named entities, geographical location, and time from ontologies such as: YAGO [@yago], Freebase [@freebase], etc.

-   Diversifying and summarizing search events

    -   Biographies of eminent personalities, for example United States presidents [@wiki_potus].

    -   Historical timelines of various countries, for example for India [@wiki_timeline].

**Structure**. Each event in our test bed is then composed of a fact with an accompanying query. Formally, a *fact* in our testbed is a 4-tuple extracted from one of the aforementioned sources: $$\langle q,\mathcal{E}, g, t, \mathcal{W} \rangle$$

where $q$ consists of keyword query describing the event, $\mathcal{E}$ is a bag of participating entities, $g$ is the geographic location, $t$ is the time of its occurrence, and $\mathcal{W}$ are important terms describing the event.

**Metrics**. Based on the structure of the testbed of events, metrics such as *precision*, *recall* and *F$_1$* can be utilized to measure the effectiveness of the algorithms for detecting important events in semantically annotated corpora. How effectively the algorithm diversifies documents along multiple dimensions can be evaluated by metrics such as $\alpha$-nDCG [@diverse]. Quality of summaries can be measured by an automatic evaluation metric called *Rouge* [@rouge].

Discussion
==========

 \[sec:discussion\]

I briefly present some open technical challenges that I will address along with the research objectives in my PhD dissertation.

**Mathematical Models**. One key aspect that occurs in the design of the algorithms is that of computational models for named entities, geographical locations and temporal expressions. What would be the most descriptive mathematical models for each of these semantic annotations?

**Similarity Functions**. Given a pair of named entities, geographical locations or temporal expressions; how can we efficiently compute the similarity between the same type of annotations?

**Efficiency & Scalability**. Identifying data structures for indexing corpora along with their semantic annotations, such that their asymptotic run times scale linearly with the size of the corpora.

**Evaluation**. Since evaluation of the solutions outlined are very subjective in nature; what are other reliable sources of objective ground truth ? What other metrics can be employed to test the effectiveness of our methods ?

Conclusion
==========

 \[sec:conclusion\]

In this article I laid out an outline of the research work that I envisage to carry out for my PhD dissertation. The research would in its culmination provide us methods to computationally extract world history as sequence of temporally ordered events and portray future events to take place from semantically annotated corpora. The research would also provide ways to perform semantic search and large scale event analytics on these annotated corpora. I further described already available resources that can be utilized for carrying out the research; test cases that can be built from encyclopedic resources on the Internet; and the metrics that can be utilized for evaluation.

[10]{} Clueweb’09. <http://www.lemurproject.org/clueweb09.php/>.

Clueweb’12. <http://www.lemurproject.org/clueweb12.php/>.

English gigaword. <https://catalog.ldc.upenn.edu/LDC2003T05>.

New york times anotated corpus. <https://catalog.ldc.upenn.edu/LDC2008T19>.

Abujabal A. and Berberich K. Important events in the past, present, and future. WWW’15 Companion Volume.

Agrawal R. et al. Diversifying search results. WSDM’09.

Allan J., editor. . Kluwer Academic Publishers, Norwell, MA, USA, 2002.

Baeza-Yates R. Searching the future. SIGIR’05 Workshop MF/IR.

Bast H. and Buchhold B. An index for efficient semantic full-text search. CIKM’13.

Berberich K. et al. A language modeling approach for temporal information needs. ECIR’10.

Berberich K. and Bedathur S. Temporal diversification of search results. TAIA’13.

Bollacker K. et al. Freebase: A collaboratively created graph database for structuring human knowledge. SIGMOD’08.

Chang A. X. and Manning C. D. : A library for recognizing and normalizing time expressions. LREC’12.

Ringgaard M. et al. Facc1: Freebase annotation of clueweb corpora, version 1 (release date 2013-06-26, format version 1, correction level 0), June 2013. <http://lemurproject.org/clueweb12/>.

Gupta D. and Berberich K. Temporal query classification at different granularities. SPIRE’15.

Han J. et al. . Morgan Kaufmann Publishers Inc., San Francisco, CA, USA, 3rd edition, 2011.

Hoffart J. et al. analytics with strings, things, and cats. CIKM’14.

Hoffart J. et al. searching with strings, things, and cats. SIGIR’14.

Hoffart J. et al. Robust disambiguation of named entities in text. EMNLP’11.

Jatowt A. and Yeung C. A. Extracting collective expectations about the future from large text collections. CIKM’11.

Jones R. and Diaz F. Temporal profiles of queries. , 25(3), July 2007.

Kanhabua N. and N[ø]{}rv[å]{}g K. Determining time of queries for re-ranking search results. ECDL’10.

Ling X. and Weld D. S. Temporal information extraction. AAAI’10.

Michel J. B. et al. Quantitative analysis of culture using millions of digitized books. Science’10.

Nguyen T. N. and Kanhabua N. Leveraging dynamic query subtopics for time-aware search result diversification. ECIR’14.

Radinsky K. et al. Learning to predict from textual data. , 45:641–684, 2012.

Samet H. et al. Reading news with maps by exploiting spatial synonyms. , 57(10):64–77, 2014.

Str[ö]{}tgen J. and Gertz M. Event-centric search and exploration in document collections. JCDL’12.

Strötgen J. and Gertz M. Multilingual and cross-domain temporal tagging. , 47(2):269–298, 2013.

Suchanek F. M. et al. Yago: A large ontology from wikipedia and wordnet. , 6(3):203–217, September 2008.

Swan R. C. and Allan J. Automatic generation of overview timelines. SIGIR’00.

Wikipedia. List of presidents of the united states — [W]{}ikipedia[,]{} the free encyclopedia, 2015. <https://en.wikipedia.org/wiki/List_of_Presidents_of_the_United_States>.

Wikipedia. List of years — [W]{}ikipedia[,]{} the free encyclopedia, 2015. <https://en.wikipedia.org/wiki/List_of_years>.

Wikipedia. List of years in india — [W]{}ikipedia[,]{} the free encyclopedia, 2015. <https://en.wikipedia.org/wiki/List_of_years_in_India>.

Wikipedia. Portal:contents/history and events — [W]{}ikipedia[,]{} the free encyclopedia, 2015. <https://en.wikipedia.org/wiki/Portal:Contents/History_and_events>.

Wikipedia. Portal:current\_events — [W]{}ikipedia[,]{} the free encyclopedia, 2015. <https://en.wikipedia.org/wiki/Portal:Contents/History_and_events>.

Wikipedia. ikipedia[,]{} the free encyclopedia, 2015. <http://en.wikipedia.org/>.

Yeung C. A. and Jatowt A. Studying how the past is remembered: towards computational history through large scale text mining. CIKM’11.

Lin C. Y. Rouge: a package for automatic evaluation of summaries. ACL-04 workshop.

[^1]: <http://www.bbc.com/sport/0/athletics/34032366>
