M A S A R Y K O V A UNIVERZITA
FAKULTA INFORMATIKY
B u i l d i n g
t h e U l t i m a t e M a t h S e a r c h E n g i n e
P H . D . THESIS PROPOSAL
Mgr. Martin Líška
Brno, 2015
Advisor: assoc. prof. RNDr. Petr Sojka, Ph.D.
Advisor's signature
Contents
1 Introduction 2
1.1 Motivation 2
1.2 Digital Mathematics Libraries 2
1.3 Mathematics Information Retrieval 3
1.4 Conclusion 5
1.5 Outline 5
2 State of the Art 6
2.1 Approaches 6
2.2 Math Indexer and Searcher 12
2.3 Evaluation 16
2.4 Comparison 16
3 Proposed Research 19
3.1 Research Topics and Goals 19
3.1.1 Semantic Based Search 19
3.1.2 Subformula Unification 20
3.1.3 Query Expansion 21
3.1.4 Combination of Different Approaches 21
3.1.5 Combined Text-Mathematical Search 22
3.1.6 Evaluation Framework 22
3.2 The Goal 23
3.3 Publications 24
3.4 Schedule 25
4 Achieved Results 26
4.1 Publications 26
5 Summary 28
A Publications 34
Indexing and Searching Mathematics in Digital Libraries 34
The Art of Mathematics Retrieval: Architecture, Design and Scalability
Issues 51
Similarity Search for Mathematics: Masaryk University team at the
NTCIR-10 Math Task 55
Math Indexer and Searcher under the Hood: History and Development
of a Winning Strategy 61
Math Indexer and Searcher Web Interface: Towards Fulfillment of
Mathematicians' Information Needs 69
Normalization of Digital Mathematics Library Content 73
Building Corpora of Technical Texts: Approaches and Tools 86
1
1 Introduction
1.1 Motivation
Imagine a world where computers do not have input devices. At least not the
devices we are accustomed to - keyboards, mouses, touch pads, fingers on a
touch sensitive screen, etc. On the screen of computers there is a mouse cursor
waiting for the user to move it to the desired destination to perform a click
operation. Imagine that to move this mouse you have only one input device a
numerical keyboard on which you can type the coordinates of the position
where you want to place the cursor, and one key to confirm the position. For
typing there would be a virtual keyboard operated by this coordinates-based
mouse-like input device. The vast amount of functionality, abilities and data that
today's computers have would be very distant from users, in fact, inaccessible.
It is the same story with computer systems and search engines. Imagine a
world wide web without the power of Google search engine or, in a smaller
scale, a web forum for growing thousands of different plants without a search
feature. The forum's search would be based only on the names of plants and
not the plants' properties like height, color, etc., so it would still be not very
useful for users doing a research.
This is very similar to digital mathematics libraries (DMLs) and mathematics
information retrieval (MIR). In a common mathematically oriented paper
indexed in a DML, half of the content is mathematics - mathematical expressions,
symbols and formulae. These structures are not only an addition to the
regular text of the documents, but can be actually the core of the content of the
document accompanied and described by the surrounding text. Yet, it is still
uncommon to do search based on mathematical expressions.
One reason is that math search forms a new paradigm of searching that
math researchers are not accustomed to. However, they realize the potential that
math search has and the value it could bring to mathematics related research.
The other reason is that the sophistication of existing math search engines still
does not fully support spreading of this new paradigm.
1.2 Digital Mathematics Libraries
There are several DMLs that could benefit from the ability to search mathematics.
However, only a few of them currently support this type of search. One
exception is EuDML (European Digital Mathematics Library) which uses Math
Indexer and Searcher (MlaS, described in Section 2.2), developed at Faculty
of Informatics, Masaryk University. Another example is DML-CZ (Czech Dig-
2
1. INTRODUCTION
ital Mathematics Library) in which there is an integration of MlaS currently
ongoing.
One of the most significant digital libraries is arxiv.org e-print archive for
STEM sciences as well as other domains [8]. Number of submission currently
presented by arxiv.org is nearly 1,000,000. Another popular DML for mathematics
is Euclid [9] with around 130,000 papers online.
1.3 Mathematics Information Retrieval
Mathematics information retrieval (MIR) is a broad term for all activities related
to obtaining information from a collection of resources and answering
an information need that involves mathematics. A concrete implementation
usually means a search engine that is able to answer a query containing mathematics
from a collection containing mathematics. The following sections briefly
describe main aspects of MIR that need to be considered when building a math
search engine. The aim of my thesis is to develop on some of the following
aspects as described in Section 3.
Preprocessing
A document in a searched collection which serves as source of information can
come from different sources. It can be a harvested web page, a PDF document
or a TgX source document. Most of the scientific papers are created using TgX
with math typeset in some version of TpX markup (AMS, etc.), however there
are only PDFs available for some documents.
Another aspect of an input document is its encoding. Mathematics can be encoded
in TpX, MathML, OpenMath or OMDoc format. Some of the formats are
convertible, other can be powerful only when specifically authored. Depending
on the input format of the documents and representations of mathematics, an
appropriate preprocessing methods need to be chosen to enhance the input, e.g.
canonicalization, and make it usable for searching purposes.
Indexing
Indexing is the most important section which covers translating input documents
into searchable units according to the chosen data representation. This
may include further processing steps which enhance system's usability, precision
as well as performance. The data representation can be based on the
presentation of the formulae (syntactically-based) or the meaning of the formulae
(semantically-based). In general, there is a natural motivation and effort
to understand both the indexed as well as queries formulae - if the system
understands what the user is looking for, it can return the right results even
though the presentation of the formulae may be different.
3
1. INTRODUCTION
Some of the other aspects in the indexing phase are formulae tokenization
that enables searching for subformulae, normalization, similarity weighting,
semantic processing as well as converting into final data structures.
Searching
Searching is the part of the workflow which is responsible for getting a query
from a user, which starts with a user interface, then translating the query into
an appropriate system query or a set of queries according to the used indexing
approach and finally presenting the result list back to the user. The system
needs to offer an easily usable means for inputting queries as well as clear
presentation of the results that allow user to quickly evaluate the relevance to
their query.
If the system supports querying in different languages, it needs to convert it
to the form understandable by the system. If the system supports the queries in
the form of text as well as math, it needs to properly combine these parts of the
query into one or more system queries as well as to weigh them against each
other.
Evaluation
The evaluation aspect of MIR is an integral part in developing indexing and
searching strategies [23]. When developing new or enhancing existing indexing
features, the impact on the systems precision, i.e. relevance of results needs to be
assessed. A typical evaluation framework consists of a document collection, a
collection of queries and a set of relevance judgments for document-query pairs.
Ideally, this triple as well as the evaluation process is supported by a software
which then can automatically judge the increase or decrease of effectiveness of
a system after a change.
Performance
A MIR system aimed for the real world usage, typically for a DML, is a searching
tool deployed on hundreds of thousands of documents (and millions of
formulae). Arxiv.org indexes almost 1,000,000 articles. However, a search system
is expected to have as low latency as possible. The indexing and searching
methods that are used need to always consider this. A system can use precise
matching methods based on the semantics of formulae and achieve 99%
precision of the results. However, such methods can be intensive from the performance
point of view resulting in the indexing speed of 100 documents per
hour and average query time of 60s per query. Such system will not be used by
users at all.
4
1. INTRODUCTION
User Interface
Not very much attention was paid to the design of user interafce of MIR systems.
User experiments were performed using math expression drawing canvas for
inputting math queries [45]. An appropriate user interface can encourage users
to using math expression as a part of their query as well as can make working
with the system easier.
1.4 Conclusion
For the last few years mathematicians and librarians have devoted to the
digitalisation of past mathematical literature and making it as available as
possible together with newly published literature in one place. This is the main
reason why MIR has emerged and got more and more popular over the last few
years. Emerging DMLs, e.g. EuDML or planned WDML (World DML), as well
as established DMLs all have a need for a powerful way to search through its
resources.
An evidence of the recognition of MIR as a new domain of Information
Retrieval is the establishment of Math Task at NTCIR evaluation forum [4, 5].
The availability of the rigorous evaluation process, even though it is held only
every one and a half year, has drawn even more attention to MIR. IR experts
from other domains try to find their best ways to search structured mathematical
information.
There are several aspects that play role in a good performing MIR system.
Each group that researches these aspects and develops methods supporting
them can have a different approach in accomplishing their goal, which can also
be slightly different from each other.
My goal is to create the ultimate MIR system aimed for the real world use
in DMLs. I want to accomplish this by enhancing our system MlaS, which is
currently the best performing according to the recent evaluation [5].
1.5 Outline
The rest of the Thesis proposal is structured as follows: Section 2 describes and
compares existing approaches in MIR related aspects. The section also describes
the current state-of-the-art of the MlaS system more in depth as this is our
approach to MIR. Section 3 introduces several topics that form the proposed
research. Previously achieved results and the list of publications can be found
in Section 4 followed by the summary in Section 5.
5
2 State of the Art
Mathematical search has been explored and developed for almost 10 years
now. Yet, in my view, it is still not very usable for its potential users and
therefore still not wide-spread among DMLs. The evidence is currently only
MlaS, MathWebSearch and L^TgXSearch are deployed in live environments,
some of them with unsatisfactory results. This chapter summarizes the existing
approaches to building math-aware search engines and their coping with the
requirements.
In the second part of the chapter the state of the art of the evaluation of
math-aware IR systems is described.
2.1 Approaches
There are several research groups that aim at creating well performing and
usable math search engines. Every group has a different approach to individual
tasks pointed out in the previous sections. This section descriptively compares
main aspects of MIR of currently developed systems and a more complete
description of the MlaS system.
The systems presented here have been previously compared in [22]. In [23]
new or previously unstated information were summarized. Some of the systems
that have been previously introduced are again summarized in this text to keep
a complete information about notable approaches in the past as well as in the
present time. As opposed to [14], where seven general approaches (algorithms)
to retrieve mathematical data were evaluated, the following sections describe
real existing systems.
MathDex
MathDex was one of the first math-aware search engines developed [28]. It
crawls the Web looking for documents containing mathematics, which are then
converted by different converters to XHTML containing Presentation MathML
for mathematics. MathDex normalizes MathML notation, corrects possible
errors and canonicalizes it. Math trees are linearized to strings and indexed in a
regular full-text index. MathDex is therefore a syntactically-based system.
MathDex is able to search for text as well as math in a single query, which
is internally split into multiple queries searching over different fields - text
or math - in the index. Even mathematical content is split into multiple fields
based on the type of the expressions, which, as reported in [28], is beneficial for
the performance.
The MathDex project no longer seems to be alive nor is a working public
demo available, nevertheless, the ideas of indexing real-world semantically
6
2. STATE OF THE A R T
poor documents, enhancing the notation, preprocessing mathematics to allow
some degree of similarity in searches and using conventional full-text indexing
engine has inspired many of its successors.
DLMF Search
Digital Library of Mathematical Functions [34] (DLMF) is a web counterpart to
NIST Handbook of Mathematical Functions, a project of National Institute of
Standards and Technology (NIST). DLMF provides reference for researchers
and other users in applied mathematics and many other research fields who
daily encounter special functions in the course of their work.
DLMF was developed according to the general design principles described
in [26] and [27], however, it is deployed in an environment with data in controlled
format. To allow similarity search, query relaxation is used. The ranking
is based on the type of matched expression - definitions rank the highest, followed
by theorems, etc. Formulae metadata are also indexed to allow searching
for these objects by their natural language expression. DLMF data are indexed
using a standard full-text index, therefore it supports text as well as math
querying naturally.
MgX Search
I^TpX Search is a search tool provided by Springer [40]. The system searches
over the documents in Springer corpus of literature.
Very limited information about the tool is officially provided. From empirical
testing we assume that math formulae from TgX sources of the documents are
indexed. TgX is the query language for mathematical expressions. The system
supports very little similarity searching capabilities and needs considerable
time to complete queries. The system does not support mixed mathematical
and textual queries even though it probably uses a full-text index and is able
to search in titles and by DOI independently. We can only suggest that the
math-aware searching works on matching TpX strings using an unspecified, but
rather limited similarity algorithms.
The system seems to have not been changed for several years maintaining
its original features, speed and user interface. According to the [40] the system
searches through about 8.2 million formulae, which from the statistics of
arXiv.org could be between 10 and 15 thousand documents.
Math Go!
MathGo! is one of the oldest systems in the overview. It named several issues
to building a math search system [3].
7
2. STATE OF THE A R T
Math formulae are preprocessed in several ways. The system uses MathML
as an internal representation for mathematics. MathML tree is converted to regular
expressions which are indexed in a standard full-text index. Additionally,
keywords are mapped to expressions to disambiguate the meaning.
To rank the results, the system uses an enhanced TF-IDF formula, which
uses cosine similarity of vectors build from mathematical equations. As an
input language, Math Go! uses an equation editor. The system also addresses
performance issues by employing clustering techniques.
LeActiveMath
LeActiveMath is an intelligent web education environment for self-learning according
to users' own preferences. This is a closed environment with documents
and mathematics encoded in OMDoc and OpenMath format respectively.
The system has a math-aware search tool [20,19] allowing users to search
in titles, textual content, metadata as well as mathematics. OpenMath standard
encodes semantic information with the formulae, however, the system uses a
full-text search index for data storing and query matching. We can therefore
classify this system as a mixed approach.
In the indexing phase, OpenMath tree structures are converted into textual
tokens. Queries are converted similarly to text tokens and the query is expanded
into multiple system queries that allow matching of subexpressions.
Neither LeActiveMath seems to have any ongoing development.
EgoMath
EgoMath is a math-aware search system aimed for semantically poor real world
documents and the documents in digital mathematical libraries [30, 29, 32].
The system uses MathML as an internal data representation format for
mathematics. There is tokenization in the process of indexing as well as generalization
algorithms that allow similarity searching. One formula is represented
by many textual tokens in the index. As I have discovered in my diploma
thesis [23], similarity search is enabled via two algorithms - augmentation and
ordering. The augmentation generalizes math structures and produces several
differently generalized representation for one formula. The ordering algorithm
orders parts of augmented expressions to produce their canonicalized form.
These tokens are indexed by a full-text indexing core EgoThor.
EgoMath seems to no longer be under development. Its previously publicly
available demo interface have been unavailable for several years as well as is
now the project website [31].
8
2. STATE OF THE A R T
MathWebSearch
MathWebSearch is a substitution based search engine for mathematics [17,15].
As the only system described in this text, MathWebSearch does not use fulltext
index for storing mathematical content. MathWebSearch depends on the
semantic annotations of encoded mathematical expressions and uses mainly
Content MathML as its internal format. The lack of Content MathML documents
is compensated by using LTpXML converter [41].
MathWebSearch uses substitution trees to index math expression trees. In
these substitution trees the root node is a general term and every child node
represents a substitution of one term or subtree. The system naturally supports
query variables in which users can indicate a part of the query as a variable and
the system is able to match any subtree in the place of the variable.
A disadvantage of this approach is that it does not naturally support weighting
of individual substituted expressions from the substitution tree and makes
it more difficult to develop a custom scoring function to order the result list
based on some similarity measure with the query. Another disadvantage is that
textual searching is neither naturally supported and therefore a second index
with textual data needs to be maintained and the results from these indices
merged back together according to some algorithm [16].
That said, MathWebSearch in its latest version [13] uses a second full-text
index for keyword search provided by ElasticSearch [1]. It is therefore able to
search for text as well as math with a single query MWS supports only a basic
notion of ranking that prefers formulae over keywords. Formulae are scored by
the size of the substitution and keywords are scored based on the ElasticSearch
scheme.
MCat
MCat belongs to the newer group of math search systems. It is being developed
at Nil in Japan and was described in [33] and [44].
The system extracts three types of features from the mathematical formulae.
First type is ordered paths, which means paths from a root node of a tree to all
leaves of the tree while preserving the exact order of child nodes. The system
extracts not only paths from a main root node to leaves, but also from any other
inner node to its respective leaves. The second type of feature is unordered paths.
These paths are similar to ordered paths but without the ordering information
of the nodes on the path. The paths does not store information about the type
of the inner nodes, it only stores the node type of leaves as well as its value.
The third type of nodes are sisters - the list of nodes which are sisters in each
subtree. All these features encode information about the structure of a formula.
Additionally, the system tries to disambiguate the meaning of formulae
with the information taken from a text window around them. By using NLP
9
2. STATE OF THE A R T
and machine learning methods the system extracts noun phrases in the narrow
window around the formula and builds a dependency graph of mathematical
expressions. Both context window and descriptions from dependency graphs
are indexed [18].
When retrieving matched items for a query, a similarity between the query
and the matching documents is computed. This similarity measure is a combination
of a structure similarity and a content similarity. Structure similarity is
an Euclidean distance of the paths in a query and the paths in matched documents.
Similarly, content similarity is based on the content (operators, numeric
constants and identifiers) of query and matched formulae.
FormulaSearchEngine
More than a standalone search system, FormulaSearchEngine is a set of experiments
of approaches in querying mathematical content from scientific
documents.
There were experiments on employing Stratosphere execution framework
instead of pre-building a static index that is then searched in [38]. Each query is
transformed to a set of different features which may use regular expressions.
There are several tasks that are run through the document collection. One of the
tasks is an extraction task to extract necessary information and data (formulae)
from the documents. Another task is the filtering task that filters the query
match candidates from the corpus. Another task then scores the hits according
to the preset similarity measures and ranks the results.
Later experiments are focused on the formulae matching and similarity
determining methods described in [47] and their evaluation. The methods
include taxonomy classification of the functions, data-type hierarchy, depth of a
subformula match, amount of matched terms and structure and finally formula
vs. expression consideration.
TUW-IMP
TUW-IMP is a team that developed a search engine for NTCIR-11 Math-2
Task [5]. It extends a regular full-text search supported bu Lucene by preprocessing
methods for mathematical content and results merging and ranking [21].
The system builds an index for regular text that is analyzed using English
Minimal Analyzer to preserve proper names, mathematicians' names and common
mathematical phrases. Mathematical formulae are tokenized. There are
three tokenizers used. The first extracts only formula literals. The second tokenizer
extracts formulae subtrees that are on each level of the original formula.
These subtrees are one level deep and have a special symbol placed in the place
of child nodes. The third tokenizer extracts subtrees that are two levels deep.
10
2. STATE OF THE A R T
The tokens are stored in three different indices. The system queries the text
index with query terms and three mathematical indices with formula terms.
The system compares the formulae found in the retrieved documents with the
formulae returned from the mathematical indices.
Tangent
Tangent is a math-aware search system that uses a federated search over two inverted
indices - the first for TF-IDF text search and the second for mathematical
expressions [35].
Mathematical expression are represented as symbol pairs. Each symbol pair
is a tuple consisting of all pairs in an expression paired with all of the symbol's
children (direct and non-direct). The level distance between the main symbol
and a child symbol and their vertical distance complete the tuple. The tuples
are stored in a first inverted index pointing to the original expressions which
are stored in the second inverted index pointing to the original documents.
The results from the two indices are combined using a linear combination
factor that can be varied. The Tangent system also addresses retrieving special
constructs as matrices and sub/superscripts as well using query variables.
Tangent turned out to be the second best performer at NTCIR-11 Math-2
Main task as shown in Section 2.4.
ICST System
A team from Peking University joined NTCIR-11 Math-2 Task with their proposed
system [12]. ICST System processes only Presentation MathML to extract
math information from documents. It then applies basic tokenization and generalization
algorithms to allow similarity search. The system is reported to
have very poor performance which prevented it from receiving satisfactory
evaluation scores.
QUALIBETA
Qualibeta is the first attempt to build a MIR system by IFIS, Technische Universität
Braunschweig [36]. Their approach is a feature extraction from both
formulae as well as text. For mathematics, the system extracts from Content
MathML four types of features: category of the formula, set of unique identifiers,
set of operators and a set of constants. For textual content, the systems considers
three sentences surrounding a formula: before, after and where the formula
appears. From the sentences, the system extracts noun phrases and verbs. All
extracted keywords are stored in a full-text index provided by ElasticSearch [1].
In the searching phase the query is converted to the same set of features which
are then combined using different boolean operators to form the final query.
11
2. STATE OF THE A R T
2.2 Math Indexer and Searcher
Math Indexer and Searcher (MlaS) is a math-aware information retrieval system
that was developed and first described as a part of my Bachelor thesis [22]
called Vyhledávání v matematickém textu (Searching Mathematical Texts). It
researched existing approaches to math searching to date and based on the
findings designed and developed its own solution for real world usage. It aimed
to be used in environments with large document bases as those in digital mathematic
libraries such as EuDML [42] or DML-CZ. Math processing functionality
used in MlaS was subsequently integrated into EuDML's search [10].
MlaS is a math-aware full-text based search system. It enables users to
search for mathematical formulae and expressions contained within indexed
documents encoded in the MathML format. It is a Java-based server application
and is coupled with a web interface, WebMIaS. The application was built on the
top of the state-of-the-art full-text indexing system Lucene [43] (current version
4.5.0). Mathematical preprocessing part (Figure 2.1) is built as an extension and
can be easily plugged into other Lucene or Solr based systems and with few
modifications possibly to any full-text search engine. The general overview of
the system's components and its workflow with the detail on math processing
is displayed in Figure 2.1. MlaS deals with different aspects of MIR, which is
described in the following sections.
Math Processing
Special attention is being paid to the processing of math formulae so as to enable
similarity search - users are able to retrieve not only exact matches for their
queries but also equal formulae written differently up to a certain level of mathematical
equivalence; similar formulae and subformulae. The system builds a
static index, therefore handling all sorts of problems with matching mathematical
expressions are underpinned in the preprocessing stage. Matching of tokens
is then left to well-established conventional full-text search. Expressions are
processed in several steps, functions. Every function creates modified formulae
which are more generalized than the original one. Every formula is assigned
a weight which denotes its distance from the original form extracted from a
document. This weight enables the system to rank the results and order hits
accordingly from the most relevant to the least. A detailed overview of the
preprocessing of math is displayed in Figure 2.1. There are five methods currently
carried out in the math preprocessing module: canonicalization, ordering,
unification of variables, unification of constants and finally MathML attributes
handling.
Canonicalization turned out to be a very important preprocessing method
in the workflow. MlaS has so far indexed documents with MathML generated
by LTgXML but users of WebMIaS are able to input lATgX queries which are
12
2. STATE OF THE A R T
Figure 2.1: Math preprocessing
converted by a converter. They can as well directly paste MathML. This led
a team at Masaryk University to develop its own solution mainly for the use
of MlaS [11]. The canonicalizer contains several modules, each of which aim
at reducing variability in MathML notation in one aspect, e.g. reduction of
unnecessary mrow elements. It is important to apply the same canonicalization
on input documents during indexing as well as on user input in the searching
phase.
Weighting and Fine Tuning
Ranking hits is one of the most important aspects in the search process. Hit
ranking designates the order of search results and can have considerable affect
on the perceived quality of the system. MlaS depends on a fine tuned hit scoring
function of a conventional text search (i.e. TF-IDF) and adds a math-specific
parameter to it and argues with [46].
The unification methods produce formulae that are more generalized than
their original forms. MlaS indexes all versions of math expression that are generated
in the process, which also means that all these expressions can be matched
13
2. STATE OF THE A R T
when searching. The system needs to discriminate between these matches based
on their generalization level. More generalized formulae are assigned a lower
weight so they appear lower in the result list than less generalized formulae hits.
MlaS introduces a metric which defines the distance of a generalized formula
from its unmodified and untokenized form.
M-terms
The final stage in the preprocessing of the mathematics contained in documents
is producing text tokens representing formulae so they can be stored
by the indexing core. MlaS transforms MathML XML nodes to linear strings
using bracketed prefix notation. For example a formula 4? with its Presentation
MathML representation
<math >
<mfrac >
<mn>l</mn>
<msup >
<mi mathvariant="bold">x</mi>
<mn>2</mn>
</msup >
</mfrac >
</math>
is rewritten to mfrac(mn(l)msup(mi [mathvariant=bold] (x)mn(2))).
Every formula in MlaS is coupled with a weight that was computed during
the preprocessing. Ordered pairs of string representations of formulae and their
weights - (string formula, weight) - we call M-terms. They might be usable not
just for indexing and searching but also for other applications. In fact they are
as well an another representation of formulae in documents and can even be
encoded together with regular MathML within an appropriate tag.
Scalability experiments showed that the size of the index can be considerably
lowered by substituting MathML element names, attribute names and
common attribute values, which are constantly repeating in expressions. MlaS
uses a dictionary, which maps repetitive items to single characters, in order
to compact the string representations of formulae The resulting form of the
previous example after applying the dictionary isF(N(l)J(I [V=B] (1) N (2))).
Searching
When a user writes and posts a query to the system it is important it passes the
same processing as in the indexing phase for the system to be able to match
indexed tokens, whether it is stemming regular text or transforming query
14
2. STATE OF THE A R T
formulae to M-terms. There is however one exception in the processing of math
- query formulae are not tokenized.
Several (4 or 5) M-term representations of each query formula are produced
during preprocessing. Generated weights are not used and only formulae
strings connected to the textual part of the query are passed to the searching
core in the following manner: (formulai V ... V formulan) A (termi V ... V
termn). Users can override this default query composition by manually stating
preferences for query tokens to occur in the matched documents by using AND
and OR operators.
MlaS additionally sets the boost for query formulae according to their
complexity. This has two reasons: one is to counterbalance text and formula
parts of the query since matched expressions can be indexed with relatively low
weight, and secondly to balance weights between different query formulae. The
bigger a formula in the query, the bigger weight it should have in the resulting
score of matched documents.
MathML Processing
MlaS aims to process real world documents. It was primarily focused on Presentation
MathML markup, which can be relatively easily converted from the
format most used by authors - TpX and its variations. Its biggest advantage,
availability, is negated by several downsides. For machine processing it contains
a lot of unnecessary markup which is used mainly for nice rendering. There is
very little semantics in the encoded formulae, i.e. element <mi>f </mi> can not
be told whether it is a variable or a function name or the name of some constant.
To extend precision coming from the semantic character of Content MathML,
MlaS expanded its capabilities and is now able to index Content MathML in
the same way as Presentation MathML.
Generating Snippets
The MlaS system is capable of showing match snippets to the user. As opposed
to regular text search, math preprocessing changes the visual of expressions
quite heavily (consider Section 2.2), so it can not show retrieved matched terms
directly from the index. MlaS indexes math terms together with their positions
in the original documents. Since MlaS weighs every formula, when a query
hits a document the most significant terms can be easily retrieved together with
their positions. The position is a sequence number of a hit formula among other
document formulae; other document terms are not considered. Derived and
extracted M-terms hold the same position information as their original formula,
therefore when a query matches a subformula, the system can only highlight
the whole original formula.
15
2. STATE OF THE A R T
Optimisations
MlaS tackles performance issues in several forms. As to the speed of the indexing,
MlaS uses a multi-threaded computing flow for preparing and preprocessing
documents, especially for the most time consuming preprocessing of math
formulae. To reduce the space requirements of the index, M-terms compacting
is done as well as the optimization on the level of choosing the right data types
for various data stored in the index. To reduce the space requirements of the
document collection, MlaS is able to read documents from a zipped archive.
Web Interface
MlaS uses a simple and straightforward interface for writing queries - only
one input text box, where users can write text and math queries at the same
time. Query formulae are accepted in MathML notation as well as TgX. MlaS
is able to auto-detect TgX math that is surrounded by $ signs, and converts it
after the submit by LTgXML converter. For even better usability, TgX queries are
converted on-the-fly to presentation MathML by the SnuggleTeX [37] converter
and rendered for visual verification by Mathjax [25].
2.3 Evaluation
Evaluation of information retrieval systems is an integral part of developing
new techniques or enhancing current approaches. Official evaluation happenings
that serve as a testing ground are held at well-known conferences like
TREC, CLEF or NTCIR. Different approaches to same domains of IR can be
compared at these conferences and usually, one team can submit multiple runs
to compare variations of the same methods. Official evaluation of MIR systems
was held already two times at NTCIR as a Math Pilot Task and Math-2 Task
and once as a pilot workshop called MIR Happening at CICM 2012 [6].
An evidence that MlaS with its design decision and implementation works
very well among other MIR system are the results of NTCIR Math 2 Task.
8 teams which included for example MCAT, FSE, MathWebSearch and others,
submitted 20 runs in total. Four metrics were evaluated for two different relevance
levels - relevant and partially relevant results. Our MlaS system was
ranked the first in 6 out of 8 evaluated metrics, and in the remaining two it was
ranked second. The complete results are shown in Table 2.1 and Table 2.2.
2.4 Comparison
In [39] we compared available systems by 2011. The systems were for completeness
shortly described in the previous sections. In the comparison Table 2.3
16
2. STATE OF THE ART
Table 2.1: Results of submitted runs with Relevance Level > 3 (Relevant)
PMath CMath PCMath TP*
MAP avg 0.307 0.363 0.359 0.335
P-10 avg 0.304 0.352 0.348 0.338
P-5 avg 0.512 0.568 0.556 0.540
Bpref 0.462 0.513 0.500 0.478
Table 2.2: Results of submitted runs with Relevance Level > 1 (Partially Rele-
vant)
PMath CMath PCMath TEX
MAP avg 0.255 0.280 0.279 0.274
P-10 avg 0.502 0.544 0.552 0.540
P-5 avg 0.844 0.872 0.864 0.848
Bpref 0.454 0.473 0.474 0.472
only the systems that are new or have undertaken significant changes and are
still under development are listed. All of the compared systems as they entered
NTCIR-10 Math Pilot task or/and NTCIR-11 Math-2 Main Task are processing
XHTML containing mixed Presentation and Content MathML. The systems
are able to search mathematical as well as text content of the documents and
combine the queries into a single result set. Since all of the systems entered
NTCIR-11 Math-2 task it is possible to extract a rank from the evaluation to
see how does their approach perform. The rank in the table is extracted from
best performing run of each system using the Bpref metric on relevant (R) and
partially relevant (PR) results [5].
From the comparison as well as from our latest experiences we see an ongoing
interest in using preprocessing methods for mathematics that extract
features that preserve structural information from the formulae (MlaS, MCAT)
as well as relationships of operators and literals that may denote some semantical
meaning of the formula (TUW, Tangent). These features are usually stored
in a full-text index for performance reasons and out-of-the-box TF-IDF scoring
(MlaS, MCAT, Tangent, TUW).
An emerging requirement is to handle query variables or wild cards. Using
query variables user can denote concrete literals (identifiers, numbers, operators)
as query variables that can be substituted in the result. By using wild
cards user can query for expressions that have an arbitrary subtree in the place
of the wild card. Some of the systems (MathWebSearch) support these features
naturally, others have to adapt.
The MlaS approach that extracts all subtrees of an expression that are then
unified and weighted, then converted into linear strings stored in the full-
17
2. STATE OF T H E A R T
Table 2.3: Comparison of math search systems. The ranks are extracted from
best performing run of each system in NTCIR-11 Math-2 Task using the Bpref
metric on relevant (R) and partially relevant (PR) results.
System Internal representation/approach . c f
• c
•£
A* Rank
R / P R
MathWebSearch Substitution trees, full-text index
with full texts
• X • 2/3
MCat Ordered and unordered path features
and sibling features in a fulltext
index, context window and
dependency graph noun phrases
for text search in a full-text index
• • X 4/4
FSE Original documents, linear search
using regular expressions
• • • 6/7
TUW-IMP Literals, one and two level subtrees
in a full-text index, full-text
index with full texts
• • • 5/5
Tangent Symbol pairs tuples in a full-text
index, full-text index with full
texts
X • • 3/2
ICST generalized subtrees in a full-text
index
• X X 8/8
QUALIBETA text and math features in a full-text
index
• X X 7/6
MlaS Canonical M a t h M L subtrees as
compacted strings (M-Terms), one
full-text index for full texts and
mathematics
• • X 1/1
text index together with textual content of documents and queried by query
expansion techniques proves to be a sound solution that is efficient as well.
18
3 Proposed Research
Previous chapter summarizes different approaches to MIR. They vary in many
aspects of the whole retrieval package. One of the most important aspects is the
representation of math inside the system that determines and influences most of
the other core aspects like preprocessing as well as storing methods. There are
systems that base mostly on the content of the harvested mathematics and there
are syntactically driven systems as well, which, based on the current evaluation
results, perform no worse than semantically driven systems. However, there
is undeniable effort to introduce more semantics to the search process as it
promises to bring more precision to search.
We have built MlaS, math-aware search system. As described in Section 2.2,
MlaS is syntactically based. It originally used only Presentation MathML for
mathematics. It preprocesses MathML notation to utilize the structure information.
Later, we included Content MathML support for better, more notation-clear
representation. The next section lists topics of interest of my research.
3.1 Research Topics and Goals
As shown in Section 2.3, MlaS approach is currently one of the most reliable in
terms of precision and relevance of the results returned to users. In my work,
I want to build upon the current performance of MlaS and research further
methods and topics that could possibly make the system perform even better.
The topics on which I would like to research are described in the following
sections.
3.1.1 Semantic Based Search
MlaS preprocesses mathematics from the documents as well as from the query.
The generalization process is currently limited to ordering of the operands of
commutative operations (so a + 5 matches with 5 + a), unification of variables
with respect to bound variables and unification of numbers. To perform semantical
solving of formulae to match on their actual value is unfeasible at the level
of XML tree processing. Such operations are associativity, distributivity, fraction
operations, etc. I think that this kind of formula preprocessing can be helpful
in many cases, especially when user posts a query formula that can be further
simplified.
Computer algebra systems (CAS) are software programs that allow computation
over mathematical expressions. Involvement of CAS in MIR can provide
basic computational power over expressions found in the documents in the
index as well as query expressions.
19
3. PROPOSED RESEARCH
I would like to research on the strategy of the efficient incorporation of
computer algebra systems as a way to increase precision. The main idea of
integration of CAS is that every formula from the document can be simplified
using CAS and then acted as if it was found in the document. It would be
therefore stored on the position of the original formula in a generalized and
tokenized form for it to be searchable by queries. Query formulae can be
simplified as well and added to the list of original query expressions before the
unification process. This approach will give the maximum versatility and could
increase the system's recall as well as precision. An appropriate weighting
method for formulae matched on the basis of CAS simplification would need
to be determined as well.
3.1.2 Subformula Unification
In text search users can usually perform search using wild cards. Generally, a
wild card is a special character that can be substituted by any other character or
a string of characters, or any other appropriate data type.
In MIR, these wild cards are called query variables, and can stand for
different types of tokens in an expression. For example, a user can put a query
variable in the place of an operator in case they don't remember it or don't want
to rely on a specific operator. Similarly, a user can place a query variable in the
place of a variable or a number literal in case they don't want to rely on a literal
variable or number. Most importantly, a user can put a query variable in the
place of a whole expression's substructure. This can be helpful when a user
remembers only a part of a formula or does not want to specify unimportant
parts. For example, a query JJ? can match both and Ef=i/ where ? is a query
variable. Another use is when a user wants to search only by the structure of
expression. They can pose a query in the form ^y^+? which could match a lot
of different possible expressions, but with a required fraction, addition of 5 in
the numerator and some addition to the whole fraction.
An effective implementation of this type of unification will not be a simple
task in the context of MlaS. A naive approach would perform a basic string
search with wild cards. This would mean iterating over all terms in the index
and would cause an unacceptable query time. Formulae supporting query
variables need to be stored in the index so they can be directly searched like
other terms in an inverted index. To create all combinations of substituted
subexpressions in a formula would again be unfeasible due to the performance
reasons.
I would like to research on the best strategy to implement indexing with
substructure unification that would enable search with query variables. A tradeoff
method between subexpression unification and good efficiency needs to be
designed. Level based subexpression unification outlined in [24] is one of the
possible ways. To ensure ranking based on the similarity of matched terms and
20
3. PROPOSED RESEARCH
documents to the query, a substructure unification factor will be determined
and introduced into the weighting scheme.
3.1.3 Query Expansion
To increase recall of not very successful queries, query expansion and resubmission
is a useful technique. When a user posts a query that finds no or very
few results, in order to give at least some results to the user albeit with a lower
score, the query can be modified or relaxed and the search run again. A method
to expand query to multiple queries where each query is a subset of the original
query mathematical and textual terms was proved to be very helpful [24]. This
was a first experiment in this direction and in my thesis, I would like to research
on this topic further.
Two types of query relaxation are possible. One way is to reduce the number
of terms if the query consists of more than one term. A combination of reduced
terms needs to be selected, especially if the query consists of text as well as
math terms. More query term combinations can be run through the system one
after another. The important step is then an effective algorithm to merge result
lists with an appropriate weighting. The basic rule for a weighted merging
should be that more reduced query the lower score its individual results should
get.
Another type of query relaxation could be mathematical expression relaxation.
If a query expression is an actual formula with equal sign, the expression
can be split to left and right side of the equal sign. These expressions can then
form a new query. If the system supports wild card search as described in Section
3.1.2, queries could be relaxed by automatically inserting query variables.
3.1.4 Combination of Different Approaches
MlaS currently uses a single approach to preprocess, store and search mathematical
expressions. This method has its own rules and a weighting scheme. To
increase precision of a MIR system, a different approach can be introduced to
the same system that can lead to a better performance in a combination with
the original method. Such a simultaneous use of two or more methods would
need a combinative mechanism that outputs a single result list as a response
to a query. For example, introduction of formula structure features extraction
can work as a precise method focused on expression's structure. It then would
need to be coordinated with the original M-terms method in terms of result
lists merging and weighting.
Mathematical domain uses a lot of different constructs to express the meaning
of the underlying semantics. Another reason to introduce more methods
into a single MIR system can be that such different constructs, e.g. matrices,
can be searched in a more effective way if they were preprocessed or stored
21
3. PROPOSED RESEARCH
differently. This means analyzing a query in order to apply a correct method
for the search. Such a non-parallel use of more searching methods needs to be
researched and evaluated as well.
I would like research on the possibilities and general rules when two or
more approaches need to be combined within a search system. These rules will
be applied in the experimental addition of the second approach to MlaS. The
idea is to have a second method for extracting features capturing semantics of
formulae.
3.1.5 Combined Text-Mathematical Search
Math-aware search system should always be able to search for math as well as
text in a single query. Both math as well as text keywords serve a discriminative
purpose and effectively narrow down search results.
However, the right combination of both aspects needs to be assessed for a
concrete environment for a maximum performance. The combination consist of
two parts. The first is a right use of query operators between multiple text terms
and math terms. We have to also keep in mind any possible query expansion.
The second aspect is a mutual weighting factor between text and math. What
should play a more important role in a search? This question gets more complex
again if we consider multiple math as well as multiple textual terms in a single
query.
In my work, I would like to reevaluate the possibilities combining text and
math parts of a query into a better performing unit. I will start from the current
implementation in MlaS. Query expressions (text and math) written in one
input field are combined into a system query of the form (formulai V ... V
formulan) A (termi V ... V termn). In terms of weighting, MlaS prefers math
expressions match over text using a factor that multiplies scores of all math
query terms at the beginning of search. The final reevaluated model will be
generalized to a set of combination principles that could be implemented into
any math-aware search system.
3.1.6 Evaluation Framework
An organized evaluation event is a source of valuable information for IR system
developers. Nevertheless, for development-time evaluation, that is when
refining indexing, searching, ranking and other methods directly influencing
the system's precision, a local evaluation framework or process is needed. This
may seem as a not very difficult task, but the opposite is true. As described in
Section 1.3 a test collection is necessary.
The most important part in the collection are the relevance judgments. They
are usually triples; one triple consist of a document, a query, and a statement,
whether the document is relevant for the query. The relevance judgments are
22
3. PROPOSED RESEARCH
usually very expensive since they are time consuming to produce and should
be ideally made by mathematicians.
At the time of writing this text NTCIR-10 Math Task collection and NTCIR-11
Math-2 main task collection are two available datasets.The former dataset is
not ideal for the use as it is relatively big for daily usage and it is deformed in
a way that it only evaluates single formula hits, which is artificial for the real
world usage.
The other important thing in a local evaluation process is a software, that
takes such evaluation collection and an IR system and outputs evaluation
metrics. Such system should as well support the creation of the collection by
providing an interface to input and store relevance judgments. To the best of
our knowledge, there are only few software programs for evaluation currently
available.
One that is used at NTCIR Math task is SEPIA (Standard Evaluation Package
for Information Access systems) [7]. This tool is useful for creating evaluation
collection, creating topics and a pool of annotated answers. The tool however
does not solve evaluation metrics computing nor it does directly query search
systems.
In the course of my studies I want to form and analyze the requirements for
an evaluation framework. The implemented solution may or may not be built
on the existing evaluation software, e.g. SEPIA, but it will serve the purpose
of instant development-time evaluator of the math-aware search systems. The
system will be general enough so it could be used to evaluate MIR systems that
would meet basic requirements.
3.2 The Goal
In the previous sections six MIR related topics were introduced. Each of these
topics will be researched in the course of my studies and will be dealt with in
my Ph.D. Thesis. Each of these topics will have their own discourse and a partial
outcome. The topics together form the main goal of my studies. The goal is to
design the ultimate math information retrieval system. The ultimateness can be
understood as a combination of specific features that all together will support
high precision as well as recall in searching documents with mathematical
content.
Basing on the current state of MlaS and the research topics that form possible
new features, the new system will be able to search primarily by structure
similarity of formulae enhanced by their normalized form provided by CAS.
The system will be ready to incorporate other approaches to search by different
type of information. When matching expressions, the system will be able to
substitute whole subtrees of formulae with users able to optionally specify
parts of query expressions with wild cards. In case of unsuccessful query,
23
3. PROPOSED RESEARCH
the system will be able to expand the query into multiple relaxed queries
and repeat the search to get more relevant results. The development of these
features and experiments on the right setup will be backed up by an automated
evaluation framework telling whether the adjustments had improved or worsen
the effectiveness.
In [14] different theoretical approaches were experimentally compared. The
approach of MlaS was ranked as the third best performing approach. Two other
approaches were ahead of MlaS. The first is based on the math formula tree
similarity with similarity function computed as the edit distance between the
two trees. The second approach is based on patterns. This way, the user can
specify a pattern that matching expressions need to comply with. The user has
more control over the results.
By implementing substructure unification in MlaS we will provide a complete
formula tree similarity matching (SimSearch in [14]). By implementing
query variables that will make use of substructure unification, a pattern like
queries will be enabled (PatternSearch in [14]). This will elevate MlaS approach
- it will aggregate the best of similarity, structure and pattern search. The top
tree approaches according to [14].
3.3 Publications
Following is a list of publishing possibilities:
• SIGIR 2015 (Special Interest Group on Information Retrieval)
http: / / s i g i r . org/ - Short paper about query expansion.
• CIKM 2015 (Conference on Information and Knowledge Management)
http: //www. cikmconf erence. org/ - Integration of CAS with similarity
search system.
• SIGIR 2016 (Special Interest Group on Information Retrieval)
http: / / s i g i r . org/ - Paper on substructure unification.
• NTCIR 2016 (Nil Testbeds and Community for Information Access Re-
search)
http://research.nii.ac.jp/ntcir/index-en.html - Evaluation of the
substructure unification and query expansion techniques.
• ECIR 2016 (European Conference on Information Retrieval)
http: //ecir2015. if s. tuwien. ac. at/wp/ - MIR evaluation framework
description.
• CIKM 2016 (Conference on Information and Knowledge Management)
http: //www. cikmconf erence. org/ - Overall design of MlaS with all the
new features.
24
3. PROPOSED R E S E A R C H
• SIGIR 2017 (Special Interest Group on Information Retrieval)
http: / / s i g i r . org/ - Paper on query variables in a similarity based MIR
system.
3.4 Schedule
Spring 2015
• Research on substructure unification and search with query variables
• Research on query expansion
• Analysis and design of the evaluation framework
Autumn 2015
• Research on introducing CAS to indexing a searching process
• Implementation of the evaluation framework
Spring 2016
• Research on combining multiple approaches in one system
• Research on text-math weighting
• Writing Ph.D. thesis
Autumn 2016
• Finishing Ph.D. thesis
25
4 Achieved Results
In 2010 I finished my bachelor thesis in which I designed and implemented
very first version of MlaS. It was then accepted as a contribution to EuDML and
integrated within the search subsystem. In 2013 I finished my master's thesis
aimed on evaluation of mathematics information retrieval. It was then awarded
3rd best IT related master's thesis in Czech republic and Slovakia [2] out of
more than 2000 submitted and 150 judged thesis in 2013. In 2014 NTCIR Math-2
Task evaluation forum our MlaS system achieved the best overall results. My
poster for the conference was awarded The best poster at the poster session at
our Faculty of Informatics.
4.1 Publications
Full texts of these publications can be found in Appendix A.
• SOJKA, Petr and Martin LÍŠKA. Indexing and Searching Mathematics in
Digital Libraries - Architecture, Design and Scalability Issues. In James
H. Davenport, William M. Farmer, Josef Urban, Florian Rabe. Intelligent
Computer Mathematics Lecture Notes in Computer Science, 2011, Volume
6824/2011. Berlin / Heidelberg: Springer, 2011. pp. 228-243. ISBN 978-3-
642-22672-4.
I am the main contributor to this paper.
• SOJKA, Petr and Martin LÍŠKA. The Art of Mathematics Retrieval. In
Matthew R. B. Hardy, Frank Wm. Tompa. Proceedings of the 2011 A C M
Symposium on Document Engineering. Mountain View, CA, USA: ACM,
2011. pp. 57-60. ISBN 978-1-4503-0863-2.
I am the main contributor to this paper.
• LÍŠKA, Martin, Petr SOJKA and Michal RŮŽIČKA. Similarity Search for
Mathematics: Masaryk University team at the NTCIR-10 Math Task. In
Noriko Kando, Kazuaki Kishida. Proceedings of the 10th NTCIR Conference
on Evaluation of Information Access Technologies. Tokyo: National
Institute of Informatics, 2-1-2 Hitotsubashi, Chiyoda-ku, Tokyo 101-8430
Japan, 2013. pp. 686-691. ISBN 978-4-86049-062-1.
I contributed to the paper with the Sections 4 (Math Retrieval Task
overview from the point of view of MIRMU team) and 5 (Results discussion)
in the paper.
• RŮŽIČKA, Michal, Petr SOJKA a Martin LÍŠKA. Math Indexer and
Searcher under the Hood: History and Development of a Winning Strategy.
26
4. A C H I E V E D RESULTS
In Noriko Kando, Hideo Joho, Kazuaki Kishida. Proceedings of the 11th
NTCIR Conference on Evaluation of Information Access Technologies.
Tokyo: National Institute of Informatics, 2-1-2 Hitotsubashi, Chiyoda-ku,
Tokyo 101-8430 Japan, 2014. pp. 127-134. ISBN 978-4-86049-065-2.
I contributed to the paper mainly with the Section 4 (Indexing Statistics)
as well as the Section 5 (Achieved Results discussion).
LÍŠKA, Martin, Petr SOJKA a Michal RŮŽIČKA. Math Indexer and
Searcher Web Interface: Towards Fulfillment of Mathematicians' Information
Needs. In Stephen M. Watt, James H. Davenport, Alan P. Sexton,
Petr Sojka, Josef Urban. Intelligent Computer Mathematics CICM 2014.
Proceedings of Calculemus, DML, MKM, and Systems and Projects. LNAI
8543. Zurich: Springer International Publishing Switzerland, 2014. pp.
444-448. ISBN 978-3-319-08434-3.
I contributed with the information regarding WebMIaS throughout the
paper.
FORMÁNEK, David, Martin LÍŠKA, Michal RŮŽIČKA a Petr SOJKA.
Normalization of Digital Mathematics Library Content. In CEUR Workshop
Proceedings, Volume 921. Aachen, 2012. pp. 91-103. ISSN 1613-0073.
I contributed to the majority of the sections, mainly to the Use cases
section as well as with the motivation of the paper.
SOJKA, Petr, Martin LÍŠKA a Michal RŮŽIČKA. Building Corpora of
Technical Texts: Approaches and Tools. In Aleš Horák, Pavel Rychlý. Fifth
Workshop on Recent Advances in Slavonic Natural Languages Processing,
RASLAN 2011. Brno: Tribun EU, 2011. pp. 71-82. ISBN 978-80-263-0077-9.
I contributed to the paper with the M-terms description as well as maths
information retrieval overview.
LÍŠKA, Martin a Petr SOJKA. MlaS, WebMIaS (software)
I am the main developer of the system.
27
5 Summary
Mathematics information retrieval (MIR) is a domain specific branch of IR.
MIR aims at searching information in documents with significant amount of
mathematical content in the form of expressions and formulae. It is interesting
in that MIR stands on the border of text retrieval, XML retrieval, structure
search and semantic search. Based on the newly established international MIR
evaluation forum and on the number of MIR related research groups around
the world, it is definitely on the rise.
One group of people will benefit from rising interest in MIR - users of digital
mathematics libraries (DMLs). DMLs are online providers of mathematical
heritage in the form of papers, books, journals, etc. The usability of DMLs also
depends on their ability to provide useful searching facilities for their users.
In this work I summarized different approaches to math-aware search systems.
They were also compared based on the results of NTCIR-11 Math-2
Task [5]. Some of the approaches are more successful, some are less successful
in performing search in real world documents, therefore, not all approaches are
suitable for the environment of a DML.
More detailed description of Math Indexer and Searcher (MlaS) was provided
as this is our system created at Faculty of Informatics, Masaryk University,
primarily designed and developed by me. MlaS is currently reported as the
best performing MIR system [5] in terms of effectiveness. MlaS is currently
deployed in European Digital Mathematics Library [10] providing search over
mathematical expressions to users.
In this work I proposed several topics which are main research interests of
my studies. The topics correlate with possible features that can improve the
effectiveness of a MIR system. Namely, the topics are substructure unification,
integration of algebraic computational power, query expansion, query variables,
combination of more approaches within one system and a combination of text
and math search. One topic that spans over all other topics is evaluation which
is a necessity in a process of continuous improvement of effectiveness.
28
Bibliography
[1] ElasticSearch website, http://www.elasticsearch.org/ (visited on 2015-
01-18).
[2] A C M SPY. A C M SPY 2013. http://www.acm-spy.cz/absolutnivitezove/rocnik-2013
(visited on 2015-01-18).
[3] M. Adeel, H . S. Cheung, and S. H. Khiyal. MATH GO! Prototype of a
Content Based Mathematical Formula Search Engine. Journal of Theoretical
and Applied Information Technology, 4(10):1002-1012, 2008.
[4] A. Aizawa, M . Kohlhase, and I. Ounis. NTCIR-10 Math Pilot Task
Overview. In N. Kando and K. Kishida, editors, Proceedings of the 10th
NTCIR Conference on Evaluation of Information Access Technologies, pages
654-661. National Institute of Informatics, 2013.
[5] A. Aizawa, M. Kohlhase, I. Ounis, and M. Schubotz. NTCIR-11 Math-2
Task Overview. In N. Kando and K. Kishida, editors, Proceedings of the 11th
NTCIR Conference on Evaluation of Information Access Technologies, pages
88-98. National Institute of Informatics, 2014.
[6] CICM 2012. Math IR Happening at MIR 2012. http: //cicm- conference.
org/2012/cicm.php?event=mir&menu=happening (visited on 2015-01-18).
[7] C M U Team. Standard Evaluation Package for Information Access
systems (SEPIA), http://cicm-conference.org/2012/cicm.php?event=
mir&menu=happening (visited on 2015-01-18).
[8] Cornell University Library. arXiv.org e-Print archive, http://arxiv.org/
(visited on 2015-01-18).
[9] Cornell University Library. Project Euclid, http://projecteuclid.org
(visited on 2015-01-18).
[10] EuDML. Advanced search, https: //eudml. org/search (visited on 2015-
01-18).
[11] D. Formánek, M. Líška, M. Růžička, and P. Sojka. Normalization of digital
mathematics library content. In J. Davenport, J. Jeuring, C. Lange, and
P. Libbrecht, editors, 24th
OpenMath Workshop, 7 Workshop on Mathematical
User Interfaces (MathUI), and Intelligent Computer Mathematics Work
in Progress, number 921 in CEUR Workshop Proceedings, pages 91-103,
Aachen, 2012.
29
BIBLIOGRAPHY
[12] L. Gao, Y. Wang, L. Hao, and Z. Tang. ICST Math Retrieval System for
NTCIR-11 Math-2 Task. In N . Kando and K. Kishida, editors, Proceedings
of the 11th NTCIR Conference on Evaluation ofInformation Access Technologies,
pages 99-102. National Institute of Informatics, 2014.
[13] R. Hambasan, M. Kohlhase, and C. Prodescu. MathWebSearch at NTCIR-
11. In N . Kando and K. Kishida, editors, Proceedings of the 11th NTCIR
Conference on Evaluation of Information Access Technologies, pages 114-119.
National Institute of Informatics, 2014.
[14] S. Kamali and F. W. Tompa. Retrieving documents with mathematical
content. In Proceedings of the 36th International ACM SIGIR Conference on
Research and Development in Information Retrieval, SIGIR '13, pages 353-362,
New York, NY, USA, 2013. ACM.
[15] M . Kohlhase, B. A. Matican, and C.-C. Prodescu. Mathwebsearch 0.5:
Scaling an open formula search engine. In J. Jeuring, J. A. Campbell,
J. Carette, G. Reis, P. Sojka, M. Wenzel, and V. Sorge, editors, Intelligent
Computer Mathematics, volume 7362 of Lecture Notes in Computer Science,
pages 342-357. Springer Berlin Heidelberg, 2012.
[16] M. Kohlhase and C. Prodescu. MathWebSearch at NTCIR-10. In N. Kando
and K. Kishida, editors, Proceedings of the 10th NTCIR Conference on Evaluation
ofInformation Access Technologies, pages 675-679. National Institute of
Informatics, 2013.
[17] M. Kohlhase and I. Sucan. A Search Engine for Mathematical Formulae. In
Proceedings ofAISC, pages 241-253, Beijing, China, 2006. http: //dx. doi.
org/10.1007/11856290.21.
[18] G. Y. Kristianto, G. Topic, F. Ho, and A. Aizawa. The MCAT Math Retrieval
System for NTCIR-11 Math Track. In N . Kando and K. Kishida, editors,
Proceedings of the 11th NTCIR Conference on Evaluation ofInformation Access
Technologies, pages 120-126. National Institute of Informatics, 2014.
[19] P. Libbrecht and E. Melis. Methods to access and retrieve mathematical
content in activemath. In A. Iglesias and N. Takayama, editors, Mathematical
Software - ICMS 2006, volume 4151 of Lecture Notes in Computer Science,
pages 331-342. Springer Berlin / Heidelberg, 2006.
[20] P. Libbrecht and E. Melis. Semantic Search in LeActiveMath. In
Proceedings of the WebALT 2006 Conference. The WebALT project, Jan. 2006.
http://www.activemath.org/pubs/Libbrecht-etal-SemanticSearch-
WebALT2006.pdf.
30
BIBLIOGRAPHY
[21] A. Lipani, L. Andersson, E Piroi, M. Lupu, and A. Hanbury. TUW-IMP at
the NTCIR-11 Math-2. In N. Kando and K. Kishida, editors, Proceedings of
the 11th NTCIR Conference on Evaluation of Information Access Technologies,
pages 143-146. National Institute of Informatics, 2014.
[22] M. Liška. Vyhledávání v matematickém textu (in Slovak), Searching Mathematical
Texts, 2010. Bachelor Thesis, Masaryk University, Brno, Faculty
of Informatics (advisor: Petr Sojka), https: / / i s .muni . cz/th/255768/f i _
b/?lang=en.
[23] M. Líška. Evaluation of Mathematics Retrieval, Jan. 2013. Master Thesis,
Masaryk University, Brno, Faculty of Informatics (advisor: Petr Sojka),
https://is.muni.cz/th/255768/fi_m/?lang=en.
[24] M. Líška, M. Růžička, and P. Sojka. Math Indexer and Searcher under
the Hood: History and Development of a Winning Strategy. In N. Kando
and K. Kishida, editors, Proceedings of the 11th NTCIR Conference on Evaluation
of Information Access Technologies, pages 127-134. National Institute of
Informatics, 2014.
[25] Mathjax Consortium. Mathjax. http: //www. mathj ax. org/ (visited on
2015-01-18).
[26] B. R. Miller and A. Youssef. Technical aspects of the digital library of
mathematical functions. Annals of Mathematics and Artificial Intelligence,
38:121-136,2003.
[27] B. R. Miller and A. Youssef. Augmenting presentation mathml for
search. In S. Autexier, J. Campbell, J. Rubio, V. Sorge, and F. Suzuki,
Masakazuand Wiedijk, editors, Intelligent Computer Mathematics, volume
5144 of Lecture Notes in Computer Science, pages 536-542. Springer Berlin
Heidelberg, 2008.
[28] R. Miner and R. Munavalli. An approach to mathematical search through
query formulation and data normalization. In M. Kauers, M . Kerber,
R. Miner, and W. Windsteiger, editors, Towards Mechanized Mathematical
Assistants, volume 4573 of Lecture Notes in Computer Science, pages 342-355.
Springer Berlin / Heidelberg, 2007. http://dx.doi.org/10.1007/978-3-540-
73086-6_27.
[29] J. Mišutka. Indexing Mathematical Content Using Full Text Search Engine.
In WDS '08 Proceedings of Contributed Papers: Part I - Mathematics and
Computer Sciences, pages 240-244. Charles University, Prague, Matfyzpress,
2008.
31
BIBLIOGRAPHY
[30] J. Mišutka and L. Galamboš. Extending Full Text Search Engine for Mathematical
Content. In DML 2008: Towards Digital Mathematics Library, pages
55-67. Masaryk University, 2008. http: //dml. cz/dmlcz/702546.
[31] J. Mišutka and L. Galamboš. EgoMath project website, http: //egomath.
proj ekty. ms. mff . cuni . cz (visited on 2015-01-18).
[32] J. Mišutka and L. Galamboš. System description: Egomath2 as a tool for
mathematical searching on wikipedia.org. In Proceedings of the 18th Calculemus
and 10th International Conference on Intelligent Computer Mathematics,
M K M '11, pages 307-309, Berlin, Heidelberg, 2011. Springer-Verlag.
[33] M.-Q. Nghiem, G. Kristianto, G. Topic, and A. Aizawa. Which one is
better: Presentation-based or content-based math search? In S. M . Watt,
J. H. Davenport, A. P. Sexton, P. Sojka, and J. Urban, editors, Intelligent
Computer Mathematics, volume 8543 of Lecture Notes in Computer Science,
pages 200-212. Springer International Publishing, 2014. http: //dx. doi.
org/10.1007/978-3-319-08434-3_15.
[34] N. I. of Standards and Technology. Digital Library of Mathematical Functions,
http: //dlmf . nist. gov/ (visited on 2015-01-18).
[35] N . Pattaniyil and R. Zanibbi. Combining TF-IDF Text Retrieval with
an Inverted Index over Symbol Pairs in Math Expressions: The Tangent
Math Search Engine at NTCIR 2014. In N . Kando and K. Kishida, editors,
Proceedings of the 11th NTCIR Conference on Evaluation of Information Access
Technologies, pages 135-142. National Institute of Informatics, 2014.
[36] J. M . G. Pinto, S. Barthel, and W.-T. Balke. QUALIBETA at the NTCIR-11
Math 2 Task: An Attempt to Query Math Collections. In N . Kando and
K. Kishida, editors, Proceedings of the 11th NTCIR Conference on Evaluation
of Information Access Technologies, pages 103-107. National Institute of
Informatics, 2014.
[37] School of Physics & Astronomy, The University of Edinburgh. Snuggletex.
http://www2.ph.ed.ac.uk/snuggletex/documentation/overviewand-f
eatures .html (visited on 2015-01-18).
[38] M. Schubotz, M. Leich, and V. Markl. Querying Large Collections of Mathematical
Publications: NTCIR10 Math Task. In N. Kando and K. Kishida,
editors, Proceedings of the 10th NTCIR Conference on Evaluation of Information
Access Technologies, pages 667-674. National Institute of Informatics, 2013.
[39] P. Sojka and M . Líška. Indexing and Searching Mathematics in Digital
Libraries - Architecture, Design and Scalability Issues. In J. H. Davenport,
32
BIBLIOGRAPHY
W. M. Farmer, J. Urban, and F. Rabe, editors, Intelligent Computer Mathematics.
Proceedings of18th Symposium, Calculemus 2011, and 10th International
Conference, MKM 2011, volume 6824 of Lecture Notes in Artificial Intelligence,
LNAI, pages 228-243, Berlin, Germany, July 2011. Springer-Verlag.
http://dx.doi.org/10.1007/978-3-642-22673-1_16.
[40] Springer. LaTeXSearch: About, http://www.latexsearch.com/static/
about.j sp.
[41] H. Stamerjohanns, M. Kohlhase, D. Ginev, C. David, and B. Miller. Transforming
Large Collections of Scientific Publications to XML. Mathematics in
Computer Science, 3:299-307, 2010. http: //dx. doi. org/10.1007/sl 1786-
010-0024-7.
[42] W. Sylwestrzak, J. Borbinha, T. Bouche, A. Nowiriski, and P. Sojka.
EuDML—Towards the European Digital Mathematics Library. In P. Sojka,
editor, Proceedings of DML 2010, pages 11-24, Paris, France, July 2010.
Masaryk University, http: //dml. cz/dmlcz/702569.
[43] The Apache Software Foundation. Apache Lucene. http://lucene.
apache. org/core/ (visited on 2015-01-18).
[44] G. Topic, G. Y. Kristianto, M.-Q. Nghiem, and A. Aizawa. The MCAT Math
Retrieval System for NTCIR-10 Math Track. In N. Kando and K. Kishida,
editors, Proceedings of the 10th NTCIR Conference on Evaluation of Information
Access Technologies, pages 680-685. National Institute of Informatics, 2013.
[45] K. D. V. Wangari, R. Zanibbi, and A. Agarwal. Discovering real-world
use cases for a multimodal math search interface. In Proceedings of the
37th International ACM SIGIR Conference on Research & Development in
Information Retrieval, SIGIR '14, pages 947-950, New York, NY, USA, 2014.
ACM. http: //doi. acm. org/10.1145/2600428.2609481.
[46] A. Youssef. Methods of relevance ranking and hit-content generation in
math search. In M . Kauers, M . Kerber, R. Miner, and W. Windsteiger,
editors, Towards Mechanized Mathematical Assistants, volume 4573 of Lecture
Notes in Computer Science, pages 393-406. Springer Berlin / Heidelberg,
2007. http://dx.doi.org/10.1007/978-3-540-73086-6.31.
[47] Q. Zhang and A. Youssef. An approach to math-similarity search. In
S. M . Watt, J. H. Davenport, A. P. Sexton, P. Sojka, and J. Urban, editors,
Proceedings of Intelligent Computer Mathematics, CICM 2014, volume 8543
of Lecture Notes in Computer Science, pages 404^118. Springer International
Publishing, 2014. http: //dx. doi. org/10.1007/978-3-319-08434-3.29.
33
A Publications
The list of attached publications can be found in Section 4.1. The full list of
my publications can be found at https: / / i s .muni. cz/osoba/martin. liski#
publikace.
34
Indexing and Searching Mathematics
in Digital Libraries
Architecture, Design and Scalability Issues
Petr Sojka, Martin Líška
Masaryk University, Faculty of Informatics, Botanická 68a, 602 00 Brno, Czech Republic
sojka@fi.muni.cz, 255768@mail.muni.cz
Abstract. This paper surveys approaches and systems for searching mathematical
formulae in mathematical corpora and on the web. The design and architecture
of our MlaS (Math Indexer and Searcher) system is presented, and our design
decisions are discussed in detail. An approach based on Presentation MathML
using a similarity of math subformulae is suggested and verified by implementing
it as a math-aware search engine based on the state-of-the-art system, Apache
Lucene.
Scalability issues were checked based on 324,000 real scientific documents from
arXiv archive with 112 million mathematical formulae. More than two billions
MathML subformulae were indexed using our Solr-compatible Lucene extension.
Keywords: math indexing and retrieval, mathematical digital libraries, information
systems, information retrieval, mathematical content search, document
ranking of mathematical papers, math text mining, MlaS, WebMIaS
1 Introduction
I do not seek. I find.
Pablo Picasso
The solution to the problem of mathematical formulae retrieval lies at the heart of
building digital mathematical libraries (DML). There have been numerous attempts to
solve this problem, but none have found widespread adoption and satisfaction within the
wider mathematics community. A n d as yet, there is no widely accepted agreement on
the math search format to be used for mathematical formulae by library systems or by
Google Scholar.
M a t h M L standard by W 3 C has become the standard for mathematics exchange
between software tools. Almost no MathML is written directly by authors—they typically
prefer a compact notation of some TgX flavour such as LTgX or Jlj\^-W^i. The
designer of a search system for mathematics is thus faced with the task of converting data
to a unifying format, and allowing D M L users to use their prefered notation when posing
queries. [,?lyv4S]LTpX or other TpX flavour are the typical preferences; Presentation
M a t h M L or Content M a t h M L are used only when available as outputs of a software
system.
During the integration of existing D M L s into larger projects such as E u D M L [15],
the unsolved math search problem becomes evident—DML without math search support
J.H. Davenport et al. (Eds.): Calculemus/MKM 2011, LNA I 6824, pp. 228-243, 2011.
© Springer-Verlag Berlin Heidelberg 2011
Indexing and Searching Mathematics in Digital Libraries 229
is an oxymoron. As our subject matter search has not lead to a satisfactory solution, we
have designed and implemented [7] new robust solutions for retrieval of mathematical
formulae.
Section 2 explores published facts about research done in the area of mathematics
retrieval. Pros and cons of existing approaches are outlined, most of them being neither
applicable nor satisfactory for digital library deployment. In Section 3 we present our
design of scalable and extensible system for searching mathematics, taking into account
not only inherent structure of mathematical formulae but also formula unification and
subformulae similarity measures. Our evaluation of prototypical implementation above
the Apache Lucene open source full-featured search engine library is presented in
Section 4. The paper closes listing future work directions in Section 5 and a conclusion
is summarised in Section 6.
Computers are useless. They can only give you answers.
Pablo Picasso
2 Approaches to Searching Mathematics
A great deal of research on has been already undertaken on searching mathematical
formulae in digital libraries and on the web. Several such Mathematical Search Engines
(MSE) have been designed in the past: MathDex, EgoMath, LTE XSearch, LeActiveMath
or MathWebSearch. In this section, we will briefly comment on each of these.
MathDex1
(formerly MathFind [9]) is a result of a NSF-funded project headed by
Robert Miner of Design Science2
. It encodes mathematics as text tokens, and uses
Apache Lucene as if searching for text. Using similarity with search terms, ranked results
are produced by the search algorithm, matching n-grams of presentation MathML. The
creators of MathDex report that most of the work was due to a necessary and extensive
normalization of MathML—because of the fact that it uses several converters and
filters to convert to X H T M L + M a t h M L — H T M L (jtidy), T E X / E T E X (blahtex, D T E X M L ,
Hermes), Word (Word+MathType), P D F (pdf2tiff+Infty). The algorithm of n-gram
ranking has several drawbacks. For one thing, it cannot take many kinds of elementary
mathematical equivalences into account, and it puts undue weight on variable names.
Contrary to its intentions, MathDex has not become a sustainable service to the
mathematical community, although it has fueled research in the area of mathematics
searching [16,17,1],
EgoMath? is being developed by Josef Misutka as an extension of a full text websearch
core engine Egothor (by Leo Galambos, M F F U K Prague) [8] licenced under G P L . It
uses presentation M a t h M L for indexing and develops generalization algorithms and
relevancy calculation to cope with normalization. A s part of EgoThor evaluation, an
M S E evaluation dataset is also being developed.4
1
www.mathdex.com/ 2
www.ima.umn.edu/2006-2007/SW12.8-9.06/activities/Miner-Robert/index.html
3
egomath.projekty.ms.mff.cuni.cz/egomath/ 4
egomath.cythres.cz/dataset.py
230 Petr Sojka, Martin Liška
EtTjjXSearch5
is a search tool offered by Springer in SpringerLink. It searches directly
in the Tr-X math string representations as provided by the authors of papers submitted to
Springer in ffljgX sources. Some kind of text similarity matching is probably used. Since
it is not open source, one can only guess the strategy for posing queries. Our experiments
typically lead to a very low precision. Neither is there any definition of the article dataset
available.
LeActiveMath6
search has been developed as part of the ActiveMath-EU project. It
is Lucene based, indexing string tokens from O M D o c with an OpenMath semantic
notation. The document database format is internal since only documents authored for
LeActiveMath learning environments are indexed.
MathWebSearch1
is an M S E developed in Bremen/Saarbriicken by Kohlhase et al. [2]
It is not based on full text searching, rather it adopts a semantic approach: it uses substitution
trees in memory. Both presentation and content M a t h M L is supported, together
with OpenMath. It is exceptional in the fact that it primarily deals with semantics and
uses its own engine, not being built on the Lucene engine, for math. Further development
is now being pursued under LaMaPun architecture [6].
The comparison of math search systems is summarized in Table 1. A l l of the MSEs
reviewed had some drawbacks regarding their employment in a digital mathematical
library such as E u D M L . This was our main motivation for designing a new one, primarily
for the use in large scale libraries, such as E u D M L or ArXiv.
Everything you can imagine is real.
3 Design of MlaS P a b l
° p i c a s s o
We have developed a math-aware, full-text based search engine called MlaS (Math
Indexer and Searcher). It processes documents containing mathematical notation in
MathML format. MlaS allows users to search for mathematical formulae as well as the
textual content of documents.
Since mathematical expressions are highly structured and have no canonical form,
our system pre-processes formulae in several steps to facilitate a greater possibility of
matching two equal expressions with different notation and/or non-equal, but similar
formulae. With an analogy to natural language searching, MlaS searches not only for
whole sentences (whole formulae), but also for single words and phrases (subformulae
down to single variables, symbols, constants, etc.). For calculating the relevance of the
matched expressions to the user's query, MlaS uses a heuristic weighting of indexed
terms, which accordingly affects scores of matched documents and thus the order of
results.
3.1 System Workflow
The top-level indexing scheme is shown in Figure 1 on page 232. A detailed view of the
mathematical part is shown in Figure 2 on page 233.
5
www.latexsearch.com/ 6
devdemo.activemath.org/ActiveMath2/ 7
search.mathweb.org/index.xhtml
Table 1: Comparison of math search systems
System Input documents Internal representation Approach a-
eq.
Query language Queries Indexing
core
MathDex HTML, TpX/LTrÄ, Word,
PDF
Presentation MathML (as
strings)
syntactic X 7 text, math,
mixed
Apache
Lucene
LeActiveMath OMDoc, OpenMath OpenMath (as string) syntactic X OpenMath (palette editor) text, math,
mixed
Apache
Lucene
LTpXSearch LTpX LTpX (as string) syntactic X LTpX titles, math,
DOI
?
MathWeb Search Presentation MathML, Content
MathML, OpenMath
Content MathML, OpenMath
(substitution trees)
semantic • QMath, LTpX,
Mathematica, Maxima,
Maple, Yacas styles (palette
editor)
text, math,
mixed
Apache
Lucene (for
text only)
EgoMath Presentation MathML,
Content MathML, PDF
Presentation MathML trees
(as strings)
mixed X LTpX text, math,
mixed
EgoThor
MlaS any (well-formed) MathML Canonical Presentation
MathML trees (as compacted
strings)
math tree
similarity/
normalization
• J%(S-MEX or MathML text, math,
mixed
Apache
Lucene/Solr
232 Petr Sojka, Martin Liška
input
canonized
document
document
handler
input
canonized
document
document
handler
indexing
T "I
searching
Fig. 1: Scheme of the system workflow
3.2 Indexing
MlaS is currently able to index documents in X H T M L , H T M L and T X T formats. As
Figure 1 shows, the input document is first split into textual and mathematical parts. The
textual content is indexed in a conventional way.
Mathematical expressions, on the other hand, are pre-analyzed in several steps to
facilitate searches not only for exact whole formulae, but also for subparts (tokenization)
and for similar expressions (formulae modifications). This addresses the issue of the
static character of full-text search engines and creates several representations of each
input formula all of which are indexed. Each indexed mathematical expression has a
weight (relevancy score) assigned to it. It is computed throughout the whole indexing
phase by individual processing steps following this basic rule of thumb—the more
modified a formula and the lower the level of a subformula, the less weight is assigned
to it.
At the end of all processing methods, formulae are converted from X M L nodes to a
compacted linear string form, which can be handled by the indexing core. Start and end
X M L tags are substituted by the tag name followed by an argument embraced by opening
and closing parentheses. This creates abbreviated but still unambiguous representation
of each X M L node. For example, formula a + b2
, in MathML written as:
Indexing and Searching Mathematics in Digital Libraries 233
<math xmlns="http://www.w3.org/1998/Math/MathML">
<mrow>
<mi>a</mi>
<mo>+</mo>
<msup> <mi>b</mi><mn>2</mnx/msup>
</mrow>
</math>
is converted to "math(mrow(mi(a)mo(+)msup(mi(b)mn(2))))" and this string is
then indexed by Lucene.
3.3 Tokenization
Tokenization is a straightforward process of obtaining subformulae from an input formula.
MlaS makes use of Presentation MathML markup where all logical units are enclosed
in X M L tags which makes obtaining all subformulae a question of tree traversal. The
inner representation of each formula is an X M L node encapsulating all the member
child nodes. This means the highest level formula—as it appears in the input document—
is represented by a node named "math". A l l logical subparts of an input formula are
obtained and passed on to modification algorithms.
234 Petr Sojka, Martin Liška
3.4 Formulae Modifications
MlaS performs three types of unification algorithms, the goal of which is to create
several more or less generalized representations of all formulae obtained through the
tokenization process. These steps allow the system to return similar matches to the user
query while preserving the formula structure and a-equality.
3.5 Ordering
Let us take a simple example: a+3 and the query 3 +a. This would not match even though
it is perfectly equal. This is why a simple ordering of the operands of the commutative
operations, addition and multiplication, is used. It tries to order arguments of these
operations in the alphabetical order of the X M L nodes denoting the operands whenever
possible—it considers the priority of other relevant operators in the formula. The system
applies this function to the formula being indexed as well as to the query expression.
Applied to the example above, the X M L node denoting variable a is named "mi", the
node denoting number 3 is named "mn". "mi"<"mn" therefore 3 + a would be exchanged
for a + 3 and would match.
3.6 Unification of Variables
Let us take another example: a + ba
and x+yx
. Again, these would not match even though
the difference is only in the variables used. MlaS employs a process that unifies variables
in expressions while taking bound variables into account. A l l variables are substituted for
unified symbols (ids) in both the indexing and searching phases. Applied to the example,
both expressions would unify to idi + idf1
and would match. This process is not applied
to single symbols—this would lead to the indexing of millions of ids and searching for
any symbol would end up matching all of the documents containing it.
3.7 Unification of Constants
This is a strightforward process of substituting all the numerical constants for one unified
symbol (const). This obviates the need for the exact values of constants in user queries.
In some situations however, this can be too much of a generalization. A s well as in
the case of the variables, stand-alone numerical constants are not unified for the same
obvious reason.
3.8 Formulae Weighting
During the searching phase, a query can match several terms in the index. However one
match can be more important to the query than another, and the system must consider
this information when scoring matched documents. For mathematical formulae the
system makes use of the processing operations described above since they all produce
expressions more generalized than the input ones.
It is impossible to assemble a weighting function that is exactly right. Such a function
should consider a document base on which the system will run as well as the established
Indexing and Searching Mathematics in Digital Libraries 235
customs in a particular scientific field. We tried to create a complex and robust weighting
function that would be appropriate to many fields.
The original unchanged untokenized formula should of course have the greatest
weight, but the precision of the ordered representation is not compromised at all, so it
should have the same weight. In fact, if the ordering process changes the order of some
members in an expression, the original formula is not indexed at all. The starting weight
for such a representation is 1.
The tokenization process should naturally lower the weight of the subformulae since
they are deeper in the structure and therefore less important to the overall formula. When
a user who is searching for a + b finds two documents, the first containing a + b and the
second containing the first should score more and appear higher in the results, as
it matches in higher level of M a t h M L expression tree. Hence the tokenization process
reduces the weight of the subformulae according to the level coefficient / < 1.
Both unification algorithms produce representations that are more generalized than
their input expressions. They have a higher probability of matching, and should therefore
score less. The unification of variables alters the weight of the result formula by
coefficient v < 1, unification of number constants uses coefficient c < 1.
Theoretically, two equally unified subformulae matched on the same level of differently
complex parent formulae would have the same score. For example
a + b3+a
and
J 25b2
db
o d — e
- + + WOab
3 + a b
with the query 3 + a. Both matches are not unified, and both are found on the third level.
Analogously to conventional full-text engines which discriminate documents with more
tokens than others, we use information about the complexity of parent formulae. More
specifically, an initial weight of 1 is multiplied by the inverse number of nodes of a
whole parent expression.
According to this model, each formula has a weight attribute indexed alongside itself,
which belongs to the interval (0,1). Weight w of the subformula contained on a certain
level in a parent formula with the number of nodes («) can be calculated in particular
situations as follows:
- no changes made: w = , k , d ( 1 + v + c + v c )
- unified variables: w = -—
n
flcvcl/ , \
- unified constants: w = -—y±1
^d
n
/level
- unified both variables and constants: w = —— .
n
See Section 3.9 for details.
To fine tune the weighting parameters, we developed a tool with verbose output in
which the behavior of the model can be observed and tested. A sample from the tool
mentioned above is shown in Table 2 on page 237.
236 Petr Sojka, Martin Liška
input:
arranged:
variables
unification:
constants
unification:
(a, 0.0875) / ' / ( + • 0.0875) (b'*2
, 0.0875)
lb, 0.06125
(c, 0.042875) / ', \ (2,0.042875)
(+, 0.04287,5)
/ (id,+id?, + 2
,0.1) / (rdf'+ 2
,0.07) (ii/, + 2,0.0343)
a + r; , 0.0625) (fec+OT
", 0.04375)
(c + coníí, 0.030625)',
(íd1 +ídj, +
™~',0.05) (ídf"+ O T
", 0.035) (í'í^ + co/wf, 0.01715)
Fig. 3: Example of formula preprocessing. Ordered pairs are (<expression written naturally;*,
<it's weight>). A l l expressions as shown are indexed, except for the original
one.
We have come to the conclusion that the unification of variables interferes less with
original formula meaning than the unification of number constants. For this reason, its
coefficient should be higher—i.e., less discriminating. The main question then became,
how discriminating the level coefficient should be. Our empirical deduction is that going
deeper in a structural tree should be discriminating, the precise match on a lower level
should still score more than any unified formula on the level above, as could be seen in
Table 2: (row 5) is an exact match on the second level and its score is higher than
unified expressions matched on the first level (rows 2, 3 and 4).
This led us to the valuation of level weighting coefficient / = 0.7, unification
weighting coefficient v = 0.8 and constant weighting coefficient c = 0.5.
In Figure 3 the whole formula preprocessing process is illustrated together with its
subformulae weightings.
3.9 Searching
In the search phase, user input is again split into mathematical and textual parts. Formulae
are then reprocessed in the same way as in the indexing phase, except for tokenization—
which we doubt that users are likely to query, for example — wanting to find documents
only with occurrences of variable c. That means the queried expressions are first ordered,
then unified. This produces several representations which are connected to the final query
by the logical O R operator.
Textual query terms are connected to the final query by the logical A N D operator.
Therefore by specifying a text term we can narrow down the results, because each
Indexing and Searching Mathematics in Digital Libraries 237
Table 2: Example of weighting function on several formulae. Original query is a+3—all
queried expressions are a + 3, idi + 3, a + const, idi + const.
Formula Indexed Expressions Score Matched
a + 3
0.25=[a + 3], 0.2=[idi + 3], 0.175=[a, 3, +],
0.125=[a + const], 0.1=[idi + const]
2.7
0.1 [idi + const] + 0.25 [a + 3] +
0.2[idi + 3] + 0.125[a + const]
b + 3
0.25=[b + 3], 0.2=[id! + 3], 0.175=[6, +, 3],
0.125=[£ + const], 0.1=[idi + const]
1.2 0.1 [idi + const] + 0.2[idi + 3]
a + 5
0.25=[a + 5], 0.2=[idi + 5], 0.175=[a, +, 5],
0.125=[a + const], 0.1=[idi + const]
0.9 0.1 [idi + const] + 0.125[a + const]
c + 10
0.25=[c + 10], 0.2=[idi + 10],
0.175=[c, +, 10], 0.125=[c + const],
0.1=[idi + const]
0.4 0.1 [idi + const]
l
a+3
0.16667=[^3],0.13334=[;5iT3],
0.11667=[l,a + 3], 0.09334=[idi + 3],
° - 0 8 3 3 4
= [ ^ = ] ' 0.08167=[+,3,a],
0.06667=[^ai!_], 0.05833=[a + const],
L
idi +const -" L J
'
0.04667=[id, + const]
1.26
0.04667[idi + const] + 0.11667[a +
3] + 0.09334[idi + 3] + 0.05833[a +
const]
1
b+3
0.16667=[^],0.13334=[-^],
0.11667=[fe + 3,1], 0.09334=[idi + 3],
0.08334=[^^1;], 0.08167=[6, 3, +],
0.06667=[I S ^^], 0.05833=[fe + const],
0.04667=[id! + const]
0.56
0.04667[idi + const] + 0.09334[idi +
3]
1
a+5
0.16667=[^-], 0.13334=[,/-],
L
o+5J
' L
idi+5J
'
0.11667=[l,a + 5], 0.09334=[idi + 5],
0 . 0 8 3 3 4 = 0 . 0 8 1 6 7 = [ a , 5, +],
0.06667=[^sss!_;], 0.05833=[a + const],
L
ldj +const -" L J
'
0.04667=[idi + const]
0.42
0.04667[idi + const] + 0.05833[a +
const]
1
c+10
0.16667=[^],0.13334=[^],
0.11667=[l,c+ 10],0.09334=[idi + 10],
0 . 0 8 3 3 4 = [ ^ ] , 0.08167=[+, c, 10],
0.06667=[^sss!_;], 0.05833=[c + const],
L
ldj +const -" L J
'
0.04667=[idi + const]
0.19 0.04667 [idi + const]
returned document must have the term contained. When more than one text term is
specified, they are implicitly connected to the text query by the OR operator which means
at least one term should occur in the result. We can also explicitly state preferences about
each text term—whether it needs to occur in the result or not.
As stated above, the final query, without having explicitly stated occurrences of text
terms, is in the logical form of (formulai V . . . V formula,,) A (termi V . . . V termn ).
In order to counterbalance the weight of the textual and mathematical parts of the
query, the score of the matched formulae are additionally multiplied by number of nodes
the matching query consists of. This results in more complex mathematical queries
scoring more.
238 Petr Sojka, Martin Liška
A very positive value has its price in negative terms... the genius of Einstein leads to Hiroshima.
Pablo Picasso
4 Evaluation
For large scale evaluation, we needed an experimental implementation and a corpus of
mathematical texts.
4.1 Implementation
The Math Indexer and Searcher is written in Java. The role of full-text indexing and
searching core is performed by Apache Lucene 3.1.0. The mathematical part of document
processing can be seen as a standalone pluggable extension to any full-text library,
however it would need custom integration for each one. In the case of Lucene, a custom
Tokenizer (MathTokenizer) has been implemented.
For the textual content of documents, Lucene's StandardAnalyzer is employed. In
MathTokenizer, TermAttributes are used for carrying strings of math expressions and
PayloadAttribute for storing weights of formulae.
The question now is, how should the weights of formulae be taken into consideration
in the overall score of matched documents. Lucene's practical scoring function for every
hit document d by query q with each query term t is as follows:
score(q,d) = coordjq, d)-queryNorm(q)-^ (tf(t md) • idf(t)2
• t.getBoostQ • norm(t,df)
t ill q
It is described in detail at h t t p : / / l u c e n e . a p a c h e . o r g / j a v a / 3 _ l _ 0 / a p i / c o r e /
i n d e x . h t m l ? o r g / a p a c h e / l u c e n e / s e a r c h / S i m i l a r i t y . h t m l .
When searching for mathematical formulae, their weights need to be considered
in the final score of the document. The resulting MlaS scoring function adds another
parameter to the basic function—weight w of one matched formula:
score(q, d) = coord(q, d) • queryNorm{q) •
• ^ (//'(find) • avg{w) • idf(t)2
• t.getBoostQ • norm(t, <i)) (1)
t ill q
If a document contains the same formula more than once (each occurrence can have
different weight assigned), the average value of all the weights is taken into consideration
(avg(w)).
Let's take a simplified version of the function (1). Specifically, let us not to consider
normalization factor queryNorm(q), inverse document frequency idf(t)2
and document/
field boost and length factor norm(t, d):
score(q, d) = coord(q, d) • ^ (tf(t in d) • avg(w) • t.getBoostQ) (2)
t ill q
and follow the example in Table 2 on the previous page. Let's consider we query a
document containing only two formulae b + 3 and (rows 2 and 5). During indexing
Indexing and Searching Mathematics in Digital Libraries 239
time, preprocessing creates several more representations, all of which are indexed (shown
in the second column). The query is a + 3 which is expanded by query preprocessing to
the final query that takes the form of a + 3 V idi + 3 V a + const V idi + const. Column 4
shows which actual expressions will match the query for each particular input formula.
coord(q, d) will be | because all four of the four query terms found a match. Query terms
a + 3 matched only one indexed term and its weight is 0.11667; query term a + const also
matched only one indexed term and its weight 0.05833; query term idi + 3 matched two
indexed terms with weights 0.2 and 0.09334 so its average is 0.14667; finally the last
query term idi + const matched two indexed expressions with weights 0.1 and 0.04667
so its average is 0.07335. t.getBoostQ is a query time boosting factor and as stated in
Section 3.9, we use the number of X M L nodes of the original query formula—in this
example it is 4. The resulting score of the whole document is then
- • ((1 • 0.11667 • 4) + (1 • 0.05833 • 4) + (2? • 0.14667 • 4) + (2? • 0.07335 • 4))
4.2 Corpus of Mathematical Documents MREC
A document corpus M R E C with 324,060 scientific documents (version 2011.3.324) was
initially used to evaluate the behaviour of the system we modelled. The documents come
from the arXMLiv project that is converting document sets from arXiv into X H T M L +
M a t h M L (both Content and Presentation) [13]. At the time of testing, our system was
not yet able to process mixed MathML markup so preprocessing in the sense of filtering
out unwanted markup was needed. The resulting corpus size was 53 G B uncompressed,
6.7 G B compressed. Documents contained 112,055,559 formulae in total, of which
2,129,261,646 mathematical expressions were indexed. The resulting index size was
approx. 45 G B .
We were able to gather even greater amount of documents in M R E C corpus version
2011.4.439 to test our indexing system. This corpus consists of 439,423 arXMLiv
documents containing 158,106,118 mathematical formulae. 2,910,314,146 expressions
were indexed and the resulting size of the index is 63 G B . Sizes of uncompressed and
compressed corpora size are 124 G B and 15 G B , respectively.
Mentioned M R E C corpora are available to the community for download from M R E C
web page h t t p : / / n i p . f i . muni. c z / p r o j ekty/eudml/MREC/ so that other math indexing
engines could be compared with MlaS on the same data.
4.3 Results
Math Indexer and Searcher demonstrated the ability to index and search a relatively
vast corpus of real scientific documents. Its usability is highly elevated thanks to its
preprocessing functions together with formulae weighting model. The ability to search
for exact and similar formulae and subformulae, more so with customizable relevancy
computation, demonstrates an unquestionable contribution to the whole search experi-
ence.
It is very difficult, i f not impossible, to completely verify the correctness of the
theoretical considerations made in the previous sections and thus correctness of search
240 Petr Sojka, Martin Liška
Table 3: Scalability test results (run on 32 G B R A M , quad core A M D Opteron
Processor 850 driven machine).
Documents Input formulae Indexed formulae Indexing time [min] Average query time [ms]
10,000 3,450,114 65,194,737 39.15 32
50,000 17,734,342 334,078,835 201.68 178
200,000 70,102,960 1,316,603,055 889.28 576
324,060 112,055,559 2,129,261,646 1,292.16 789
results. For this purpose, a sufficiently large corpus of documents with fully controlled
content would be needed. For any assembled query, there should exist beforehand a
complete list of the documents ordered by their relevance to the query to compare the
actual results to.
We have applied an empirical approach to the evaluation so far. For these purposes
we have created a demo web interface WebMIaS which is publicly available on the
MlaS web page h t t p : / / n i p . f i .muni. c z / p r o j e k t y / e u d m l / m i a s / . It works over
M R E C corpora discussed in the Section 4.2 Additionally, for the latest M R E C corpus
we have implemented and added demanded snippet generation and mathematical match
highlighting in hit list. Preliminary version of this functionality is available.
Our WebMIaS interface supports queries in two different notations—in jy^-UfFpK
and M a t h M L . Mathematical queries are additionally canonized using X S L T transformations
from U M C L library [4,3] to improve the query and to avoid notation flaws
restraining proper results retrieval. Portability of the interface is increased by using
MathJax for rendering of mathematical formulae in snippets.
4.4 Scalability Testing and Efficiency
We have devised a scalability test to see how the system behaves with an increasing
number of documents and formulae indexed. Subsets containing 10,000, 50,000,200,000
and the complete 324,060 documents were gradually indexed and several values were
measured: the number of input formulae, the number of indexed formulae, the indexing
time and the average query time.
The number of input formulae indicate how rich a particular subset was in formulae;
the number of indexed formulae should illustrate their complexity. Moreover both should
indicate whether indexing and query time are dependent on the number of documents
or specially on the formulae they contain. For measuring the average query time, we
queried each created index with the same set of differently complex queries (mixed,
non-mixed, more/less complex single/multiple formulae) computing the average time.
The results are shown in Table 3 and in the form of diagrams in Figure 4 on the next
page.
M R E C version 2011.4.439 was indexed using improved and optimised algorithms
and ran on a different machine. Therefore it cannot be compared to measured values
shown in tables 3 and 4 on the next page. Indexing time of this corpus was 1378.82 ms,
e.g. almost 23 hours.
Indexing and Searching Mathematics in Digital Libraries 241
Inputformijlas [K] hput formulae [K|
(a) Number of input formulae vs. indexing (b) Number of input formulae vs. query time
time
0 5DOC0 100000 150000 200000 250000 3C0000 350000
Hoc J no 1 ts
(c) Number of documents vs. query time (d) Number of formulae vs. number of docu-
ments
Fig. 4: Scalability diagrams
He can who thinks he can, and he can't who thinks he can't.
This is an inexorable, indisputable law.
Pablo Picasso
5 Open Issues, Future Work
We are now awaiting heterogeneous MathML data collected by the E u D M L project, that
has been generated from born-digital [metajdata [10], from born-digital PDFs [5] or
from math O C R [14].
It is evident that some kind of normalization of M a t h M L will be a necessity. We
have opted for Canonical MathML [4,3] as normalization MathML format and are using
software library U M C L supporting it. Our latest experiments with canonical form of
M a t h M L generated by U M C L shows that it not only increases fairness of similarity
ranking, but also helps to match a query against the indexed form of MathML. We are
also working hard on snippets generation and on matched formulae visualization.
Another area of long-term research planned is supporting Content MathML, in a
way similar to the current handling of Presentation MathML. The architectural design is
open to it, but as most of math within E u D M L will be in Presentation M a t h M L taken
from PDFs, this is not currently a high priority.
242 Petr Sojka, Martin Liška
I am always doing that which I can not do, in order that I may learn how to do it.
, _ , Pablo Picasso
6 Conclusions
We have presented an approach to mathematics searching and indexing—the architecture
and design of the MlaS system. The feasibility of our approach has been verified on large
corpora of real mathematical papers from arXMLiv. Scalability tests have confirmed that
the computing power needed for fine math similarity computations is readily available;
this would allow the use of this technology for projects on a European or world-wide
scale.
Acknowledgements. This work has been in part financed by the European Union
through its Competitiveness and Innovation Programme (Information and Communications
Technologies Policy Support Programme, "Open access to scientific information",
Grant Agreement no. 250,503). We thank anonymous reviewers for their improvement
and future work suggestions, Michal Růžička for help with figure drawings and web
form of MlaS interface, and Peter Mravec for collecting M R E C
References
1. Moody Altamimi and Abdou S. Youssef. A Math Query Language with an Expanded Set of
Wildcards. Mathematics in Computer Science, 2:305-331, 2008. http://dx.doi.org/10.
1887/sl1786-888-8856-4.
2. §tefan Anca. Natural Language and Mathematics Processing for Applicable Theorem Search.
Master's thesis, August 2009. https://svn.eecs.jacobs-university.de/svn/eecs/
archive/msc-2889/aanca.pdf.
3. Dominique Archambault, Frederic Berger, and Victor Moco. Overview of the universal maths
conversion library. In Alain Pruski and Harry Knops, editors, Assistive Technology : From
Virtuality to Reality: Proceedings of the AAATE'05 Conference.
4. Dominique Archambault and Victor Moco. Canonical MathML to Simplify Conversion
of MathML to Braille Mathematical Notations. In Klaus Miesenberger, Joachim Klaus,
Wolfgang Zagler, and Arthur Karshmer, editors, Computers Helping People with Special
Needs, volume 4061 of Lecture Notes in Computer Science, pages 1191-1198. Springer Berlin
/Heidelberg, 2006. http://dx.doi.org/18.1887/11788713_172.
5. Josef B. Baker, Alan P. Sexton, and Volker Sorge. Extracting Precise Data on the Mathematical
Content of PDF Documents. In Sojka [11], pages 75-79. http: //dmi. cz/handle/18338.
dmlcz/782535.
6. Mihai Grigore, Magdalena Wolska, and Michael Kohlhase. Towards context-based disambiguation
of mathematical expressions. Math-for-Industry Lecture Note Series, 22:262-271,
December 2009.
7. Martin Liška. Vyhledávání v matematickém textu (in Slovak), Searching Mathematical Texts,
2010. Bachelor Thesis , h t t p s : / / i s .muni. cz/th/255768/fi_b/?lang=en.
8. Jozef Mišutka and Leo Galamboš. Extending Full Text Search Engine for Mathematical
Content. In Sojka [11], pages 55-67. http://dml.cz/dmlcz/782546.
9. Rajesh Munavalli and Robert Miner. MathFind: A Math-Aware Search Engine. In Proceedings
of the 29th annual international ACM SIGIR conference on Research and development
in information retrieval, SIGIR '06, pages 735-735, New York, NY, USA, 2006. ACM.
http://doi.acm.org/18.1145/1148178.1148348.
Indexing and Searching Mathematics in Digital Libraries 243
10. Michal Růžička and Petr Sojka. Data Enhancements in a Digital Mathematics Library. In
Sojka [12], pages 69-76. http: //dmi. cz/dmlcz/702575.
11. Petr Sojka, editor. Towards a Digital Mathematics Library, Birmingham, UK, July 2008.
Masaryk University, http: //www. f i .muni. cz/~sojka/dml-2008-program.xhtml.
12. Petr Sojka, editor. Towards a Digital Mathematics Library, Paris, France, July 2010. Masaryk
University, http: //www. f i .muni. cz/~sojka/dml-2010-program.html.
13. Heinrich Stamerjohanns, Michael Kohlhase, Deyan Ginev, Catalin David, and Bruce Miller.
Transforming Large Collections of Scientific Publications to XML. Mathematics in Computer
Science, 3:299-307, 2010. h t t p : / / d x . d o i .org/10.1007/sll786-010-0024-7.
14. Masakazu Suzuki, Fumikazu Tamari, Ryoji Fukuda, Seiichi Uchida, and Toshihiro Kanahori.
INFTY — An integrated OCR system for mathematical documents. In C. Vanoirbeek,
C. Roisin, and E. Munson, editors, Proceedings ofACM Symposium on Document Engineering
2003, pages 95-104, Grenoble, France, 2003. ACM.
15. Wojtek Sylwestrzak, José Borbinha, Thierry Bouche, Aleksander Nowiňski, and Petr Sojka.
EuDML—Towards the European Digital Mathematics Library. In Sojka [12], pages 11-24.
http://dmi.cz/dmlcz/702569.
16. Abdou S. Youssef. Roles of Math Search in Mathematics. In Jonathan Borwein and William
Farmer, editors, The 5th International Conference on Mathematical Knowledge Management,
volume 4108 of Lecture Notes in Computer Science, pages 2-16. Springer-Verlag, August
2006. http://dx.doi.org/10.1007/11812289_2.
17. Abdou S. Youssef. Methods of Relevance Ranking and Hit-Content Generation in Math
Search. In Manuel Kauers, Manfred Kerber, Robert Miner, and Wolfganag Windsteiger,
editors, Towards Mechanized Mathematical Assistants. Proceedings of 6th International
Conference, MKM 2007, volume 4573 of Lecture Notes in Computer Science, pages 393^-06,
Berlin, Germany, June 2007. Springer-Verlag.
The Art of Mathematics Retrieval
Petr Sojka
Faculty of Informatics, Masaryk University
Botanická 68a, 602 00 Brno, Czech Republic
sojka@fi.muni.cz
Martin Líška
Faculty of Informatics, Masaryk University
Botanická 68a, 602 00 Brno, Czech Republic
255768@mail.muni.cz
ABSTRACT
The design and architecture of MlaS (Math Indexer and Searcher), a
system for mathematics retrieval is presented, and design decisions
are discussed. We argue for an approach based on Presentation
MathML using a similarity of math subformulae. The system was
implemented as a math-aware search engine based on the state-ofthe-art
system Apache Lucene.
Scalability issues were checked against more than 400,000 arXiv
documents with 158 million mathematical formulae. Almost three
billion MathML subformulae were indexed using a Solr-compatible
Lucene.
Categories and Subject Descriptors
H.3.7 [Information Systems]: Information storage and Retrieval—
Information Search and Retrieval; 1.7 [Computing Methodologies]:
Document and text Processing—Index Generation
General Terms
Algorithms, Design, Experimentation, Performance
Keywords
MlaS, WebMIaS, digital mathematics libraries, information systems,
math indexing and retrieval, mathematical content representation
There is no abstract art. You must always start with something. Afterward
you can remove all traces of reality.
I. INTRODUCTION P a W
°P i c a s s
°
The solution to the problem of mathematical formulae retrieval
lies at the heart of building digital mathematical libraries (DML).
There have been numerous attempts to solve this problem, but none
have found widespread adoption within the wider mathematics community.
And as yet, there is no widely accepted agreement on the
math search format to be used for mathematical formulae by library
systems or by Google Scholar.
MathML standard by W3C has become the standard for mathematics
exchange between software tools. Almost no MathML is
Permission to make digital or hard copies of all or part of this work for
personal or classroom use is granted without fee provided that copies are
not made or distributed for profit or commercial advantage and that copies
bear this notice and the full citation on the first page. To copy otherwise, to
republish, to post on servers or to redistribute to lists, requires prior specific
permission and/or a fee.
DocEng2011, September 19-22, 2011, Mountain View, California, U S A
Copyright 2011 A C M 978-1-4503-0863-2/11/09 ...$10.00.
written directly by authors—they typically prefer a compact notation
of some TgX flavour such as LTgX or AMSLTgX. The designer of a
search system for mathematics is thus faced with the task of converting
data to a unifying format, and allowing DML users to use their
preferred notation when posing queries. [AMS]LTBX or similar Tj<X
macropackages are the typical preferences; Presentation MathML
or Content MathML are used only when available as outputs of a
software system.
During the integration of existing DMLs into larger projects such
as EuDML [9], the unsolved math search problem becomes evident—
DML without math search support is an oxymoron. We have evaluated
several systems for our goals: 1) MathDex1
(formerly MathFind
[6]); 2) EgoMath2
developed by Josef Misutka as an extension
of a full text websearch core engine Egothor [5]; 3) MTgXSearch3
,
a search tool offered by Springer in SpringerLink; 4) LeActive-
Math4
search, developed as part of the ActiveMath-EU project and
5) MathWebSearch5
is an MSE developed in Bremen/Saarbriicken
by Kohlhase et al. [1] Our evaluation [7] has lead us to conclude that
there is no satisfactory, math-aware and scalable solution. For this
reason, we designed and implemented [3,7] a new robust solution
for retrieving mathematical formulae.
Section 2 presents our design of this scalable and extensible system
for searching mathematics, taking into account not only inherent
structure of mathematical formulae but also formula unification and
subformulae similarity measures. Our evaluation of a prototypical
implementation on the Apache Lucene open source full-featured
search engine library is presented in Section 3. The paper concludes
with a description of the WebMIaS interface and listing future work
directions in Section 4 and with a summary in Section 5.
Art is never chaste. It ought to be forbidden to ignorant innocents, never
allowed into contact with those not sufficiently prepared. Yes, art is
dangerous. Where it is chaste, it is not art.
2. DESIGN OF MIAS Pablo Picasso
We have developed a math-aware, full-text based search engine
called MlaS (Math Indexer and Searcher). It processes documents
containing mathematical notation in MathML format. MlaS allows
users to search for mathematical formulae as well as the textual
content of documents.
Since mathematical expressions are highly structured and have no
canonical form, our system pre-processes formulae in several steps
to facilitate a greater possibility of matching two equal expressions
with different notation and/or non-equal, but similar formulae. With
1
www.mathdex.com/
2
egomath.projekty.ms.mff.cuni.cz/egomath/
3
www.latexsearch.com/
4
devdemo.activemath.org/ActiveMath2/
5
search.mathweb.org/index.xhtml
an analogy to natural language searching, MlaS searches not only
for whole sentences (whole formulae), but also for single words and
phrases (subformulae down to single variables, symbols, constants,
etc.). For calculating the relevance of the matched expressions
to the user's query, MlaS uses a heuristic weighting of indexed
mathematical terms, which accordingly aifects scores of matched
documents and thus the order of results.
At the end of all processing methods, formulae are converted
from X M L nodes to a linear string form, which can be handled by
the indexing core.
2.1 Math Indexing Workflow
The top-level indexing scheme with a detailed view of the mathematical
part is shown in Figure 1.
MlaS is currently able to index documents in XHTML, HTML
and TXT formats. As Figure 1 shows, the input document is first
split into textual and mathematical parts. The textual content is
indexed in a conventional way, mathematics needs to be processed
differently.
2.2 Math preprocessing
Mathematical expressions are pre-analyzed in several steps to
facilitate searches not only for exact whole formulae, but also for
subparts (tokenization) and for similar expressions (formulae unifications).
This addresses the issue of the static character of full-text
search engines and creates several representations of each input
formula, all of which are indexed.
Tokenization is a straightforward process of obtaining subformulae
from an input formula. MlaS makes use of Presentation
MathML markup where all logical units are enclosed in X M L tags
which makes obtaining all subformulae a question of tree traversal.
MlaS performs three types of unification algorithms, the goal of
which is to create several more or less generalized representations
of all formulae obtained through the tokenization process. These
steps allow the system to return similar matches to the user query
while preserving the formula structure and a-equality [5]:
1. Ordering—ordering of the operands of the commutative oper-
ations;
2. Variables unification—substitution of all variables for unified
symbols (ids) while preserving bound variables;
3. Constants unification—substitution of all number constants
for one unified symbol (const).
During the searching phase, a query can match several terms in
the index. However one match can be more important to the query
than another, and the system must consider this information when
scoring matched documents. Each indexed mathematical expression
has a weight (relevance score) assigned to it describing how far the
actual formula is from its original representation. It is computed
throughout the whole indexing phase by individual processing steps
following this basic rule of thumb—the more modified a formula
and the lower the level of a subformula, the less weight is assigned
to it.
It is impossible to assemble a weighting function that is exactly
right. Such a function needs to consider a document base on which
the system will run as well as the established customs in a particular
scientific field. We tried to create a complex and robust weighting
function that would be appropriate to many fields.
At the end of the preprocessing phase, mathematical formulae are
transformed from X M L nodes to a compacted string form so it can
be handled by a full-text indexing core.
An example of the formula preprocessing is displayed in Figure 2.
2.3 Searching
In the search phase, user input is again split into mathematical
and textual parts. Formulae are then preprocessed in the same way
as in the indexing phase, except for tokenization—we doubt that
users would want to search for subparts of a queried expression
rather than the whole.
Art is the elimination of the unnecessary.
3. EVALUATION Pablo Picasso
For large scale evaluation, we needed an experimental implementation
and a corpus of mathematical texts.
3.1 Implementation
The Math Indexer and Searcher is written in Java. The role of fulltext
indexing and searching core is performed by Apache Lucene
3.1.0. The mathematical part of document processing can be seen
as a standalone pluggable extension to any full-text library, however
it needs custom integration for each one. In the case of Lucene, a
custom Tokenizer (MathTokenizer) has been implemented.
When searching for mathematical formulae, their weights need
to be considered in the final score of the document. The scoring
function of our MlaS system adds one parameter to the Lucene's
standard practical scoring function (described in detail at http:
//lucene.apache.org/java/3_l_8/api/all/org/apache/
lucene/search/Similarity .html)—weight w of one matched
formula:
score(q, d) = coord(q, d) • queryNorm(q)•
^ (tf(t in d) • avg(w) • idf(t)2
• t.getBoostQ • norm(t, d)) (1)
tinq
If a document contains the same formula more than once (each
occurrence can have different weight assigned), the average value
of all the weights is taken into consideration (avg(w)).
3.2 Corpus of Mathematical Documents
A document corpus MREC (Mathematical REtrieval Corpus) with
439,423 scientific documents was used to evaluate the behavior of
the system we modelled. The documents come from the arXMLiv
project that is converting document sets from arXiv into XHTML +
MathML (both Content and Presentation) [8]. The resulting corpus
size was 124 GB uncompressed, 16 GB compressed. This corpus of
documents (MREC version 2011.4.439) is available for download
at http://nip.fi.muni.cz/projekty/eudml/MREC.
3.3 Results
Math Indexer and Searcher demonstrated the ability to index and
search a relatively vast corpus of real scientific documents. Its usability
is greatly improved thanks to its preprocessing functions
together with the formulae weighting model. The ability to search
for exact and similar formulae and subformulae, more so with customizable
relevance computation, demonstrates an unquestionable
contribution to the whole search experience.
It is very difficult, if not impossible, to completely verify the
correctness of the theoretical considerations made in the previous
sections and thus correctness of search results. For this purpose, a
sufficiently large corpus of documents with fully controlled content
would be needed. For any assembled query, there should exist beforehand
a complete list of the documents ordered by their relevance
to the query to compare the actual results to. On the other hand,
the real world relevance of the results being returned needs to be
verified by an extensive user study and perhaps several parameters
need to be adjusted for the best results.
We have applied an empirical approach to the evaluation so far.
For these purposes we created a demo web interface, see Section 4.
3.4 Scalability Testing and Efficiency
We have devised a scalability test to see how the system behaves
with an increasing number of documents and formulae indexed.
Subsets containing 10,000, 50,000, 100,000 ... and the complete
439,423 documents were gradually indexed and several values were
measured: the number of input formulae, the number of indexed
formulae, the indexing run-time and indexing CPU-time. Our observation
showed that system scales linearly in proportion to the
number of documents.
The whole document set contained 158,106,118 formulae, after
all the preprocessing was done, our system indexed 2,910,314,146
expressions and the indexing run-time was 1,378 min (almost
23 hours) and the resulting index size was approx. 63 GB. We also
measured an average query time by querying the created index with
a set of differently complex queries (mixed, non-mixed, more/less
complex single/multiple formulae). Resulting average query time
was 469 ms.
You don't make art, you find it.
Pablo Picasso
4. WEB INTERFACE AND FUTURE WORK
To allow user evaluation, we have created web interface for
MlaS—the WebMIaS system [4]—available at http: / / n i p . f i .
muni.cz/projekty/eudml/mias/. WebMIaS allows the retrieval
of mathematical expressions written in Tr^X or MathML.
TpX queries are converted on-the-fly into tree representations of
Presentation MathML, which is used for indexing. WebMIaS allows
complex queries composed of plain text and mathematical formulae.
It currently works over our complete mathematical corpus, MREC.
As the semantically same formulae can be represented by different
MathML notation, it is evident that some kind of normalization
of MathML is necessary. We use Canonical MathML [2] as normalization
MathML format and are using the software library U M C L
supporting it. Canonicalization (converting to a canonicalized form
of MathML) is used both during the indexing and querying phases.
It not only increases fairness of similarity ranking, but also helps
to match a query against the indexed form of MathML. We plan to
extend the effect of the commutative ordering part of the normalization
mentioned in 2.2 by arranging a full list of commutative
operators and all the operators with their priorities so the ordering
can be perfected.
Another area of long-term research planned is supporting Content
MathML, in a way similar to the current handling of Presentation
MathML. The architectural design is open to it, but as most of the
math available is in Presentation MathML taken from PDFs, this is
not currently a high priority.
Art is the lie that enables us to realize the truth.
Pablo Picasso
5. CONCLUSIONS
We have presented an approach to mathematics searching and
indexing—the architecture and design of the MlaS system, and
input:
ordered:
tokenization:
variables
unification:
constants
unification:
(id.+idz'+2
, 0.1)
\a + b1+c
, 0.125)
mi" < "mn" => 2 - c]
a, 0.0875 / / +, 0.0875 , 0.0875
[b, 0.06125)/ ;
(c, 0.042875)/ ', \ (2,0.042875)
(+,0.042875) * \
( ŕ < ! + 2
, 0 . 0 7 ) (id,+ 2, 0.0343)
(a +bc+con
", 0.0625)
\id,+id"-,
(bc+c
""", 0.04375) c + const, 0.030625
', 0.05
1
lid,+con:idT- , 0.035 (id, + const, 0.01715
Figure 2: Example of formula preprocessing. Ordered pairs are (<expression written naturally>, <it's weight>). All expressions as
shown are indexed, except for the original one.
its WebMIas interface. The feasibility of our approach has been
verified on large corpora of real mathematical papers from arXMLiv.
Scalability tests have confirmed that the computing power needed
for fine math similarity computations is readily available and allows
the use of this technology for projects on world-wide scale.
Acknowledgements. This work has been partially supported by
the Ministry of Education of CR within the Center of Basic Research
LC536 and by the European Union through its Competitiveness and
Innovation Programme (Policy Support Programme, 'Open access
to scientific information", Grant Agreement No. 250503). We thank
Michal Ružička for help with figure drawings and web form of MlaS
interface.
Bad artists copy. Good artists steal.
Pablo Picasso
6. REFERENCES
[1] §. Anca. Natural Language and Mathematics Processing for
Applicable Theorem Search. Master's thesis, Jacobs University,
Bremen, Aug. 2009.
https://svn.eecs.jacobs-university.de/svn/eecs/
archive/msc-2889/aanca.pdf.
[2] D. Archambault and V. Moco. Canonical MathML to Simplify
Conversion of MathML to Braille Mathematical Notations. In
K. Miesenberger, J. Klaus, W. Zagler, and A. Karshmer, editors,
Computers Helping People with Special Needs, volume 4061 of
Lecture Notes in Computer Science, pages 1191-1198.
Springer Berlin / Heidelberg, 2006.
http://dx.doi.org/18.1887/11788713_172.
[3] M. Liška. Vyhledávání v matematickém textu (in Slovak),
Searching Mathematical Texts, 2010. Bachelor Thesis, Masaryk
University, Brno, Faculty of Informatics (advisor: Petr Sojka),
https://is.muni.cz/tn/255768/fi_b/?lang=en.
[4] M. Líška, P. Sojka, M. Ružička, and P. Mravec. Web Interface
and Collection for Mathematical Retrieval. In P. Sojka and
T. Bouche, editors, Proceedings of'DML 2011, pages 77-84,
Bertinoro, Italy, July 2011. Masaryk University, http:
//www.fi.muni.cz/~sojka/dml-2811-program.html.
[5] J. Mišutka and L. Galamboš. Extending Full Text Search
Engine for Mathematical Content. In P. Sojka, editor,
Proceedings of'DML 2008, pages 55-67, Birmingham, UK,
July 2008. Masaryk University,
http://dmi.cz/dmlcz/782546.
[6] R. Munavalli and R. Miner. MathFind: A Math-Aware Search
Engine. In Proceedings of the 29th annual international ACM
SIGIR conference on Research and development in information
retrieval, SIGIR '06, pages 735-735, New York, N Y USA,
2006. ACM.
http://doi.acm.org/18.1145/1148178.1148348.
[7] P. Sojka and M. Líška. Indexing and Searching Mathematics in
Digital Libraries - Architecture, Design and Scalability Issues.
In J. H. Davenport, W.M. Farmer, J. Urban and F. Rabe, editors,
Proceedings of CICM Conference 2011 (Calculemus/MKM),
volume 6824 of Lecture Notes in Artificial Intelligence, LNAI,
pages 228-243, Berlin, Germany, July 2011. Springer-Verlag.
http://dx.doi.org/18.1887/978-3-642-22673-1_16.
[8] H. Stamerjohanns, M . Kohlhase, D. Ginev, C. David, and
B. Miller. Transforming Large Collections of Scientific
Publications to X M L . Mathematics in Computer Science,
3:299-307, 2010.
http://dx.doi.org/18.1887/sl1786-818-8824-7.
[9] W. Sylwestrzak, J. Borbinha, T. Bouche, A. Nowiňski, and
P. Sojka. EuDML—Towards the European Digital Mathematics
Library. In P. Sojka, editor, Proceedings ofDML 2010, pages
11-24, Paris, France, July 2010. Masaryk University,
http://dmi.cz/dmlcz/782569.
Similarity Search for Mathematics:
Masaryk University team at the NTCIR-10 Math Task
Petr Sojka
Faculty of Informatics
Masaryk University
Botanická 68a, 602 00 Brno
Czech Republic
sojka@fi.muni.cz
Michal Růžička
Faculty of Informatics
Masaryk University
Botanická 68a, 602 00 Brno
Czech Republic
mruzicka@mail.muni.cz
Martin Líška
Faculty of Informatics
Masaryk University
Botanická 68a, 602 00 Brno
Czech Republic
martin.liski@mail.muni.cz
ABSTRACT
This paper describes and summarizes experiences of Masaryk
University team M I R M U with the mathematical search performed
for the N T C I R pilot Math Task. Our approach is
the similarity search based on enhanced full text search utilizing
attested state-of-the-art techniques and implementations.
The variability of used Math Indexer and Searcher
(MlaS) system in terms of the math query notation was
tested by submitting multiple runs with four query notations
provided. The analysis of the evaluation results shows
that the system performs best using TrnjX queries that are
translated to combined Presentation-Content MathML.
Team Name
M I R M U (Math Information Retrieval at Masaryk Univer­
sity)
Subtasks
Math Retrieval Subtask
Keywords
math, search, similarity search, math information retrieval,
MIR, MlaS, evaluation, math representation and indexing
1. INTRODUCTION
Math information retrieval (MIR) starts to be recognized
as an important very domain-specific sort of information retrieval
research field.
Masaryk University (MU) has entered the area of M I R
during the development of the Czech Digital Mathematics
Library D M L - C Z in mid nineties. It became obvious that
Digital Mathematical Libraries (DMLs) are specific in many
aspects. This fact motivated and triggered establishment of
D M L workshop series in 2008 [7].
Some papers in D M L s consist of more formulae than texts,
and we started to think about representation and indexing
of mathematical formulae in addition to texts. Because formulae
appearing even in the main metadata (title, abstract,
references) were not properly recognized, represented, and
indexed, handling of math in Google Scholar or D M L s was
notably suboptimal. There was no widely acceptable user
interface and representation for math formulae in information
retrieval (IR). T^jX math has been designed for typesetting
and optimized for minimal stroke typing. Luckily,
logical math markup of DTpjX is widespread now, and A M S
packages cover most of math needed in IR.
We have designed and developed first math formulae indexing
and retrieval prototypes in the series of Bachelor thesis
[2, 5]. Math formulae are structures appearing within
accompanying texts that convey meaning and relations between
objects mentioned in the text. They could be represented
as trees and one could define formulae similarity as
tree structure similarity.
The working prototypes were further experimented with,
developed, researched [9, 10], discussed at D M L panels and
evaluated [6]. First M I R specific workshop was co-organized
in Bremen in 2012, to heat the discussions about M I R as a
gateway to the vast knowledge stored in DMLs.
M U has partnered in the development of the European
Digital Mathematics Library, E u D M L [11], where it has
been decided to support math formulae search, as one of
math specific features. [12] We have also paid attention to
the user interface aspects—formulae is rendered as user types
by rendering the formulae after every keystroke [13, Section
3.5]. To the best of our knowledge, E u D M L with MlaS is
the first digital library collecting non-born-digital P D F s that
supports math search in fulltexts. Mathematician all over
the world can used it and practise math search as a mean
to narrow their search with math formulae facets.
The paper is structured as follows. In the Section 2 we
give a brief overview of our approach used in our MlaS system.
Section 3 describes run that M I R M U team submitted
for N T C I R Math tasks, with scripts used for automation of
querying. In the Section 4 our approach in all three participated
subtasks is revealed. Results are discussed in the
Section 5. We conclude with summary and further development
thoughts in the Section 6.
2. OVERVIEW
Our approach to searching mathematical content in documents
is based on conventional full-text searching. As mathematical
notation, e.g. expressions and formulae, is highly
structured, we preprocess mathematical content in order to
be processable by full-text searching methods. The preprocessing
procedures include canonicalization, which is very
important in order to allow matching of two equal formulae
with slight notational differences [3]. Therefore, the level
of canonicalization needs to be as high as possible. Then,
to allow searching of subformulae, expressions are tokenized
and subtrees of formulae extracted. Subformulae are stored
in the locations of their original forms so they can be easily
located at the query time. To be able to search for similar
expressions, we propose several generalization preprocess-
ing techniques. These include unification of variables, unification
of number constants and font typeface preservation.
These aim to increase the recall of mathematical search. To
increase the precision, we rank each indexed expression according
to its distance from the original non-tokenized formula.
The less unified subformulae extracted from a higher
level of the original formula tree, the higher weight factor
it gets. Assigned weights affect the ordering of retrieved
results.
The factors that influence resulting weights of indexed
subformulae are adjustable. Different document collections,
i.e. from different S T E M fields, benefit from different setups.
The current setup reflects our generic view of distance of extracted
subformulae to their original trees. Different setup
might influence the order of retrieved results significantly.
From the evaluation point of view, different setups bring
different hits to the pooling resulting in higher or lower relevancy.
There is no ideal set of factors, however, we want
to reach to the optimal setup by repetitive evaluation as
discussed in the Section 6.
We developed a search system according to these principles.
MlaS (Math Indexer and Searcher) is a math-aware
full-text based search engine. It is based on the state-of-theart
searching library Lucene. It supports combined text and
math searching. Refinement of many text query results by
adding a math query is believed to be a very powerful tool.
Mathematical preprocessing is a plug-in that can be used
with any Lucene or Solr based systems. This is the case of
E u D M L . MlaS processes documents with mathematics encoded
in Presentation or Content MathML. A t the end of the
preprocessing, expression trees are linearized to compacted
string form to reduce index space requirements.
The very straightforward query interface of MlaS consists
of only one input field. Users can type in textual queries
together with math queries encoded using DTj^X notation
as well as M a t h M L notation. Query is on-the-fly visualized
as 'typeset' formula in user's web browser to allow users to
verify the correctness of the mathematical part of the query.
Along the basic information about retrieved documents the
result list shows a snippet with highlighted text and math
tokens that are the most significant in the document's rank.
This allows for quick primary evaluation of the documents
relevance to user's query.
Alongside interactive web querying interface MlaS offers
searching using web services. This is a indispensable feature
for automated querying that was used to retrieve evaluation
results for the N T C I R Math Task. [I]
MlaS participated in the M I R 2012 Happening evaluation
workshop with good performance. Further evaluation for
both effectiveness and efficiency using M I R Happening as
well as N T C I R Math Task collections was done in [6].
For a more detailed description of all parts of the system
the reader is referred to [9, 8, 6].
3. AUTOMATIC QUERYING SCRIPTS
Availability of the task inputs in the X M L format supplemented
by MlaS web service interface allowed us to fully
automatize the task data processing.
For the Formula Search and Full Text Search subtasks the
batch querying script read subtask topic specifications from
the particular X M L file and constructed four different X M L
queries for the MlaS web service interface for each of the
subtask topics:
P M a t h q u e r y The query contained Presentation M a t h M L
code specified in the pquery element of the subtask
topic X M L specification. In the case of the Full Text
Search subtask, plain text from the words element of
the particular topic was added to the end of the query.
The input M a t h M L code was slightly modified—each
occurrence of the construction
<mws:qvar xmlns:mws="http://www.mathweb.org/mws/ns"
name="X"/>
was substituted for a simple <mi>X</mi> statement.
C M a t h query This query was constructed in the very same
way as the P M a t h query but using Content M a t h M L .
i.e. cquery element was used instead of the pquery element
and qvar was substituted for the c i element.
P C M a t h q u e r y This query combines both Presentation
and Content MathML, i.e. the query is constructed as
concatenation of the Presentation M a t h M L from the
PMath query and Content M a t h M L from the CMath
query, in the case of the Full Text Search subtask followed
by the plain text from the words element.
T g X The last query is similar to the previous ones but the
TJ5X code from the TeXquery element was used instead
of the M a t h M L . There was no modification of the Tj^X
statement except for a single dollar sign ($) added on
both sides of the original statement to properly indicate
TJiJX encoded part of the query to the MlaS sys-
tem.
Presentation M a t h M L is widely used X M L encoding of
mathematical contents and is often used together with the
X H T M L markup language on the web. It is also used as
a common format for data interchange among various computer
systems. Encoding just the appearance of the formulae
it is reasonably easy to generate Presentation M a t h M L from
other languages, e.g. TJ^X. Being widely used we believe a
math-aware search engine have to be able to cope well with
this M a t h M L encoding.
On the other hand, Content M a t h M L encodes meaning
of the formulae. With proper normalization of the input
encoding, it should be easier to find similar formulae using
this form of MathML. Through the C M a t h and P C M a t h
queries we wanted to compare behaviour of our system in
contrast to the query using Presentation M a t h M L notation.
The TJiJX query was used to investigate impact of the
DTj^X to M a t h M L on-the-fly conversion that is performed
by the MlaS system if the user ask queries in this 'humanfriendly'
language.
For the Open Information Retrieval subtask we had to
prepare MlaS queries based on the natural text specification
of the problem. Queries were constructed as set of keywords
for each topic usually extended by mathematical formula
in the TJiJX notation. Technically, query was constructed
similarly to the TgX queries for the Full Text Search subtask.
To allow automation of the subtask processing our query
data was saved in a simple machine processable plain text
format that was read by the batch script.
The constructed X M L query was sent to the MlaS web
service. Two different indexes were used—for the Formula
Search subtask index for finding and retrieving single formulae
was used, the Full Text Search and Open Information
Retrieval subtasks used standard MlaS index for document
finding (see Section 4).
MlaS web service answered in a X M L format. The answer
was analyzed by our script and three different output
formats were created.
text The text format was constructed according to the N T CIR
Math Task requirements for the text results submission
format. Topic ID, found document/formula
ID and its rank (order in the result list) together with
MlaS score assigned to the result and identifier of the
run was presented in a simple plain text format.
X M L The N T C I R Math Task defines also X M L format for
submission of the results. This file encodes in X M L
similar information as the text format and was used
for final submission of the M I R M U results.
H T M L For investigation of the results during the tuning of
the system and queries we generated H T M L summary
of the results. In this format, plain text representation
of the results in the N T C I R Math Task format
was shown. However, in addition to that hyperlinks
for direct navigation to the WebMIaS interface were
available for interactive investigation of the queries and
results together with MlaS web service response X M L .
See Figure 1.
The querying process of all nine runs we performed for
participation in the N T C I R Math Task took less than one
hour (roughly 6 minutes each) of clock time on a standard
P C workstation.
4. MATH RETRIEVAL SUBTASK
M I R M U team participated in the Math Retrieval Subtask
with contributions to all three types of search: Formula
Search, Full Text Search and Open Information Retrieval.
Full Text Search simulated the standard use of a search
system—queries comprised math expressions as well as text.
For each query, the system returned a list of documents as
they were provided in the test collection. No special modifications
were therefore needed.
For the Formula Search, however, several adjustments were
necessary. Formula Search aimed at retrieving independent
formulae located in the provided documents. If, for example,
a document contained 100 formulae, each of them could
be retrieved as a hit on its own. This is a difference to the
normal workflow. However, flexible design of MlaS allowed
us to index every formula as an independent index document
containing only that formula by adding a special document
handler.
For the needs of Math Retrieval Subtask, we created two
indexes from the provided document collection, that contained
36,697,971 math expressions and had 7.3 G B in size.
After preprocessing, both indices stored more than 1.5 billion
subexpressions. The first index, NTCIR-fragments, was
created from single formulae to complete Formula Search
search type. Every index document represented only one formula
from the input files, therefore, the resulting index contained
more than 73.5 million documents. It took 8.5 hours
to complete the index sized around 39.5 G B . The second
index called NTCIR-files was created the regular way consisting
both of text and formulae where one index document
represented exactly one physical document from the collection.
It took 5 hours to complete the index sized around
30 G B . This comparison shows an interesting overhead of
the Formula Search index. It contains less data but is split
into more logical units which resulted in the longer indexing
time and a larger index.
Table 1: Index statistics (run on 448GiB R A M ,
eight 8-core 64bit processors Intel Xeon T M X7560
2.26GHz machine)
Indexing times [minj Index
size [GB]Index Wall C P U
Index
size [GB]
NTCIR-files 291.8 1649.0 30
NTCIR-fragments 513.3 2029.4 39.5
Alongside text, MlaS accepts DTr^X and both Content and
Presentation M a t h M L as a query notation for mathematics.
DTj^X queries are converted to combined PresentationContent
M a t h M L by D T E X M L converter. We decided to
utilize the possibility of submission of four runs to analyse
the difference in the performance of the system with regard
to the query language. This was supported by the test query
collection that provided all of the mentioned formats for each
query. Table 2 shows differences in query language for each
run.
Table 2: Runs submitted to Formula Search and Full
Text Search
R u n # Query language
1 Presentation M a t h M L
2 Content M a t h M L
3 Presentation and Content M a t h M L
4
After the results publication we discovered that R u n 2
and R u n 3 produced exactly the same hit lists with the same
results. Therefore, we omit erroneous R u n 3 from our results
analysis in Section 5. We estimate its effectiveness to be at
the same level with the Tr^X R u n 4.
Open Information Retrieval Subtask
Open Information Retrieval subtask is probably closest to
the real use and setup of M I R both in digital library systems
or on the web. People are used to query Google just
by giving small set of keywords, and find what they are looking
for. Mathematicians are used to write their formulae in
D T ^ X are are capable of specifying domain and semantically
related formulae in a query.
We took the advantage of textual index of our system—
MlaS has both text and math indexed in a Lucene based
system. Queries were written manually mainly as bag of text
and formulae. Textual area allows querying of alphabetical
or alphanumerical words, or collocations, and search was
narrowed usually by additional bag of formulae.
The second author has prepared a set queries in a text
file, from which the queries containing all text and M a t h M L
(both Presentation and Content, by LaTeXML) were generated
by a script. The strategy was to find and write down the
biggest and 'semantically' close set of formulae and words.
As MlaS scoring is cumulative, the more, the better, given
the laziness of user. Examples from a submitted query file is
below (query N T C I R code is follow by line of formulae and
line of textual keywords and collocations:
Results for 'TeX' run with query ID 'NTCIR10-FS-21' in index '1' (XML response)
Results for 'TeX' run with query IP 'NTCIR10-FS-22' in index '1' (XML response
Results for 'PMath' run with que/y ID 'NTCIR10-FT-1' In Index '0' (XML respons
NTCIR*
NTCIR*
NTCIR*
NTCIR*
NTCIR*
NTCIR*
NTCIR*
NTCIR*
NTCIR*
NTCIR*
wraFÍNT
CI R*
NTCIR*
NTCIR*
NTCIR*
NT'IIFr
NTCIR*
NTCIR*
NTCI
. \meta{.126/f050057.xhtml)
. \meta{l37/-f054563. xhtml)
. \meta(88/f034822.xhtml)
. \mets-{65/f 025688. xhtml)
. \meta-{104/-f041288.xhtml)
. \meta{36/f014099.xhtml)
. \meta{.142/f056619.xhtml)i
. \meta-£97/f 038791. xhtml)
. \meta{149/f059.
\metall93/f07S900.xhtmj
. \metai236/-fQ94:
. \meta(3/f000885.xhtml)]
. \metaU71/f068256.xht/l)
. \meta{215/t 0:^710.
,{3.1079004) \meta{M:RMU_PMath_2013-01-16T 16:52:2"+vi:-:>
a(0.32205144)
a-{0.263323-13)
ta{0.24791265}
a{0.24737564)
tsi 0.23069659)
a{0.22932S26) \
meta{0.22177562)
ymetať0.20^91624)
[0. 1960693)
{0. 16182569) '
:.H{M:F lath ;
m4t.H[M:RMU_F M^t|-i_2013- 01 - 1GTIC: 32:27+0:
mata{I"i:FWU_PMath
\meta{MI RMU_PMati
meta{MIRMU_PMath
\meta{MI RMU_PMati
-MMZP
lath
WEBMIaS
$H-{n)[x)=Z'{n)(x)/&-in)(x)s
Your query: H"[X) - Z"<X)IB"[X;
converted aid c.
Line and contin
...r W(A)=ßW(A)/S«(A)..
f088746. xhtml
...HP(J£) = Cf(Jt)JBP(JF) ...
scare = 0.01843161
f088746.xhtml - cached XHTML
variability of two intermediats-redshift, hiah-k
This XML file does not appear to have any style information associated with it. The document tree is shown below.
</path>
< r e s u l t s >
- < r e s u l t >
<id>f088746.xhtml#idl21369</id>
<info>score = 0.76074165</info>
<path>NTCIR-sandbox-origirifl -darumenrs/???/f088746.xhtrr
- < s n l p p e t >
... <spsn dass="highlight"xm:math id="idl21369" alttext="H^{p}({\mathcal{M}})=C"{p}C{\mathcal{M} })/B~{p}({\rnathcal{M}})'
display="inline"xm:semantics i d = " i d l 2 1 3 7 5 " x m : m r o w id=' i d l 2 1 3 7 6 " x m : m r o w i d = " i d l 2 1 3 7 8 " x m : m s u p i d = " i d l 2 1 3 7 9 " x m : m i
id="idl21380">H</m:mi><Ti:mi i d = " i d l 2 1 3 8 2 " > p < / m : m i x / ^ : m s u p x m : m o i d = " i d l 2 1 3 8 4 " x / m : m o x i r : m f e n c e d io="idl21386"
•pen=' (" c l o s e = " ) " x m : m i id—"id 121391" mathvariant="script">M</m:mi></m:mfenced></m:rnrow><rn:mo id="idl213S6"> =
</m:mo><m:mrow i d = " i d l 2 1 3 9 8 " x m : m r o w i d = " i d l 2 1 3 9 9 " x m : m r o w c = " i d l 2 1 4 Q 0 " x m : m s u p id="idl21401"><m:rri
id="idl21402">C</m;mixm;mi i d = " i d l 2 1 4 0 4 " > p < / m ; m i x / m ; m s u p x r r ; r T i o i d = " i d l 2 1 4 0 6 " x / m ; r n o x m ; r n f e n c e d id="idl21409"
•pen=' (" d o s e = " ) " x m ; m i id="id 121414-" mathvariant="script">M</m;mi></m;mfenced></m;mrow><rn;mo
id="idl2141B">/</m:mD><Ti:insup id=" d l 2 1 4 2 0 " x m : m i id="idl21422">B<ym:mixm:mi id="idl21424">p</m:mi></Ti:insup>
</m:mrow><m:mo i d = " i d l 2 1 4 2 6 " x / m : m o x m : m f e n c e d id="id!21428' open="(" close = " ) " x m : mi id="idl21433"
mathvsriant="script">M</iT:mi></m:mfenced></m:mrow></m:mrow><iT:annotation-xrTil id ="id 1214-38" encoding ="MathMLC
o n t e n t " x m : a p p l y i d = " i d l 2 1 4 4 1 , ,
x i r : e q id=, ,
idl21442'7xm:apply i d = " i d l 2 1 4 4 3 " x m : t i m e s i d = " i d l 2 1 4 4 4 7 x m : a p p l y
i d - " i d l 2 1 4 4 5 " x m : c s y m b o l id-"id 121116" c d - " a m b i g u o u s " s u p e r s c r i p t < / T i : c s y m b o l x m : d i d - " i d l 2 1 4 5 1 " > H < / m : c i x m : c i
id="idl21453">p</m;ci></m;apply><m:ci id="idl21455">M</m;cix/m a p p l y x m i a p p l y i d = " i d l 2 1 4 5 7 " x m ; t i m e s id="idl21458"/>
<m;apply id="idl21460"xrr;divide i d = " i d l 2 1 4 6 1 " / x m ; a p p l y i d = " i d l 2 1 4 6 2 " x m ; t i m e s id="idl21463'7xm;apply id="idl21464">
<n'i:csvmbol id ="id 121465 ' cd="ambiguous">superscript</m:csymbolxm:ci id="idl21470">C</m:cixm:c
id="idl21472">p<;m:ci></m:apply><m:ci id="idl21474">M</m:cix/m s p p l y x r r v a p p l y i d = " i d l 2 1 4 7 6 " x ' n : e s y m b o l id="idl21477"
r_d=' ambiguous">superscript</m:csyiTbolxm:ci id="idl21482">B</rn:ci><m:ci id="idl21484">p</m:cix,'m:apply>
</m:applyxrrvci id="id 121486">M</rr:cix/m:apply></m:apply></m:annotation-xmlxm:annotation id=" c 121488"
encccing="application/x-tex'>H"{p}({\nathcal{M>>)=CA
{p}({\mathcal{M}}yB~{p}({\mathcal{M}})</m:annotation>
< / m : s e m a n t i c s x / m ; m a t h x / s p a n > ,,,
</snippet>
<title>f088746.xhtrnl#idl21369</title>
- < r e s u l t >
<id>f065185.xhtml#id57989</id>
<info>score = 0.753482 4</info>
<path>NTCIR-sandbox-origina -documents/163/f065185.xhtml</path>
- < s n i p p e t >
,,, <span class="highlight"xm;math id="id5790i, M
i h="ii ~ilii i íŕ":: -111: f Hŕi 11 n i iti •:: f i d = " i d 5 7 9 9 2 " x m ; m r o w i d = " i d 5 7 9 9 3 " x m ; m r o w
i d = " i d 5 7 9 9 4 " x m : m r o w i d = " i d 5 7 9 9 6 " x m : m s u p id="id57997"xm:mi ic="id57998">Li</m:mixm:mfenced id="id58000" open="("
c l o s e = " ] " x m : m i id=M
id58005">k</m:mi></m:mfenced></m:msup><m:mo i d = " i d S 8 0 0 7 " x / m : m o x m : m f e n c e d id="id58010"
• p e n - ' (" d o s e - " ) " x m : m i id-1d50015,
'>A</m:mi></m:mferced></m:mrcw><m:rrio i d - " i d 5 0 O 1 7 " > - < / r n : m o x m : m r o w
Figure 1: H T M L summary for the investigation of the results.
NTCIR10-0MIR-1
$p\in (l,\inf)$ $l_l(l_p)$ $l_q$
conjugate space isomorphic subspace
NTCIR10-0MIR-2
$\Gamma$ $\cal{H}$ $\pi(\Gamma)~n$
Hilbert space d i f f e r e n t i a l operator discrete amenable group
Neumann algebra
NTCIR10-0MIR-3
$|\nabla u|*{r-2}$
d i f f e r e n t i a l equation operator
NTCIR10-0MIR-4
$y~{\prime\prime}+C y"\prime$ $F : R"n \rightarrow R"n$
$p : R \rightarrow R~n$
second order vector continuous "bounded solution"
"differential equation"
NTCIR10-0MIR-5
$\implies$
reduction ad absurdum
NTCIR10-0MIR-6
four color theorem
NTCIR10-0MIR-7
associative operators quantum mechanics
NTCIR10-0MIR-8
commutative monoid
NTCIR10-0MIR-9
perfect graph theorem Lovasz
NTCIR10-0MIR-10
$\implies$ $\
proof by induction
NTCIR10-0MIR-11
Nonlinearity Predicting Chaotic System
NTCIR10-0MIR-12
sequentially compact "limit point compact" compact
t o t a l l y bounded complete
NTCIR10-0MIR-13
40A05
NTCIR10-0MIR-14
Riemann theta function
NTCIR10-0MIR-15
$ax~3+bx+c$
Cardano cubic equation
NTCIR10-0MIR-16
$n~5-7n~4+17n~3-18n~2+7n-l$
root polynomial
NTCIR10-0MIR-17
zero divisor invertible f i n i t e ring inverse i s power
NTCIR10-0MIR-18
$f: R~3 \rightarrow R$
function derivative real-valued analysis
NTCIR10-0MIR-19
nonempty closed set intersection Banach space
For example, for the OMIR-2 query we have used as many
words and formulae as we thought could appear in a relevant
document. Another example worth mentioning is query
OMIR-13 where alphanumerical token of Mathematical Subject
Classification code was used as the only element of the
query: '40A05'.
In fact, preparation of the queries was straightforward
with just few debugging queries used during the development
process, especially when one got no results.
5. RESULTS
Overall scores of MlaS were above average of the Math
Task results [1]. Precision at rank five (P-5) of MlaS in
Run 4 was the highest from the all competing submissions.
Table 3 shows all four reported metrics for relevance level
'relevant'. Table 4 shows the same metrics for relevance level
'partially relevant'.
Interestingly, while other systems roughly doubled their
scores in 'partially relevant' metrics compared to the 'relevant'
ones (see the overview paper [1] for all results), results
of MlaS increased only slightly. We find this behavior very
interesting, as our system is a math similarity search system,
therefore we would expect 'partially relevant' results to be
much more successful.
We think this is caused by the design of MlaS that does
not tokenize queries. The complexity of the queries was
relatively high and MlaS does not extract subexpressions
from queries and so it searches only for the whole query
formulae. Therefore, when the query is complex, it may
match it as a whole or not at all.
We do not know the other systems in detail, but another
possible explanation for this behaviour can be different level
of unification done by the MlaS system compared to other
systems. We do match only formulae with the same structure,
but there are other systems that do either full unification
or also weight and match formulae with different or
bigger structure. The unification in MlaS is done on the
leaf level of derivation trees of formulae, namely unification
of variables and unification of number constants. No unification
on the inner node level is done so far, therefore MlaS
n
is unable to substitute subtrees. For example, ~}2 will not
i=l
71
match "^2 as (n — 5) is a different subtree to 1.
i=n — 5
Another use case is when searching small formulae. In
MlaS, every subcomponent of a complex formula is indexed.
Thus, even frequent simple formulae queries such as x2
that
occur in a large fraction of all the documents contributes
slightly to the partial relevance of each of these documents.
Therefore, almost every document is partially relevant and
the discrimination between documents is small. Possible
remedy is to use equivalent of inverse document frequency
scheme (IDF) weighting for math structure (size)—inverse
math structure document frequency (IMSDF): the more frequent
formulae [structure] occur in the documents the less
weight it will get during indexing, e.g. the weight will be
multiplied b l 0 £ #ofalldocuments
# ° f structurally same formulae '
Both tables show that the most successful run was Run 4
that used TpjX queries. Precision was the best in R u n 2.
Run 4 retrieved 50 % more results than Runs 2 but only few
of these additional items were judged as relevant or partially
relevant.
Table 3: Result metrics for submitted runs in Formula
Search with Relevance Level > 3 (Relevant)
Table 4: Result metrics for submitted runs in Formula
Search with Relevance Level > 1 (Partially rel-
evant)
Metric Run 1 Run 2 Run 4
P-10 avg 0.105 0.191 0.219
P-5 avg 0.133 0.229 0.276
M A P avg 0.060 0.112 0.127
Precision
0.109
(64/589)
0.185
(92/496)
0.123
(96/778)
Metric Run 1 Run 2 Run 4
P-10 avg 0.143 0.214 0.267
P-5 avg 0.181 0.267 0.343
M A P avg 0.066 0.081 0.100
Precision
0.148
(87/589)
0.232
(115/496)
0.161
(125/778)
Unfortunately, there has been a cardinal misunderstanding
about what the results of Full Text and O M I R searches
should report. Our search system for mathematics MlaS
and, to our knowledge, the majority of standard search engines
are designed to report results at the document level.
With M I R system, one can search only with formulae, but
still expects whole documents to be returned as results. This
becomes even more obvious, when math query is combined
with text to make the query more precise which, we believe,
is the right way of making use of math search capability.
This is exactly the case of Full Text and O M I R search
types. Queries consisted of both text and math which exactly
simulates the right usage of M I R systems. We do not
understand how only formula references can justify results
of mixed math-textual query. Additionally, as our system
is based on full-text search, we consider the implicit combination
of math and text search with the powerful weighting
function as one of our biggest advantages of our system. On
the other hand, we understand the severity of evaluating the
whole documents as results.
Nevertheless, our team posted document identifications
as results in both Full Text and O M I R searches which made
them invalid. Our system therefore could not be evaluated
in these natural search types.
6. CONCLUSIONS
Our participation in the N T C I R pilot Math Task was very
useful and motivating for the development of our system.
It provides unique opportunity to directly compare different
systems with different approaches on the same data set. Our
MlaS system achieved satisfactory results in the targeted
subtasks.
We would like to inspect on every judged results that we
posted to understand its non/relevancy to the respective
query. The MlaS system matches every formula in the same
manner and yet, there are results returned by our system
some of which were found relevant also by the judges and
some of which were found non-relevant. We hope to find patterns
in what makes some results non-relevant which could
lead us to improving our system.
The Math Pilot Task detected the best query language
for our system with the respect to the effectiveness of the
system. It is a T^X. notation that is translated to M a t h M L
parallel Presentation-Content markup. This is gratifying
news as we also want TpjX to be used as the main query
language since it is much used by the scientists and therefore
well known. To encourage T^X. input to the WebMIaS (web
interface of our system), we added the on-the-fly rendering
of the input formula for a better user experience and the
verification of correctness of the formula.
We discovered, that ability to evaluate is very valuable in
information retrieval. It is a driving force in the evolution
process of IR systems, more so if it is impartial as for example
at the N T C I R conference task. But, to justify the
development on a day to day basis, we need our own collection
with gold standards against which we could evaluate
our development steps. A l l of the participants as well as the
organizers of the Math Pilot Task recognized the difficulties
connected to evaluating math search systems. Our future
goal is to create our own, gold standard evaluation collection.
We find it a prerequisite to the further development of
retrieval techniques.
Future Work
We established the best query language for mathematical
part of queries. In the following Math Task, and we hope
there will be one, we will elaborate more on the weighting
function and make use of the runs by submitting results
generated with different factors that are used for the computation
of the similarity between the original formula and
its derived forms. This can shuffle the order of search results
to make more relevant hits appear higher in the result list.
Some ideas and aims of the future development of MlaS
and related tools are summarized in [8]. We believe that
the way to increase the practical usability and success of a
M I R system like MlaS is conditioned by better relevance and
speed (users love instant feedback). We plan to experiment
with several tier indexing for speed and prioritization of semantics
(Context MathML). A prerequisite for increasing
the relevance is better formulae disambiguation and canonicalization.
The road to it is paved by the full natural language
processing of the corpora of math texts (part of speech
tagging, named entity recognition, document classification)
and further method adapted for math from corpus linguistics
done on texts as methods for computing semantic relatedness.
This would allow us to take participation in the Math
Understanding Task next N T C I R . In this context and in
long term we expect to experiment with Explicit Semantic
Analysis (ESA) [4] adapted to M I R using also math formulae,
connotations and named entities to model semantic
relatedness. We plan to measure its impact on M I R qualities
on a developed reference document and query corpus
for M I R evaluation.
Acknowledgement. We acknowledge the support (Short
and Exchange Visit Grant) received from the European Science
Foundation (ESF) for the activity entitled 'Evaluating
Information Access Systems'.
7. REFERENCES
[1] A . Aizawa, M . Kohlhase, and I. Ounis. NTCIR-10
Math Pilot Task Overview. In Proceedings of the 10th
NTCIR Conference, Tokyo, Japan, 2013. To appear.
[2] V . Dostál. Indexing of Mathematical Texts in the
Digital Mathematics Library (in Czech), Jan. 2009.
Master Thesis, Masaryk University, Brno, Faculty of
Informatics (advisor: Petr Sojka),
https://is.muni.cz/th/72569/fi_m/?lang=en.
[3] D . Formánek, M . Líška, M . Růžička, and P. Sojka.
Normalization of digital mathematics library content.
In J . Davenport, J. Jeuring, C. Lange, and
P. Libbrecht, editors, 24th
OpenMath Workshop,
Ť Workshop on Mathematical User Interfaces
(MathUI), and Intelligent Computer Mathematics
Work in Progress, number 921 in C E U R Workshop
Proceedings, pages 91-103, Aachen, 2012.
http://ceur-ws.org/Vol-921/wip-05.pdf.
[4] E . Gabrilovich and S. Markovitch. Computing
semantic relatedness using wikipedia-based explicit
semantic analysis. In Proceedings of IJCAI '07, pages
1606-1611, San Francisco, C A , U S A , 2007. Morgan
Kaufmann Publishers Inc. http:
//dl.acm.org/citation.cfm?id=1625275.1625535.
[5] M . Líška. Searching Mathematical Texts (in Slovak),
May 2010. Bachelor Thesis, Masaryk University, Brno,
Faculty of Informatics (advisor: Petr Sojka),
https://is.muni.cz/th/255768/fi_b/?lang=en.
[6] M . Líška. Evaluation of Mathematics Retrieval, Jan.
2013. Master Thesis, Masaryk University, Brno,
Faculty of Informatics (advisor: Petr Sojka),
https://is.muni.cz/th/255768/fi_m/?lang=en.
[7] P. Sojka, editor. Towards a Digital Mathematics
Library, Birmingham, U K , July 2008. Masaryk
University, http:
//www.f i.muni.cz/~ soj ka/dml-2008-program.xhtml.
[8] P. Sojka. Exploiting Semantic Annotations in Math
Information Retrieval. In J. Kamps, J. Karlgren,
P. Mika, and V . Murdock, editors, Proceedings of
ESAIR 2012 c/o CIKM 2012, pages 15-16, Maui,
Hawaii, U S A , 2012. Association for Computing
Machinery.
http://doi.acm.org/10.1145/2390148.2390157.
[9] P. Sojka and M . Líška. Indexing and Searching
Mathematics in Digital Libraries - Architecture,
Design and Scalability Issues. In J. H . Davenport,
W. M . Farmer, J. Urban, and F . Rabe, editors,
Proceedings of CICM 2011, volume 6824 of LNAI,
pages 228-243, Berlin, Germany, July 2011.
Springer-Verlag. h t t p :
//dx.doi.org/10.1007/978-3-642-22673-1_16.
[10] P. Sojka and M . Líška. The Art of Mathematics
Retrieval. In Proceedings of the ACM Conference on
Document Engineering, DocEng 2011, pages 57-60,
Mountain View, C A, Sept. 2011. Association of
Computing Machinery.
http://doi.acm.org/10.1145/2034691.2034703.
[11] W . Sylwestrzak, J. Borbinha, T. Bouche, A . Nowiňski,
and P. Sojka. EuDML—Towards the European Digital
Mathematics Library. In P. Sojka, editor, Proceedings
of DML 2010, pages 11-24, Paris, France, July 2010.
Masaryk University, http://dml.cz/dmlcz/702569.
[12] K . Wojciechowski, A . Nowiňski, J. Grimley, and
M . Líška. Public User Interface - Final Release, Jan.
2013. Deliverable D6.5 of E U CIP-ICT-PSP project
250503 E u D M L : The European Digital Mathematics
Library.
[13] K . Wojciechowski, A . Nowiňski, P. Sojka, and
M . Líška. The E u D M L Search and Browsing Service Final,
Jan. 2013. Deliverable D5.3 of E U
CIP-ICT-PSP project 250503 E u D M L : The European
Digital Mathematics Library, revision 1.1
h t t p s : / / p r o j e c t . e u d m l . e u / s i t e s / d e f a u l t / f i l e s /
D 5 . 3 - v l . l . p d f .
Math Indexer and Searcher under the Hood:
History and Development of a Winning Strategy
Michal Růžička
Faculty of Informatics
Masaryk University
Botanická 68a, 602 00 Brno
Czech Republic
mruzicka@mail.muni.cz
Petr Sojka
Faculty of Informatics
Masaryk University
Botanická 68a, 602 00 Brno
Czech Republic
sojka@fi.muni.cz
Martin Líška
Faculty of Informatics
Masaryk University
Botanická 68a, 602 00 Brno
Czech Republic
martin.liski@mail.muni.cz
ABSTRACT
This paper describes and summarizes experience of Masaryk
University Math Information Retrieval team (MIRMU) with
the mathematical search developed and performed for the
NTCIR-11 Math-2 Task. Our approach is the similarity
search based on canonicalized M a t h M L and second generation
of scalable full text search engine Math Indexer and
Searcher (MlaS) with attested state-of-the-art information
retrieval techniques like query expansion. The capability
of MlaS system in terms of math query notation, normalization
and combining math with textual query tokens was
deployed by submitting multiple runs with four query notations
provided, and with results merged from multiple
queries. The analysis of the evaluation results shows that the
system performs best using TgjX queries that are translated
and canonicalized to Content MathML, where MlaS ranked
as #1 for all metrics returning very relevant results.
Team Name
M I R M U (Math Information Retrieval at Masaryk University)
Subtasks
Math-2 Main Task (English) and optional Math-2 Wikipedia
Subtask (English)
Keywords
math, search, similarity search, math information retrieval,
MIR, MlaS, evaluation, math representation and indexing,
math canonicalization, M a t h M L
"Study the past if you would define the future."
Confucius
1. HISTORICAL REMARKS AND MOTIVA­
TION
In the beginning, there was a dream of a global Digital
Mathematical Library (DML). Computer Science and E n gineering
advances showed the possibilities of having all
previous knowledge at fingertips of mathematicians at the
beginning of millennium. Search became ubiquitous, and has
been used as a gate to the digitally stored knowledge in the
digital libraries and on the web.
We started to design solutions for building D M L s in 2005
when the Czech D M L (DML-CZ) was conceived. [15] We
began to develop math-aware workflows to handle digital
content in the form of full texts of hundreds of thousands of
scientific papers. We have realized that math content, and
that holds for the whole S T E M domain, is specific by the
presence of mathematical formulae.
Structured mathematical notation is irreplaceable part
of mathematical vernacular, and it should be supported
when optically recognizing, storing, representing, indexing,
querying, filtering, mining, and linking exponentially growing
mathematical literature. To cover these specifics as topics of
research, specific research forum, workshop series Towards
a Digital Mathematics Library [8], has been set up. In the
D M L proceedings [16] there are already papers tackling mathaware
problems as search [13] and other related issues [22].
It become clear that the whole math-aware workflow [17] has
to be researched.
For the European Digital Mathematics Library (EuDML),
where we have been responsible for searching component, we
designed Math Indexer and Searcher (MlaS) system [25] as
probably the first production quality math-aware indexing
system indexing hundreds of thousands of documents.
Math notation needs to be specifically supported by the
Information Retrieval tools: establishment of Math Information
Retrieval (MIR) research field was necessary. MlaS was
one of two systems at Math IR Happening [19], which took
place at C I C M 2012 conference.
Finally, M I R research attracted several research groups
as Pilot Math Task has been set up at NTCIR-10. MlaS
used for the first time MathML canonicalization module and
Content MathML indexing. [11] A n d for this year, MlaS has
been enhanced with query expansion strategies and better
canonicalization. [14, 2]
The paper is structured as follows: In the Section 2 we
give an overview of our approach used in our MlaS system.
Section 3 describes runs that M I R M U team submitted for
N T C I R Math Task, with scripts used for automation of
querying. In the Section 4 our indexing statistics are revealed.
Results achieved are discussed in the Section 5. We
conclude with summary and directions of further research
and developments in the Section 6.
"God is in the details."
Ludwig Mies van der Rolie
2. OVERVIEW OF MATH INDEXING SOLUTION
MIAS
Main design principles of MlaS system were set aligned with
the awaited deployment in a large D M L s like E u D M L , or even
Global D M L [5]. We designed open, scalable, math formulaeaware
system for ranked document information retrieval, that
goes together with leading edge information retrieval systems
based on textual keywords and collocations.
The main design questions of M I R system like MlaS were:
1. How to collect data and pre-process them into uniform
representation?
2. How to make unambiguous canonical representation of
the semantically same formulae and entities?
3. How to index the data allowing quick relevance evaluation
to the query?
4. How to rank and sort the documents found?
5. What user interface for querying and presenting results
should be used?
Preprocessing
Essence of the problem is to cope with different, heterogeneous
formats and representations of structured mathematical
formulae. Even though most math content is primarily
written in some flavour of TjrjX markup, the markup and
levels of abstractions are very different. For some documents,
only P D F s are available. That means output of different
software for math optical character recognition (OCR), tools
for conversion of born-digital P D F , or even various TjrjX
macropackages needs to be converted and normalized into a
structural tree form of math. We use M a t h M L standard [3]
for this, ideally in both Presentation and Content M a t h M L
shapes. Tools as Infty Reader [24], MaxTract [4], Tralics [7]
and L a T e X M L [23] are used for these tasks in our M I R
system.
Canonicalization
Having formulae expressed in MathML still allows plethora of
ways representing the same formulae. To increase information
retrieval metrics and precision and recall it is necessary to
find a canonical representant for all semantically equivalent
formulae. We have designed, implemented and continually
improve a converter1
for both Presentation and Content
M a t h M L for this task. [6]
The achievement of the full disambiguation of all elements
in a formulae is a big future work task for which knowledge
understanding would be needed, not mentioning flexibility of
natural language to express same or slightly similar things.
Representation of Math for Indexing
Concepts of similarity and distributional representations are
central in the design of M l a S 2
. Every formulae is represented
in the index as a set of weighted tokens (subformulae,
features) that grab both structure and content of indexed
mathematical formulae. The weighting is computed via small
set of rules reflecting similarity distance of indexed tokens
to the original formulae: the more similar is token to the
original (in size, variable naming, constants used, . . . ) , the
higher weighting score is stored in the index for a token. On
average, currently the formulae representation is distributed
over about 30 indexed weighted tokens. [21]
Document Ranking
Main performance metric used at N T C I R is precision (P@l,
P@5, . . . ) . It is hard to use global document rankings as
x
h t t p s : / / m i r . f i . m u n i . c z / m a t h m l - n o r m a l i z a t i o n /
2
h t t p s : / / m i r . f i . m u n i . c z / m i a s /
PageRank in DMLs—thus importance of good 'local' document
ranking, e.g. computation of relevance of query to
matched documents, increases. Given the weighting is done
at the indexing time, at the query time only summation of
similar hits is done, which leads to the good responsiveness
of the system and superb scalability.
User Interface
Acceptance of M I R system by conservative mathematicians
depends also on the user interface. We offer WebMIaS3
user
interface [10], which allows input in both TJrjX and MathML
and on-the-fly rendering for feedback and conversion. [12]
For a more detailed description of all parts of the system
the reader is referred to [20, 21, 18, 9] and web page of our
group h t t p s : / / m i r . f i . m u n i . c z / .
"Reason and free inquiry are the only effectual agents
against error."
Thomas Jefferson
3. AUTOMATIC QUERYING SCRIPTS
To query MlaS engine there is WebMIaS user interface [12],
which offers also web services interface for query automation.
We used it to automate query processing in a novel way this
year.
Availability of the task inputs in the X M L format supplemented
by MlaS web service interface allowed us to fully
automate the task data processing. The batch querying
script read topic specifications from the particular X M L file
and constructed four different X M L queries for the MlaS
web service interface for each of the topics:
P M a t h query The query contained Presentation MathML
representation of the query formulae together with text
keywords.
C M a t h query This query was constructed in the very same
way as the P M a t h query but using Content M a t h M L
representation of the formula instead of the Presentation
M a t h M L part.
P C M a t h query This query combines both Presentation
and Content MathML, i.e. the query is constructed as
a concatenation of the Presentation MathML from the
P M a t h query and Content M a t h M L from the C M a t h
query plus the text keywords.
TgjX The last query is similar to the previous ones but the
TjjX representation was used instead of the M a t h M L .
There was no modification of the Tj^X statement except
for removing linebreaks (as well as removing any
comments and per cent sings (%) protecting these linebreaks)
in case of multiline T E X code. The \qvar-(. . .}
macros were transformed as described in the next paragraph.
Finally, a single dollar sign ($) was added on
both sides of the original statement to properly indicate
T[TX encoded part of the query to the MlaS system.
Handling Query Variables
MlaS system is designed not to depend on hints on variables
from the users in the queries. In fact, these query variable
hints are not supported by the system in the queries. Due to
this fact we had to transform \qvarf_. ..} markup to regular
identifiers.
3
h t t p s : / / m i r . f i . m u n i . c z / w e b m i a s /
Use of \qvar elements varied in different queries. Query
number 1 contained named entities in the \qvar markup
(\qvar-Csquare}, \qvar-Cphi}), query number 2 contained
plus sign in the \qvar markup (\qvar-[+!r), other queries
were using single letter \qvar identifiers (such as \qvar-fL}.
\qvar{k} etc.).
For use of MlaS, \qvar markup was transformed to regular
single letter identifiers simply by keeping only the first letter
from the original \qvar content (i.e. squere —¥ s, + —¥ +.
L —¥ L) and the \qvar macro itself was removed.
The system keeps track of mapping of the original \qvar
name to the single-letter substitute not to use the same
single-letter substitute for two different \qvar names in a
single formula. The next letter in alphabetical order is
used as the substitute if the original one has already been
used to represent a different \qvar name (i.e. l e f t —¥ 1,
lowbound > 1 —¥ m). However, this mechanism was not used
in practise as NTCIR-11 Math-2 Task does not contain \qvar
names colliding on the first letter within a single formula.
In the T ^ X queries, the single letter identifiers were inserted
to the source code to the place of the original \qvar macro
surrounded with single space. In the MathML queries, a new
mi and c i element replaced the \qvar element in Presentation
and Content markup respectively, i.e.
<mws:qvar xmlns:mws="http://search.mathweb.org/ns"
name="square"/>
I
<mi>s</mi>
However, the investigation of our results (see Section 5)
indicates that our system could benefit from some kind of
unification of the queried and indexed formulae. On the other
hand, the unification should be performed by the system
itself with no need of users' hints in the query. Proposal of
a possible simple indexing-time unification is presented in
Section 6.
Query Expansion
Combination of multiple formulae and multiple text keywords
in one query used in NTCIR-11 Math Task seems to be
more consistent with the real situation of a human using
math-aware search engine: formulae are simply a different
expression of keywords used to filter relevant documents from
the whole database. They are complement instrument of
the query specification to the keywords, not the opposite of
them. The queries work best with formulae and keywords
together.
The MlaS system supports this kind of queries natively.
All the parameters are posted to the system in one text field—
formulae are written in M a t h M L or T E X notation with a
dollar sign ($) added on both sides of the T E X formulae.
Keywords, sometimes consisting of more than one word,
were surrounded with single quotation mark (") to handle
multi-word keywords as a single entity. Formulae and text
keywords were separated by a single space.
Internally, we are expanding the original query further to
increase recall on very specific queries with no or just minimal
number of results found. More specifically, the original query
consisting of k keywords and / formulae is used to generate a
set of 'subqueries'. At first, the original query is used. Then
subqueries are generated one by one removing the keywords
from the query until the query consists of / formulae only.
The rest of subqueries are generated with all the keywords
but formulae are removed from the query one by one until
the query consisting of k keywords only is reached.
A n example of the complete 'subqueries' generation sequence
for a query consisting of two formulae (denoted fx)
and three keywords (denoted ky) is shown in Example 1.
subquery 1 (the original query): h h fci k-2 fc3
subquery 2: h h fci k-2
subquery 3: h h fci
subquery 4: h h
subquery 5: h fci k-2 fc3
subquery 6: fci k-2 fc3
Example 1: Complete sequence of subqueries derived
from the original user's query
All the queries are one by one used to ask the system and
the results lists of the subqueries are merged (see the next
Section) to the final result list that is presented to the user.
Statistics of the relative number of results found using each
of the subqueries in the MlaS most successful CMath run are
shown in Figure 1. Every subquery was limited to at most
1,000 results as requested in the NTCIR-11 Math Task. The
graph shows that the use of the original unmodified query
usually resulted in much less than requested 1,000 results.
The use of the results of multiple subqueries thus provides
significantly more results that are (at least partially) relevant
to the users' query.
Please note that the last subquery does not contain any
formulae, i.e. subquery 6 in Example 1, is standard full text
search keyword query with no involvement of mathematical
elements whatsoever.
Please also note that this algorithm does not cover all
the possible combinations of keywords and formulae as well
as 'unreasonably' handle different formulae differently—in
Example 1 formula fi is used in five subqueries in contrast
to four uses of /2. The simplification was used to keep the
number of subqueries small enough to reach an acceptable
response time even for interactive human users of the search
system as the total number of subqueries would increase
rapidly with the number of formulae and keywords in the
query if all their possible combinations should be used.
Length of MlaS searches for the most successful CMath run
are shown in Table 1. Cumulative total MlaS search time for
all 50 queries in CMath run was f0.8f seconds. Cumulative
totals for other three runs are comparable: P M a t h 12.01 s,
P C M a t h 14.70 s and for TeX 19.83 s.
This kind of query expansion provide users with results
on more general queries than the user originally posted. We
consider this behavior useful especially for 'research' search
as this shows the user wider context of the query that could
possibly reveal new and unexpected connections and paths
to follow in the research.
Merging of Results
Every subquery results in an ordered list of items with score4
assigned to each of the results. However, these scores are only
comparable within the context of the result list. That means
that a result r i with score 0.25 from the subquery 1 is not
necessarily more relevant to the subquery 1 than a result T2
with score 0.15 from the subquery 2 even though 0.25 > 0.15
4
Measure of relevance to the query.
Table 1: C M a t h run querying statistics
The percentage of ITS nil s icl miicd by imli ddiiiil sutxjucrics
• Original Query • Subquery 1 Subquery 2 • Subquery 3
• Subquery 1 Subquery 5 • Subquery (
> Subquery 7
Figure 1: Relative number of results found using
different subqueries for every query in C M a t h run
Query
ID
Number of
Subqueries
Subquery R.esp. Time [ms] Query R..
Time [ms]
Query
ID
Number of
Subqueries Avg. Min. Max.
Query R..
Time [ms]
01 5 33.20 28 38 166
02 4 31.75 21 46 127
03 4 33.25 26 49 133
04 5 48.80 30 82 244
05 5 43.20 33 57 216
06 5 48.40 32 73 242
07 6 41.67 31 59 250
08 4 37.50 31 51 150
09 4 34.50 13 54 138
10 6 42.33 29 55 254
11 3 34.67 29 44 104
12 4 59.75 38 76 239
13 4 98.50 52 165 394
14 4 33.00 28 44 132
15 4 40.75 27 54 163
16 3 43.67 39 46 131
17 4 31.00 13 45 124
18 5 34.40 25 51 172
19 4 37.25 32 52 149
20 4 31.00 29 33 124
21 4 34.50 28 42 138
22 4 43.00 30 59 172
23 5 58.40 45 78 292
24 5 43.60 27 63 218
25 6 51.83 29 119 311
26 3 32.67 6 54 98
27 6 40.83 28 65 245
28 5 316.40 117 428 1582
29 5 39.20 31 53 196
30 5 149.20 126 179 746
31 5 37.40 31 50 187
32 4 31.00 25 45 124
33 4 26.50 14 31 106
34 4 34.50 29 46 138
35 4 35.00 29 49 140
36 4 45.50 31 59 182
37 4 49.25 29 82 197
38 4 38.00 28 48 152
39 3 23.00 10 31 69
40 4 40.25 32 51 161
41 4 40.00 31 52 160
42 3 35.67 29 48 107
43 4 35.25 17 50 141
44 4 26.25 8 33 105
45 3 29.00 27 30 87
46 4 45.75 36 56 183
47 4 34.50 17 55 138
48 8 52.75 32 138 422
49 4 38.50 18 54 154
50 5 41.00 32 62 205
<all> 218 49.58 6 428 10808
as absolute scores are incomparable across subquery 1 and 2
results lists. Thus, it is not possible to generate final results
list as a simple combination of results from all the subqueries
ordered by the score.
Another reason to use a more complicated results merging
procedure is a necessity of preference of results on the original
user's query to the results found for subqueries. On the other
hand, it is well possible that the first result of a subquery
could be more relevant for the user than the 10th result on
the original query.
To produce the final results list from the subqueries according
to this hypothesis we used a method we refer to as
'strip-merging' of the results. The main idea is interleaving
of 'strips' of results from all the ordered results lists from
the subqueries. The less modified subquery to the original
query the 'wider' strip of results on more relevant position is
used in the final result list.
Let us have x subqueries (the original one and x — 1 derived
subqueries). The top x most relevant results in the final result
list are the first x most relevant results from the result list to
the original query, then x — 1 most relevant results from the
first derived subquery are added, then x — 2 results from the
second subquery and so on until the first most relevant result
from the last derived subquery is added. This procedure is
then repeated with the next x results from the result list to
the original query, x — 1 results from the first subquery etc.
until desired amount of results is reached. If all the results
from some subquery are used and no more left we continue
without changing the width of strips for other subqueries.
In the NTCIR-11 Math Task exactly 1,000 results were
demanded for each of the queries. Provided all the subqueries
together did not provide us with this number of results then
a random selection from the database of indexed documents
was used to fill in the gap. Score for all these artificial results
in the subquery results lists was the same: 0.00000000001
This constant was selected as sufficiently small not to outnumber
any real result score.
Strip-merging on three subqueries (the original one and
two derived subqueries) is demonstrated in Example 2.
Results of the original query:
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
original
original
original
original
original
'original
original
'original
original
The final result list:
r
^original
2
' r 2
original
3: r3,
4: rl
original
subquery 1
r 2
subquery 1
r
l subquery 2
r9.
rlO,
r l l
7: r4
8: r5
9: r6
original
original
original
original
original
Results of the subquery
^: r
1sub query 1
2 : r 2
subquery 1
10. i
" 3 g u i ; ) q U e r y 2
^subquery 1
1 2 : r 2
subquery 2
13. f"7o r jgm a ]
'original14
15: r9,
'subquery 1
subquery 1
'subquery 1
Results of the subquery 2:
subquery 2
subquery 2
subquery 2
subquery 2
subquery 2
original
16. r
" 5 g u i ; ) q U e r y 2
N o m o r e r e s u l t s f r o m s u b q u e r y 1.
17: r
" 3 s u i ; ) q U e r y 2
18. r
10O riginal
19. r
l l 0 r i g i n a l
N o m o r e r e s u l t s f r o m t h e o r i g i n a l <
20. r
" 4 g u i ; ) q U e r y 2
21. r
" 5 s u i ; ) q U e r y 2
N o m o r e r e s u l t s f r o m s u b q u e r y 2 .
2 2
• r
^random
23. ? " 2 r a n ( : j o m
1000: r 9 7 9 r a n d o m
Example 2: Strip-merging of results from three sub-
queries
Relevance scores from the subqueries are mutually incomparable
for two results from different subqueries. Moreover,
strip merging may not preserve score and rank consistency,
i.e. ranki < rank,- iff scorei < scorej. Thus, scores in the final
result list are not directly usable and have to be recomputed.
The score of the result in the final result list is computed
as
score = maximumScore • (targetNumberOfResults —
— (resultNumber — 1)) + scorelnSubquery
where
• maximumScore is ceiling on the highest score of a result
across all the subquery results lists,
• targetNumberOfResults is the desired number of results
in the final results list,5
• resultNumber is rank of the result in the final result
list, and
• scorelnSubquery is the original score of the result in
the subquery result lits.
Scores computed in this way certainly retains the property
of consistency of rank and score mentioned above.
"There are three types of lies—lies, damn lies, and statistics."
Benjamin Disraeli
4. INDEXING STATISTICS
N T C T R - l l Math Task dataset consists of around 100,000
documents divided into single paragraphs for better evaluation
purposes. We think this is a good way of keeping the
search and evaluation units at a reasonable size as well as
the number of documents in the collection. As opposed to
single-formula documents from NTCIR-10, the NTCIR-11
single-paragraph documents enable searchers to combine
formula queries with text queries as well.
For the dataset we created an index with a little more than
3 billion indexed subformulae. Indexing process comprises
of reading the source documents from a hard drive, parsing
the X M L , separating math content from textual content,
analyzing and indexing textual content, canonicalization
of mathematical notation, normalization of formulae and
extraction of subformulae, and finally, putting all to the
index.
The complete index statistics can be found in Tables 2
and 3.
Table 2: Index statistics
Indexing times [min] Index
size [GiB]Wall Clock C P U
Index
size [GiB]
1,940.0 3,413.55 68
Table 3: Formulae count statistics
Documents
Formulae
Documents Original Indexed
8,301,545 59,647,566 3,021,865,236
3
1,000 for NTCIR-11 Math Task.
In our previous research we have already observed that the
indexing statistics of MlaS such as indexing time and index
size are more dependant on the number of math formulae in
the collection than on the number of documents. This is confirmed
by the above numbers with comparison to NTCIR-10
MlaS data [11]. Nearly twice as many formulae in the dataset
means almost exactly twice as many number of indexed documents
as well as doubled C P U indexing time and final index
size. Wall clock time is incomparable to the previous results
due to the different indexing job management.
These performance results we find satisfying taking the extra
overhead caused by the extended canonicalization process
as well as the precision of the results into account.
"There is only one thing that makes a dream impossible
to achieve: the fear of failure."
Paulo Coelho
5. DISCUSSION OF ACHIEVED RESULTS
The result of all runs submitted by M I R M U team can be
found in Tables 4 and 5. The highest scores of our submitted
runs of all teams are highlighted in bold—our system got
the best results of all teams in 4 out of 6 evaluated categories
but more importantly, we has achieved the best score of all
teams in the evaluation of results with Relevance Level > 3.
PMath run based solely on Presentation MathML reached
the lowest precision from our runs. Nevertheless, the average
ratio between P M a t h run and C M a t h run raised from
0.64 in NTCIR-10 to 0.90 in the current evaluation. This
is thanks to the constant development of our open-source
Table 4: Results of submitted runs with Relevance
Level > 3 (Relevant). Main task team rank is in [ ]
for our best runs (in bold).
P M a t h C M a t h P C M a t h TßX
M A P avg 0.3073 0.3630 1 0.3594 0.3357
P@10 avg 0.3040 0.3520 1 0.3480 0.3380
P@5 avg 0.5120 0.5680 1 0.5560 0.5400
Table 5: Results of submitted runs with Relevance
Level > 1 (Partially Relevant). Number in [ ] is team
rank of all runs.
P M a t h C M a t h P C M a t h Tfc]X
M A P avg 0.2557 0.2807 [2] 0.2799 0.2747
P@10 avg 0.5020 0.5440 0.5520 [1] 0.5400
P@5 avg 0.8440 0.8720 [2] 0.8640 0.8480
standalone MathML Canonicalizer tool (see Section 2) which
is an important preprocessing step in the indexing as well as
searching phase of search. [6]
During the investigation of our results we have found
several 'classes' of problems that are root of search engine
failure.
Realistic User Query Formulation Problem
In the particular case the user was looking for formulae
containing operator Im. However, this was not properly
specified in the user's query.
Index: \operatorname{Im}P~{+}_{\Gamma}=C_{\mu}~{+}(\Gamma)
ImP+ = C+(r)
Query: ImP"f+}_{\gamma}=C"{+}_f\mu}(\gamma)
ImP2 : C+(7)
Index
<mrow>
<mo>Im</mo>
<!— U+2061 FUNCTION APPLICATION —>
<mo>&#x2061;</mo>
<msup>
Query
<mrow>
<mi>K/mi>
<mi>m</mi>
<msup>
This caused misinterpretation of the letters 'Im' to be
multiplication of two variables I and m. With this query no
matching formula was found even though suitable formula
with \operatorname-Clm} was in the index of the system.
It is unclear whether similar situations can be properly
and easily handled by the system. Some kind of unification
could be helpful: see proposal of possible simple unification
for MlaS system in Section 6.
Substructure Difference Problem
The unification could possibly be helpful also in other situations
where the query differs from the indexed formulae only
in some of the subtrees.
Example 1
The following examples illustrate particular cases where the
current version of MlaS missed the match even though the
query and indexed formulae share large portions of code.
<mrow>
QUERY-FORMULA-SUBPART-1
[[ INDEX
<mrow>
<mo>\int</mo>
<mrow>
I I QUERY
<mi>o</mi>
] ]
QUERY-FORMULA-SUBPART-2
INDEX-FORMULA-SUPPLEMENT
</mrow>
</mrow>
</mrow>
</mrow>
Example 2
In the following example MlaS matches on complex formula
with commutativity applied. However, more simple formula is
not found due to difference in the complexity of the nominator
and denominator in the query and indexed formulae:
Original task query:
\qvar{x}\frac{\qvar{y}H\qvar{z}}
-\qvar{u}\fracf\qvarfv}}{\qvar{w}}
Matches:
{is, qr} jdxj dy{A{x,ßY,A{y,uY}
pqßv J dxA(p)p
(A(u)q
Y
Does not match:
1 Irs
P 1 J P-v hpq
Spc SHOBC
C ~ Cl C2 —
pa "ose
Query Variables Problem
Original task query:
\qvar{S}=-\qvar{T}_{\qvar{p}}\int\qvar{d}~{\qvarfp}+l}
\qvar{x}\sqrt{\qvar{g}}
Index: S=-T_{p}\int d~{p+l}x\sqrt{-g}
S = -Tp J dP+1
x^j
Query: S=-T_{p}\int d~{p+l}x\sqrt{g}
S — Tv
rpJ d»+l
xVg
MlaS missed the hit only due to the tiny difference between
\sqrt{g} and \sqrt{-g}.
"The future belongs to those who believe
in the beauty of their dreams."
Eleanor Roosevelt
6. CONCLUSIONS AND FUTURE WORK
We have described the story of MlaS leading to the performance
we are getting now for keyword based textual
and formulae search. We indexed canonicalized version of
M a t h M L , both Presentation and Content M a t h M L . Best
'winning' results have been achieved with Content Math representation
of data. Our explanation is that with Content
M a t h M L there is smaller degree of ambiguity than with
Presentation M a t h M L . We have described and evaluated
our query expansion and merging strategy, which definitely
helped to reach the best results.
The achieved performance allows the system to be used in
real digital libraries as E u D M L to the benefit of math-aware
information seekers. Still, there is a long route to mathaware
question answering and we still see large possibilities
for improvements and optimizations of efficiency.
Further investigation of the best strategies of subqueries
derivation from the original users' query is needed as well as
proper evaluation of different strategies of merging subqueries
results to the final result list.
In this context and in the long term we plan to experiment
with Strict Content MathML, W 3 C subset of Content
MathML. Supporting it in our canonicalization process may
further decrease ambiguity in formulae indexing and retrieval.
Another area of future research is what we call 'Math
Entailment'. Textual entailment is directional relation between
two fragments, text t and hypotheses h. t entails h
if human would from t infer that h probably holds. Math
entailment is entailment adapted to M I R by the usage of
math formulae, connotations and named entities for t or h
to model semantic relatedness or weighting similarity during
indexing. We plan to measure its impact on M I R qualities
on an available N T C I R evaluation database or developed
reference document and query corpus for M I R evaluation.
It would also be useful to implement simplified version of
unification in our system. W i t h query-time complexity in
mind we would like to implement and do simple unification
at indexing time as follows:
• The main idea is to implement a special identifier, let
denote it [U|, working as a single universal unifying
element through the whole index.
• The symbol [UJ would be used to derive a set of unified
versions of formulae from the original formula.
The derived versions are generated 'layer-by-layer' according
to the MathML tree structure by substituting
subtrees for [UJ. For example:
— Original formula:
a~2+\fracAsqrt{b}Hc}
a2
+ ^ +
Sequence of the unified formulae derivation:
a~2+\f rac-C\sqrt-f_\unif icator]-Hc}
\ u n i f i c a t o r ~ \ u n i f i c a t o r
+\f rac-f_\unif i c a t o r H V i n i f icator}
msup mfrac
\ u n i f i c a t o r + \ u n i f i c a t o r
ED + ED
• This expansion of the original formula would be applied
to every formula during the indexing of the database
of documents. The same method would also be used
to expand every formula in the user's query to extend
the original query. Hits on unified formulae would be
rated with gradually decreased score according to the
unification level of the formula.
This approach does not cover all the possible substitutions
on the formula tree. However, even this approach significantly
increases probability of the query match on structurally similar
formulae with reasonable amount of additional processing
during indexing and just minimal addition of complexity
during querying. The increase in index size would also be
acceptable.
Acknowledgement. We would like to thank David Formanek
for the first idea of the simple unification for MlaS.
We acknowledge the support (Short and Exchange Visit
Grants 6965 and 6967) received from ESF, European Science
Foundation, for the activity entitled E L I AS—Evaluating
Information Access Systems.
7. REFERENCES
[1] NTCIR Workshop 11 Meeting, Tokyo, Japan, 2014.
[2] A . Aizawa, M . Kohlhase, I. Ounis, and M . Schubotz.
NTCIR-11 Math-2 Task Overview. In Proceedings of
NTCIR-11 Math-2 task Workshop Meeting [1].
[3] R. Ausbrooks, S. Buswell, D. Carlisle, G. Chavchanidze,
S. Dalmas, S. Devitt, A . Diaz, S. Dooley, R. Hunter.
P. Ion, M . Kohlhase, A . Lazrek, P. Libbrecht, B . Miller,
R. Miner, C. Rowley, M . Sargent, B . Smith, N . Soiffer,
R. Sutor, and S. Watt. Mathematical Markup
Language (MathML) Version 3.0, 2010. W 3 C
Recommendation 21 October 2010, http:
//www.w3.org/TR/2010/REC-MathML3-20101021/.
[4] J. B . Baker, A . P. Sexton, and V . Sorge. MaxTract:
Converting P D F to IATgX, M a t h M L and Text. In
J. Jeuring, J. A . Campbell, J. Carette, G. D. Reis,
P. Sojka, M . Wenzel, and V . Sorge, editors,
AISC/DML/MKM/Calculemus, volume 7362 of Lecture
Notes in Computer Science, pages 422-426. Springer,
2012.
[5] T. W. Cole, I. Daubechies, K . M . Carley, J. L. Klavans,
Y . LeCun, M . Lesk, C. A . Lynch, P. Olver, J. Pitman,
and Z. J. Xia. Developing a 2,1st Century Global
Library for Mathematics Research. National Research
Council, Washington, D . C : The National Academies
Press, Mar. 2014.
[6] D. Formánek, M . Líška, M . Růžička, and P. Sojka.
Normalization of digital mathematics library content.
In J. Davenport, J. Jeuring, C. Lange, and
P. Libbrecht, editors, 24th
OpenMath Workshop,
7* Workshop on Mathematical User Interfaces
(MathUI), and Intelligent Computer Mathematics Work
in Progress, number 921 in C E U R Workshop
Proceedings, pages 91-103, Aachen, 2012.
http://ceur-ws.org/Vol-921/wip-05.pdf.
[7] J. Grimm. Producing M a t h M L with Tralics. In
P. Sojka, editor, Proceedings of DML 2010, pages
105-117, Paris, France, July 2010. Masaryk University,
http://dmi.cz/dmlcz/702579.
[8] J. Hoffman. Starting small but adding up: a free maths
archive. Nature, 454:263, 2008. http://www.nature.
com/news/2008/080716/full/454263b.html.
[9] M . Líška. Evaluation of Mathematics Retrieval, Jan.
2013. Master Thesis, Masaryk University, Brno, Faculty
of Informatics (advisor: Petr Sojka),
https://is.muni.cz/th/255768/fi_m/?lang=en.
[10] M . Líška, P. Sojka, M . Růžička, and P. Mravec. Web
Interface and Collection for Mathematical Retrieval:
WebMIaS and M R E C In P. Sojka and T. Bouche,
editors, Towards a Digital Mathematics Library.
Bertinoro, Italy, July 20-21st, 2011, pages 77-84.
Masaryk University, July 2011.
http://hdl.handle.net/10338.dmlcz/702604.
[11] M . Líška, P. Sojka, and M . Růžička. Similarity Search
for Mathematics: Masaryk University team at the
NTCIR-10 Math Task. In N . Kando and K . Kishida,
editors, Proceedings of the 10th NTCIR Conference on
Evaluation of Information Access Technologies, pages
686-691, Tokyo, 2013. National Institute of Informatics,
2-1-2 Hitotsubashi, Chiyoda-ku, Tokyo 101-8430 Japan,
http://research.nii.ac.jp/ntcir/workshop/
OnlineProceedingslO/pdf/NTCIR/MATH/
06-NTCIR10-MATH-LiskaM.pdf.
[12] M . Líška, P. Sojka, and M . Růžička. Math indexer and
searcher web interface: Towards fulfillment of
mathematicians' information needs. In S. M . Watt,
J. H . Davenport, A . P. Sexton, P. Sojka, and J. Urban,
editors, Intelligent Computer Mathematics CICM 2014Proceedings
of Calculemus, DML, MKM, and Systems
and Projects, pages 444-448, Zurich, 2014. Springer
International Publishing Switzerland, http:
//dx.doi.org/10.1007/978-3-319-08434-3_36.
[13] J. Mišutka and L. Galamboš. Extending Full Text
Search Engine for Mathematical Content. In Sojka [16],
pages 55-67. http://dml.cz/dmlcz/702546.
[14] M . Růžička, P. Sojka, and M . Líška. Math Indexer and
Searcher under the Hood: History and Development of
a Winning Strategy. In Proceedings of NTCIR-11
Math-2 task Workshop Meeting [1].
[15] P. Sojka. From Scanned Image to Knowledge Sharing.
In K . Tochtermann and H . Maurer, editors, Proceedings
of I-KNOW '05: Fifth International Conference on
Knowledge Management, pages 664-672, Graz, Austria,
June 2005. Know-Center in coop, with Graz Uni,
Joanneum Research and Springer Pub. Co.
[16] P. Sojka, editor. Towards a Digital Mathematics
Library, Birmingham, U K , July 2008. Masaryk
University, http://dmi.cz/dmlcz/702564.
[17] P. Sojka. Digitization Workflow in the Czech Digital
Mathematics Library. Math-for-Industry Lecture Note
Series, 22:272-280, Dec. 2009.
[18] P. Sojka. Exploiting Semantic Annotations in Math
Information Retrieval. In J. Kamps, J. Karlgren,
P. Mika, and V . Murdock, editors, Proceedings of
ESAIR 2012 c/o CIKM 2012, pages 15-16, Maui,
Hawaii, U S A , 2012. Association for Computing
Machinery.
http://doi.acm.org/10.1145/2390148.2390157.
[19] P. Sojka and M . Kohlhase, editors. Towards a Digital
Mathematics Library: MIR and DML 2012. Masaryk
University, Dec. 2014. to appear.
[20] P. Sojka and M . Líška. Indexing and Searching
Mathematics in Digital Libraries - Architecture, Design
and Scalability Issues. In J. H . Davenport, W . M .
Farmer, J. Urban, and F. Rabe, editors, Proceedings of
CICM 2011, volume 6824 of LNA I, pages 228-243,
Berlin, Germany, July 2011. Springer-Verlag. http:
//dx.doi.org/10.1007/978-3-642-22673-1_16.
[21] P. Sojka and M . Líška. The Art of Mathematics
Retrieval. In Proceedings of the ACM Conference on
Document Engineering, DocEng 2011, pages 57-60,
Mountain View, C A, Sept. 2011. Association of
Computing Machinery.
http://doi.acm.org/10.1145/2034691.2034703.
[22] P. Sojka and J. Rákosník. From Pixels and Minds to the
Mathematical Knowledge in a Digital Library. In Sojka
[16], pages 17-27. http://dml.cz/dmlcz/702564.
[23] H . Stamerjohanns, D. Ginev, C. David, D. Misev,
V. Zamdzhiev, and M . Kohlhase. MathML-aware
Article Conversion from DTj^jX. In P. Sojka, editor,
Proceedings of DML 2009, pages 109-120, Grand Bend,
Ontario, C A , July 2009. Masaryk University.
http://dml.cz/dmlcz/702561.
[24] M . Suzuki, F. Tamari, R. Fukuda, S. Uchida, and
T. Kanahori. I N F T Y — A n integrated O C R system for
mathematical documents. In C. Vanoirbeek, C. Roisin,
and E. Munson, editors, Proceedings of ACM
Symposium on Document Engineering 2003, pages
95-104, Grenoble, France, 2003. A C M .
[25] K . Wojciechowski, A . Nowiňski, P. Sojka, and M . Líška.
The E u D M L Search and Browsing Service - Final, Feb.
2013. Deliverable D5.3 of E U CIP-ICT-PSP project
250503 E u D M L : The European Digital Mathematics
Library, revision 1.2 https://project.eudml.eu/
sites/default/files/D5_3_vl.2.pdf.
Math Indexer and Searcher Web Interface
Towards Fulfillment of Mathematicians' Information Needs
Martin Liška, Petr Sojka, and Michal Růžička
Masaryk University, Faculty of Informatics, Botanická 68a, Brno, Czech Republic
martin.liskiOmail.muni.cz, sojkaOfi.muni.cz, mruzicka@mail.muni.cz
WWW: h t t p s : / / m i r . f i . m u n i . c z /
Abstract. We are designing and developing a web user interface for digital
mathematics libraries called WebMIaS. It allows queries to be expressed by
mathematicians through a faceted search interface. Users can combine standard
textual autocompleted keywords with keywords in the form of mathematical
formulae in M g X or MathML formats. Formulae are shown rendered by the web
browser on-the-fly for users' feedback. We describe WebMIaS design principles
and our experiences deploying in the European Digital Mathematics Library
(EuDML). We further describe the issues addressed by formulae canonicalization
and by extending the MlaS indexing engine with Content MathML support.
Keywords: search interface; math-aware search; digital mathematical library;
formulae canonicalization; WebMIaS; MlaS; EuDML; MathML
1 The Need for a Math-Aware Search Interface
Scalable search facilities now have the status of killer application on the web and are in
high demand among the users of digital mathematics libraries (DML). There are some
papers in D M L s which contain more formulae than words. With this in mind, we are
designing and implementing the math-aware search engine, Math Indexer and Search
(MlaS) [8] supporting a presentation form of mathematics, since the vast majority of
scholarly literature in math has only been available in optically recognized presentation
formats.
MlaS has been developed primarily for use in E u D M L [1]. Since there is no established
math-aware user interface, we were faced with the task of designing and
implementing one. To gain acceptance across the wider community of potential D M L
users, the main design goal was ease of use. Having the entry barrier as low as possible
is important for attracting new users.
The only available formulae search which does not have format of sources of documents
under control was LaTeXsearch. com interface by Springer. It allows only one
DTpX formula as a query. A s the same formula can be written in many ways in TpX,
string hashing is used to match the query with formulae in documents written in LTpX.
While most mathematicians are used to writing a query in KTpX, there are problems with
this approach as formulae similarity cannot be defined as a metric on LTpX formulae
strings. Other qualities of formulae, such as their structure should be taken into account,
as well as textual phrases denoting the content sought. Furthermore, allowing users to
type longer LTpX formulae with immediate visual feedback simplifies the use.
For E u D M L , we have added on-the-fly rendering of math, as autodetected in DTpX
and MathML formats. We have added facets for searching in different document fields [6].
Most importantly, we have had the privilege of mining E u D M L search logs for user
2 Martin Líška, Petr Sojka, and Michal Růžička
search scenarios which has shown how users have striven to find the information they
require. For example, an interesting observation was that Content MathML has started to
appear in the math search box. New I^TgXML converter [4] allows the development of
new corpora of math texts with math representation in both Presentation and Content
MathML, an example of which is the database available for NTCIR-10 Math Task [5]
(100,000 arXiv documents). The most challenging problems have included the normalization
of math notations coming from different sources, typically a typed or copy-pasted
query, and heterogeneous document formats. Development of a robust math canonicalizer
emerged as a must for the success of the new math search paradigm to be supported
by the D M L search user interface.
2 User Interface for Math Information Retrieval
Users are accustomed to forming search strategies with minimal effort using words as
queries for documents represented as bags of words. For E u D M L we have designed an
advanced search form h t t p . / / e u d m l . o r g / s e a r c h
to allow faceted searches with one facet designed for inputting math formulae. On
h t t p : / / m i r . f i . m u n i . c z / w e b m i a s
we maintain a link to the latest version of the development version of WebMIaS to
discuss possible D M L users' search migration paths and strategies, and to get feedback
from the user community. The WebMIaS search interface in Figure 1 observes several
design principles and qualities:
formulae in TgX Mathematicians know and use compact DTJ3X math notation. Autodetection
of MathML is also in place. To convert DTr-X queries into MlaS-supported
MathML, we switched the converter from Tralics to DTJ3XML, which is able to
convert the user input into mixed Presentation-Content MathML.
on-the-fly formulae rendering Formulae rendering allows quick feedback when writing
the query—users know what they want when they see it. Robust live rendering
of copy-pasted MathML is provided means of MathJax. Users are also warned when
writing an invalid TgX query.
pop-up help Pop-up windows inform users about the interface.
domain-specific auto-completion Frequent collocations and terms from the D M L domain
are suggested for text queries.
facets Adding facets allows natural filtering (by language, author,...) of search results
to achieve high precision.
snippets with query coloring Snippets are shown in hit lists. Matched words and formulae
are colored in the snippets for a quicker first look evaluation of the results.
scoring and debugging Scoring of computed relevance to a query is shown for every
hit. In the development interface, one can deduce document score computation.
Mining the E u D M L and WebMIaS query search logs reveals quite different, often
contradictory user demands. While some users prefer exact searches of visually remembered
formulae, others demand semantic specification of terms representing them. For
example, we got a request to constrain a search to E = mc2
, where m represents mass.
The first request could be fulfilled by an exact Presentation MathML retrieval. However,
the latter needed semantic tagging which is usually absent in full-text X M L s and may
only be approximated by indexing disambiguated Content MathML.
Math Indexer and Searcher Web Interface
WEBMIaS
Any field
Contains, the folio-.-.incj formula
Rendered: k/H0
: 16, showing 1-16 . Cor 2-5 ^s Total s
... where iit = k/H* and ... , f l m = CfH* . and ... Exact solutions of embedding the 4D Univ 3nifoId ... Presided Hi
Search using: | presentation and conte
Search in: MTCIR-0
d a jerfect fluid with density
3 ?r: v _ a : : :e j e y ™ ? . : z-"s " - a a d •. -:=:a: "a ^:=se-z "s:e " :;:-::"de"sa:&s
: '4 .ci1 ^•-• ^ruil-. <"-•-/?• tc :e Hie •• •• riant teeter determining the variation of giant vor
the oscillation frequency slows and approaches the value of the :\-s::' --. si :'- izi :~ :
Bose-Einstein Condensates ...
score = 0.538276G
fO76410.xhtml - cached XHTML
~i::ji: i:q [.a :)'?,s£s j ' d : " , a : ' q s:?,:ss ::;
5i:S6-E -~s:s ~ ii:-'ds~sa:ss
•n frequencies. ... [larger g/flj } th
-2* (f)/(<w):
' - i ^ ? ' : : :.. J: •: ;:S:t:; ;f "use-Einstein conderand the detection of
score = 0.29080945
f027503.xhtml -cacl
sthe large density along tf
:hed XHTML
ZVJS'S -:' 5;:se-z ~s:s - Zi~fe~si:.z - :~s - ' s s s - " s D s:--
d5...
— = — — — .... Expansion of a Bose-Einstein Condensate in the Presence of Diso
score = 0.23334973
0.xhtml - cached XHTML
Fig. 1. WebMIaS user interface
fa;i:lly nit ith iicreasin^ sore sirs
;c ••e/.hst surprisingly, tf"
For testing the search behaviour we indexed 100,000 math papers from the NTCIR-10
Math task [7]. To formulate queries containing math, it emerged that new strategies
will have to be developed. It can be expected that it will take some time before math
search users learn them. To find the balance between word and math search and between
exact, proximity and subtree search, several MlaS indexing parameters have to be set.
These parameters differ from collection to collection. Currently set parameters are being
evaluated for the current collection.
As MathML created by different content generators such as InftyReader, Tralics, or
LATpXML differ significantly. To prevent the rapid growth of the math index containing
mathematical formulae [8], their canonical representations with the same meaning need
to be chosen and indexed. As the results produced by available normalization tools for
M a t h M L were not reliable enough, we concluded that it was necessary to develop our
own normalization tool that would become part of both indexing and searching in the
(Web)MIaS system [2].
To help us to see the changes made by the normalization tool we are generating
H T M L reports of its inputs and results. Samples of these reports are available for a D M L CZ
paper. The KTgX source code of the paper was transformed to X H T M L + M a t h M L by
several tools. Examples of normalized MathML can be seen for Tralics and LATpXML1
.
When querying using math formulae [3] one has to decide on the formulae similarity
metrics to allow not only exact formulae matches. Subformulae, formulae expressed in
https://mir.fi.muni.cz/mathml-normalization/samples/
4 Martin Líška, Petr Sojka, and Michal Růžička
different notation or even similar formulae with different variables need to be considered
as hits with lower scores. These metrics are used for weighting similar formulae in
documents in the same way that term frequency is used for weighting standard word hits.
The link to the WebMIaS interface provided above also shows our development tools
that allow us to debug MlaS indexing and querying. With the verbose output enabled,
the computation process of document scores can be inspected to see how words and
(sub)formulae affect the ranking. The option to take only Presentation M a t h M L , only
Content MathML or both into account is also available. Even though Content MathML
may give better, semantically related results most of the time, there are cases where
visual fidelity is sought and Presentation MathML is preferred.
In addition to the web user interface, it is also possible to use WebMIaS remotely via
web services: its general usage is described in the OpenSearch standard. Details of API
and WebMIaS OpenSearch description document can be found on the WebMIaS home
page above. The web services are particularly useful for remote automated searching, as
for example, for the purposes of system evaluation or for a programmable search.
3 Conclusions and Future Work
We have described the WebMIaS math-aware user interface designed to allow searching
D M L s with keyword and formulae faceted searching. It has been applied in the E u D M L
project to the users' satisfaction. Further deployment of the WebMIaS user interface is
in preparation for further D M L s as D M L - C Z or arXiv.
Acknowledgements This work has been financed in part by the EU through its Competitiveness
and Innovation Programme (Information and Communication Technologies Policy Support
Programme, "Open access to scientific information", Grant Agreement No. 250503).
References
1. Borbinha, J., Bouche, T, Nowiňski, A., Sojka, P.: Project EuDML—A First Year Demonstration.
In: Davenport, J.H., Farmer, W.M., Urban, J., Rabe, F. (eds.) Intelligent Computer Mathematics.
Proceedings of CICM 2011. LNAI, vol. 6824, pp. 281-284. Springer-Verlag, Berlin, Germany
(Jul 2011), http: / / d x . d o i . org/10.1007/978-3-642-22673-1_21
2. Formánek, D., Líška, M., Ružička, M., Sojka, P.: Normalization of digital mathematics library
content. In: Davenport, J., et al. (eds.) 24t h
OpenMath Workshop, 7t h
MathUI Workshop, and
Intelligent Computer Mathematics Work in Progress, pp. 91-103. No. 921 in CEUR Workshop
Proceedings, Aachen (2012), http://ceur-ws.org/Vol-921/wip-05.pdf
3. Kamali, S.: Querying Large Collections of Semistructured Data. Ph.D. thesis (advisor: Frank
Tompa), University of Waterloo (2013)
4. LaTeXML Project: A FáTpX to X M L Converter (2014), http: //dlmf . n i s t . gov/LaTeXML/
5. Líška, M., Sojka, P., Ružička, M.: Similarity Search for Mathematics: Masaryk University
team at the NTCIR-10 Math Task. In: Kando, N., et al. (eds) NTCIR-10 online Proceedings
(2013) http://research.nii.ac.jp/ntcir/workshop/OnlineProceedingslO/
pdf/NTCIR/MATH/06-NTCIR10-MATH-LiskaM.pdf
6. Líška, M., Sojka, P., Ružička, M., Mravec, P.: Web Interface and Collection for Mathematical
Retrieval. In: Sojka, P., Bouche, T. (eds.) Proceedings of D M L 2011. pp. 77-84. Masaryk
University, Bertinoro, Italy (Jul 2011), http://hdl.handle.net/10338.dmlcz/702604
7. NTCIR Project: NTCIR Pilot Task: Math Task (2012), h t t p : / / n t c i r - m a t h . n i i . a c . j p /
8. Sojka, P., Líška, M.: The Art of Mathematics Retrieval. In: Proc. of the A C M Conference on
Document Engineering, DocEng 2011. pp. 57-60. A C M , Mountain View, C A (Sep 2011),
http://doi.acm.org/10.1145/2034691.2034703
Normalization of Digital Mathematics Library
Content
MathML Canonicalization
David Formánek, Martin Liška, Michal Růžička, and Petr Sojka
Masaryk University, Faculty of Informatics
Botanická 68a, 60200 Brno, Czech Republic
david.formanekSmail.muni.cz, martin.liski@mail.muni.cz,
mruzicka@mail.muni.cz, sojkaSfi.muni.cz
Abstract. Paper discusses the needs for data normalization in a Digital
Mathematics Library (DML). Specifically, emphasis is given to canonicalizing
formulae encoded in Presentation M a t h M L notation which starts
to be available in several D M L s and is used by D M L applications. This
is a prerequisite for advanced processing—namely math enabled fulltext
searching or semantic filtering and automated classification. Different
sources of M a t h M L and their specifics are described. Several use cases of
possible formulae canonicalization transformations are listed and discussed
in detail. Findings are finally concluded and a design of a to-be-developed
canonicalization tool is outlined.
Keywords: MathML normalization, canonicalization, digital mathematics
libraries, D M L , presentation M a t h M L
1 Motivation
Modern Digital Mathematics Libraries (DML) such as E u D M L [18,5] base their
services on paper semantics, i.e. fulltext handling, including mathematical formulae,
as well as basic metadata and Mathematics Subject Classification (MSC)
codes. Mathematics literature is widely dispersed across a high number of publishers,
making it very difficult to collect fulltexts from these heterogeneous
sources. This situation is very different from other libraries, such as PubMed
Central for biomedical and life sciences, where publishers have an agreed workflow
using the N L M Journal Publishing Tag Set and tools developed with funding
from the National Institutes of Health.
Full paper texts have to be 'homogenized', converted to some uniform representation,
in order for math-aware full-text searches [15] and paper similarity
computations [11,12] to work properly These tasks are usually handled based
on a bag-of-words representation of a document text — vector space model —
every term (word, lemma) has its own dimension and the number of occurrences
of a term reflects its value. Non-textual terms such as mathematical formulae
are mostly not taken into account. This creates another challenge for D M L s , as
2 David Formánek, Martin Líška, Michal Růžička, and Petr Sojka
mathematical formulae are the essence of mathematical publications. There is an
average of 380 mathematical formulae per arXiv paper in the MREC database [8].
It has been reported [21] that even a single histogram of mathematical symbols
is sufficient for domain classification of a paper in the mathematical domain.
To reliably represent a paper for D M L processing, including handling the
mathematics, it is necessary to
1. select a canonical representation of the non-textual structural entities appearing
in fulltexts (mathematical symbols, formulae, and equations); and
2. decide on equivalence classes for these entities (e.g., for which formulae
should be considered equal for given D M L tasks such as search, similarity
computation, formulae editing, and conversion of math into Braille).
In this paper, we discuss the options for selecting the canonical representations
of formulae to be used in D M L tools, and the canonicalization process — the
process — of computing this canonical representation from a variety of different
sources and formats.
Our primary motivation is the natural requirement for our own (Web)MIaS
system, which currently uses Presentation MathML [14] to operate correctly and
offer an expected search behaviour to users regardless of the M a t h M L input
source. When a user posts a query to the system, the system must abstract it
from the underlying notational differences in order for it to behave correctly. This
requirement is increasingly emphasized with the growing number of different
sources of MathML. Currently there are three sources (KTpXML, Tralics, and user
input; the number is expected to increase). If they are not correctly normalized
the system misbehaves and it appears to users as if it simply does not work,
however good the underlying design is.
We have used U M C L library [1,2] for canonicalization in our MlaS system
sofar. However, we have found that the deficiencies of the software are so severe
(change of formulae semantics, slowness,...) [7, chapter 5], and the need for
canonicalization so important, that we have decided to design and implement
new canonicalization tool from scratch.
This paper is structured as follows: in Section 2, different sources of mathematics
are described and their differences are discussed. The core part of this
paper is Section 3, where several use cases of possible canonical representation
and canonicalization are documented and suggested. We conclude with Section 5,
and present a plan for future work.
2 MathML Sources
To store mathematical formulae in our documents we have chosen M a t h M L 1
—
an XML-based language — as a widely used, formally defined, but still evolving
standard. The widespread use of M a t h M L and its X M L base means of this
1
More precisely, Presentation MathML, as there are currently significantly more real-life
resources using this form of M a t h M L than Content MathML.
Normalization of Digital Mathematics Library Content 3
language is supported by various tools in the whole document workflow. More
importantly MathML can be used as a common language among the advanced
computer mathematical software packages that are extensively used by working
mathematicians.
O n the author end of the document workflow the M a t h M L code can be
'hand made' using simple plain text editors such as M S Windows Notepad, or
something more comfortable, such as specialized X M L editors that are usually
part of various integrated development environments. For example, the formula
x2
+ y2
can be written as follows:
<math xmlns='http://www.w3.org/1998/Math/MathML'>
<msup>
<mi>x</mi><mn>2</mn>
</msup>
<mo>+</mo>
<msup>
<mi>y</mi><mn>2</mn>
</msup>
</math>
Listing 1: Example of the 'hand made' formula x2
+ y2
However, the X M L nature of M a t h M L makes the coding of more complex
formulae rather long for manual construction. Various software tools are more
frequent sources of MathML. M a t h M L can be generated as an output / data
exchange format of complex specialized programs, such as Maple, Matlab, and
Mathematica [9,20,22], or web services, such as the well known Wolfram A l pha
[23], that are extensively used by mathematicians to support their work.
generate::MathML(x~2 + y~2,
Content = FALSE, Annotation = FALSE)
<math xmlns='http://www.w3.org/1998/Math/MathML'>
<mrow xref='No7'>
<msup xref='No3'>
<mi xref='Nol'>x</mi>
<mn xref='No2'>2</mn>
</msup>
<mo>+</mo>
<msup xref='No6'>
<mi xref='No4'>y</mi>
<mn xref='No5'>2</mn>
</msup>
</mrow>
</math>
Listing 2: Example of M a t h M L export of the formula x2
+ y2
by Matlab 7.9.0
M u P A D symbolic engine
4 David Formánek, Martin Líška, Michal Růžička, and Petr Sojka
<math xmlns='http://www.w3.org/1998/Math/MathML'>
<mrow>
<msup>
<mi>x</mi>
<mn>2</mn>
</msup>
<mo>+</mo>
<msup>
<mi>y</mi>
<mn>2</mn>
</msup>
</mrow>
</math>
Listing 3: Example of the M a t h M L export of the Wolfram Alpha input query
'x~2 + y~2'
On the consumer end of the document workflow MathML can be used as an
input for mathematical programs and services (Maple, Matlab, Mathematica,
Wolfram Alpha, etc.) or simply displayed — usually as part of an X H T M L web
page — in a web browser with MathML support.
However, a large number of mathematical documents are produced using
the Tj^C typesetting system and authored in Tj^C markup. Thus, it is necessary to
be able to convert the TgX source code of mathematical formulae to the MathML
language. Our main motivation is the WebMIaS system. For more complex input
formulae, it would be uncomfortable for the user to manually construct queries
in MathML, as the code would be very complicated. The well known LT^X syntax
is far more appropriate for manual input. Therefore, we need a conversion from
M p X to MathML as part of the WebMIaS input routine.
There are several tools that are able to convert TgX markup to the MathML
language. For example, arXMLiv [16] employs LTgXML [19]. The EuDML project
and our WebMIaS [8] system internally use Tralics [6].
<math xmlns="http://www.w3.org/1998/Math/MathML"
alttext="x~{2}+y~{2}" display="inline">
<semantics>
<mrow>
<msup><mi>x</mi><mn>2</mn></msup>
<mo>+</mo>
<msup><mi>y</mi><mn>2</mn></msup>
</mrow>
<annotation encoding="application/x-tex">
x~{2}+y~{2}
</annotation>
</semantics>
</math>
Listing 4: Example of LTjgXML generated MathML of formula x2
+ y2
Normalization of Digital Mathematics Library Content 5
<math xmlns='http://www.w3.org/1998/Math/MathML'>
<mrow>
<msup>
<mi>x</mi> <mn>2</mn>
</msup>
<mo>+</mo>
<msup>
<mi>y</mi> <mn>2</mn>
</msup>
</mrow>
</math>
Listing 5: Example of Tralics generated MathML of formula x2
+ y2
A frequent type of mathematical document in D M L is the older papers that
are unavailable in any digital-format or are available only in an 'end' format
such as PDF that is suitable for reading and printing but is not appropriate for
direct M a t h M L processing. These documents can be a significant part of the
D M L content collection, so they are worth further processing.
Documents available in hard copy only can be scanned and processed using
InftyReader [17] optical character recognition (OCR) software. InftyReader has
a unique feature for detecting mathematical formulae in a scanned document.
These formulae can be subsequently saved as MathML.
<math xmlns="http://www.w3.org/1998/Math/MathML">
<msup>
<mi mathvariant="italic">x</mi>
<mrow>
<mn mathvariant="normal">2</mn>
</mrow>
</msup>
<mo mathvariant="normal">+</mo>
<msup>
<mi mathvariant="italic">y</mi>
<mrow>
<mn mathvariant="normal">2</mn>
</mrow>
</msup>
</math>
Listing 6: Example of InftyReader generated M a t h M L from a PDF document
containing only formula the x2
+ y2
in its body
Born-digital PDF documents with no available source codes can be processed
using the MaxTract software [3,4], which that is under intensive development as
part of the E u D M L project. MaxTract generates ETpX source / XHTML+MathML
representation of the document based on an optical analysis of the positions of
6 David Formánek, Martin Líška, Michal Růžička, and Petr Sojka
characters on the page. The analysis is supported with information from the
fonts embedded in the processed document.
<math display="block" xmlns="&mathml;">
<mi>&#x0078;</mi>
</math>
<P >
</p>
<p align="right" >
<math display="inline" xmlns="&mathml;">
<mi>&#x0079;</mi>
</math>
</p>
<P >
</p>
Listing 7: Example of X H T M L + MathML generated by the development version
of MaxTract from a PDF document containing only the formula x2
+ y2
in its
body
During the MathDex project, it became clear that the most time- and resourcesconsuming
task in building a math search engine and database is the normalization
and conversion of heterogeneous sources [10]. As shown in Listings 1 — 6 ,
MathML can vary slightly due to the different ways a code was obtained, even
for a trivial formula like x2
+ y2
.
In a D M L project, there can be differences in the final M a t h M L encoding
even for semantically and structurally similar formulae, due to the origins of the
MathML from different sources. In Section 3, several more complicated examples
of possible ambiguities in MathML are discussed that have to be normalized to
allow math searches and similarity computation.
3 Use Cases
Using our public working demo of the WebMIaS system we discovered several
discrepancies in the form of MathML generated by the real-time TpX to MathML
converter we currently use — Tralics — and by the MathML canonicalizer from
the U M C L library. We employed the U M C L canonicalization module to try to
normalize the users' MathML input and the MathML produced by the ETpXML
converter contained in the arXMLiv collection. Then we went through the Presentation
M a t h M L specifications and gathered a list of possible reformatting
rules we could perform.
Normalization of Digital Mathematics Library Content 7
The goal is to reduce the possible MathML scripts with the same semantics
and mathematical structures to just one representation. To have such a canonicalized
representation is convenient for many applications, as was described in
Sections 1 and 2.
Analyzing the issues of possible inconsistencies and ambiguities of MathMLencoded
formulae raised design and strategy questions. Conceptual decisions
for handling different types of similar constructions and completely different
formulae need to be made.
More specifically for example, should we try to keep the MathML compact
and reduce the number of nodes in transformations, or should we try to add
nodes for better disambiguation? Another question is: should our future canonicalization
tool produce valid MathML according to this schema? Unquestionably,
this feature would be nice to have for many reasons and possible applications,
but it certainly adds more requirements and takes much more effort to design
and implement not only true/false validation, but also functional correctness
validation.
Below are described proposals and discussions of transformations that can be
performed with relatively minor difficulty. The list is not complete and is subject
to further evaluation.
3.1 Removing Elements and Attributes
Many of the MathML elements used in Presentation MathML make little or no
contribution to the semantics of the formula and therefore also to the formulae
for indexing and searching. These are usually elements that alter the appearance
of formulae in some way — space-like elements such as mspace, mpadded,
mphantom, maligngroup, and malignmark. They may occasionally have some
semantic meaning, but we prefer to canonicalize similar formulae into one representation
rather than risk treating the same formulae as different. Therefore,
these elements are best omitted. The content of the mtext element should be
indexed as normal text before removal.
Most element attributes are similarly undesirable. Many are used for formatting,
affecting only the appearance of rendered formulae (for example, the
attributes linebreak and indentalign of the mo element). Others might have
some slight semantic significance, but are very uncommon and usually not very
important; we think these attributes should be removed. However, several exceptions
exist. For instance, the element mf rac is used for fractions but its meaning
changes with the attribute linethickness set to 0, which express a binomial
coefficient. The attributes of the element mf enced are also important (see Listing
9). The attribute mathvariant can also influence formula semantics and
therefore should be preserved in all possible elements. For example, the MlaS
system makes use of this attribute so that hits with the assigned mathvariant
font specifying the attribute are more relevant.
8 David Formánek, Martin Líška, Michal Růžička, and Petr Sojka
<mfrac>
<mrow>
<mi> x </mi>
<mo> + </mo>
<mi> y </mi>
<mo> + </mo>
<mi> z </mi>
</nrrow>
<mrow>
<mi> x </mi>
<mphantom>
<mo> + </mo>
<mi> y </mi>
</mphantom>
<mo> + </mo>
<mi> z </mi>
</nrrow>
</mfrac>
<mfrac>
<nrrow>
<mi> x </mi>
<mo> + </mo>
<mi> y </mi>
<mo> + </mo>
<mi> z </mi>
</mrow>
<nrrow>
<mi> x </mi>
<mo> + </mo>
<mi> z </mi>
</mrow>
</mfrac>
Listing 8: Example of <mphantom> ommision
<mfrac lmethickness="2"
<mirac>
bevelled="true">
. <mi> a </mi>
<mi> a </mi>
. <mi> b </mi>
<mi> b </mi> , ,
, </mirac>
</mirac>
Listing 9: Example of omission of unnecessary attributes in mf rac
3.2 Unifying Fences
There are two approaches to creating fenced formulae. One is more semantic
and uses the mf enced element with the open, close, and separator attributes
to describe delimiters and separators. The other places fence symbols directly
within mo elements, and the fenced formula is enclosed in the mrow element to
group the elements together. Although the first approach seems to be valid, we
prefer the second one as it is more universal and allows easier conversion — e.g.,
converting addition to mf enced with attribute separators set to + would be
invalid. As shown in Listing 10, mf enced elements are replaced by a more general
mrow element, and fence and separator symbols are added as mo elements. Fenced
elements are further enclosed in an mrow element so it can be treated as a single
expression when needed. We could also consider unifying the symbols used as
separators/delimiters.
Normalization of Digital Mathematics Library Content 9
<mrow>
<mo> [ </mo>
<mfenced open="L >
<mrow>
. <mi> x </mi>
<mi> x </mi> .
<mo> , </mo>
. <mi> y </mi>
<mi> y </mi>
<mrow>
, , , <mo> ) </mo>
</mfenced>
</mrow>
Listing 10: Two ways of writing interval [x, y)
3.3 Mrow Minimizing
The mrow element is used for grouping other elements. Its most common use case
is to obtain a given correct number of child elements of some parent element (e.g.
mf rac needs two child elements). We can determine unnecessary occurrences of
mrow by summing the number of its child elements and its siblings with respect
to the number of required elements for the parent element. Parents requiring
only one child element actually accept any number of elements that are treated
as if they are inferred within a single mrow element. Hence, the grouping element
is redundant and can be removed. In any case, the impact of the transformations
to any form of processing canonicalized notation must be taken into account and
the structure of the formulae cannot be violated. For instance, after removing the
mf enced enclosing element we ought to wrap the fenced formula with an mrow
if it is not.
<msqrt> <msqrt>
<mrow>
<mo> - </mo> <mo> - </mo>
<mn> 1 </mn> <mn> 1 </mn>
</mrow>
</msqrt> </msqrt>
Listing 11: Example of <mrow> removal after optimization y7
—T
3.4 Sub-/Superscripts Handling
The msubsup element used for attaching subscript and superscript to another
element at the same time is redundant — the same thing can be expressed as
10 David Formánek, Martin Líška, Michal Růžička, and Petr Sojka
a combination of msub and msup elements. The order of the elements is important.
When both elements are used, we prefer to place msub within msup (see Listing
12) because a subscript is usually more closely related to the base expression.
A similar problem and solution is related to the elements triad of munder, mover,
and munderover. Both msubsup and munderover can be used for limits of integration
or bounds of summations; therefore, we should use only one canonical
representant.
<msubsup>
<mi> x </mi>
<mn> 1 </mn>
<mn> 2 </mn>
</msubsup>
Listing 12: Two ways of expressing
<msup>
<msub>
<mi> x </mi>
<mn> 1 </mn>
</msub>
<mn> 2 </mn>
</msup>
3.5 Applying Functions
There are many ways to express functions. Entity &#x2061; (function application)
should be used but we cannot rely on that, so we suggest removing this operator
for the purpose of unification. The opposite approach — adding the function
application operator where it was omitted — could be rather tricky and could
lead to ambiguities. The name of the function should occur in the mi element
but it also can be considered as an operator and be placed in the mo element.
The arguments of a function can be fenced with parentheses or an mf enced
element or both. We chose canonical representation without an entity, with mrow
and parentheses (see Listing 14). Other ambiguities can be caused by different
invisible operators. For example, two identifiers in a subscript with no operator
usually means multiplication but it can mean separation too.
4 Design Considerations
The design and implementation decisions of the canonicalization application
depend on the purpose of new canonicalizer. Even though the use of the math
content by different tools might be similar, the experience shows that we hardly
could 'fit one size' for all applications. Thus the main design imperative is the
modularity, simplicity, extensibility and flexibility, so that the canonicalizer might
be easily modified when the need of the applications change. With different data
the canonicalizer might change even for different types of math-aware search.
Normalization of Digital Mathematics Library Content 11
<mi> f </mi>
<mi> f </mi>
<mo> &#x2061; </mo>
<mrow>
<mrow>
<mo> ( </mo>
<mi> x </mi>
<mo> ) </mo>
</mrow>
<mo> ( </mo>
<mi> x </mi>
<mo> ) </mo>
</mrow>
Listing 13: Using or not using the operator for function application
<mi> sin </mi>
<mi>sin</mi>
<mrow>
<mo> &#x2061; </mo>
<mo>(</mo>
<mi>x</mi>
<mi> x </mi>
<mo>)</mo>
</mrow>
Listing 14: Adding parentheses to sine function argument
Examples in subsections of previous section form set of modules that do the
necessary M a t h M L tree transformations as recursive procedures on MathML
trees.
According to the expected size of the input data set, effectiveness, the speed
of the canonicalization application is also a critical parameter — in our MREC [8]
corpora there is 168,000,000 formulae to canonicalize. Thus, use of standard XSL
transformations does not seem to be appropriate, for example, as U M C L example
showed.
Another key decision is handling of invalid input MathML and question of
valid MathML on the output as mentioned in Section 3.
As the (Web)MIaS system as well as other core parts of E u D M L system
(Lucene) do use the Java platform is seems to be natural to use Java also for the
implementation of canonicalization application.
5 Conclusions and Future Work
We consider MathML canonicalization important for proper functioning of several
math-aware applications that handle documents in DMLs. We have defined
the problems and enumerated the most important use cases as modules of newly
designed canonicalizer.
We are currently working on finishing the design and implementation of a
first version of application that will be used for the task of math indexing in MlaS
12 David Formánek, Martin Líška, Michal Růžička, and Petr Sojka
system employed in E u D M L project. By evaluation of this task we will verify our
design decisions and plan to use it for another tools working with math fulltext
data (semantic similarity tools as gensim [12]).
Acknowledgements This work was partially supported by the European Union
through its Competitiveness and Innovation Programme (Information and Communication
Technologies Policy Support Programme, 'Open access to scientific
information', Grant Agreement No. 250503, a project of the European Digital
Mathematics Library, E u D M L ) .
References
1. Archambault, D., Berger, R, Moco, V.: Overview of the "Universal Maths Conversion
Library". In: Pruskí, A., Knops, H . (eds.) Assistive Technology: From Virtuality to
Reality: Proceedings of 8th European Conference for the Advancement of Assistive
Technology in Europe A A A T E 2005, Lille, France, pp. 256-260. IOS Press, Amsterdam,
The Netherlands (Sep 2005)
2. Archambault, D., Moco, V.: Canonical MathML to Simplify Conversion of MathML to
Braille Mathematical Notations. In: Miesenberger, K., Klaus, J., Zagler, W., Karshmer,
A. (eds.) Computers Helping People with Special Needs, Lecture Notes in Computer
Science, vol. 4061, pp. 1191-1198. Springer Berlin / Heidelberg (2006), h t t p : / / d x .
doi.org/10.1007/11788713_172
3. Baker, J.B., Sexton, A.P., Sorge, V.: A linear grammar approach to mathematical formula
recognition from PDF. In: Proceedings of the Conferences in Intelligent Computer
Mathematics, C I C M 2009. L N A I , vol. 5625, pp. 201-216. Springer (2009)
4. Baker, J.B., Sexton, A.P., Sorge, V.: Towards reverse engineering of P D F documents.
In: Sojka, P., Bouche, T. (eds.) Towards a Digital Mathematics Library, D M L 2011. pp.
65-75. Masaryk University Press, Bertinoro, Italy (July 2011), h t t p : / / h d l . handle.
net/10338.dmlcz/702603
5. Borbinha, J., Bouche, T , Nowiňski, A . , Sojka, P.: Project E u D M L — A First Year
Demonstration. In: Davenport, J.H., Farmer, W.M., Urban, J., Rabe, F. (eds.) Intelligent
Computer Mathematics. Proceedings of 18th Symposium, Calculemus 2011,
and 10th International Conference, M K M 2011. Lecture Notes in Artificial Intelligence,
L N A I , vol. 6824, pp. 281-284. Springer-Verlag, Berlin, Germany (Jul 2011),
http://dx.doi.org/10.1007/978-3-642-22673-1_21
6. Grimm, J.: Producing M a t h M L with Tralics. In: Sojka [13], pp. 105-117, http: / / d m i .
cz/dmlcz/702579
7. Jarmar, M . : Conversion of Mathematical Documents into Braille. Master's thesis,
Faculty of Informatics (Jan 2012), https: / / i s . muni. cz/th/172981/f i_m/?lang=en
8. Líška, M . , Sojka, P., Růžička, M . , Mravec, P.: Web Interface and Collection for Mathematical
Retrieval. In: Sojka, P., Bouche, T. (eds.) Proceedings of D M L 2011. pp. 77-84.
Masaryk University, Bertinoro, Italy (Jul 2011), http://www.fi.muni.cz/~sojka/
dml-2011-program.html
9. Maplesoft, a division of Waterloo Maple Inc.: M a t h M L - Maple Help (Apr 2012),
http://www.maplesoft.com/support/help/Maple/view.aspx?path=MathML
10. Munavalli, R., Miner, R.: MathFind: A Math-Aware Search Engine. In: Proceedings of
the 29th annual international A C M SIGIR conference on Research and development
in information retrieval, pp. 735-735. SIGIR'06, A C M , New York, NY, U S A (2006),
http://doi.acm.org/10.1145/1148170.1148348
Normalization of Digital Mathematics Library Content 13
11. Řehůřek, R., Sojka, P.: Automated Classification and Categorization of Mathematical
Knowledge. In: Autexier, S., Campbell, J., Rubio, J., Sorge, V., Suzuki, M . , Wiedijk,
F. (eds.) Intelligent Computer Mathematics—Proceedings of 7th International Conference
on Mathematical Knowledge Management M K M 2008. Lecture Notes in
Computer Science L N C S / L N A I , vol. 5144, pp. 543-557. Springer-Verlag, Berlin, Heidelberg
(Jul 2008)
12. Řehůřek, R., Sojka, P.: Software Framework for Topic Modelling with Large Corpora.
In: Proceedings of LREC 2010 workshop New Challenges for N L P Frameworks, pp. 45-
50. ELRA, Valletta, Malta (May 2010), h t t p : / / i s . muni. cz/publication/884893/en,
software available at h t t p : / / n i p . fi.muni.cz/projekty/gensim
13. Sojka, P. (ed.): Towards a Digital Mathematics Library. Masaryk University, Paris,
France (Jul 2010), http://www.fi.muni. cz/~sojka/dml-2010-program.html
14. Sojka, P., Líška, M . : Indexing and Searching Mathematics in Digital Libraries (Mar
2011), submitted to M K M 2011
15. Sojka, P., Líška, M.: Indexing and Searching Mathematics in Digital Libraries - Architecture,
Design and Scalability Issues. In: Davenport, J.H., Farmer, W.M., Urban, J.,
Rabe, F. (eds.) Intelligent Computer Mathematics. Proceedings of 18th Symposium,
Calculemus 2011, and 10th International Conference, M K M 2011. Lecture Notes in
Artificial Intelligence, LNAI, vol. 6824, pp. 228-243. Springer-Verlag, Berlin, Germany
(Jul2011), http://dx.doi.org/10.1007/978-3-642-22673-l_16
16. Stamerjohanns, H., Kohlhase, M . , Ginev, D., David, C , Miller, B.: Transforming Large
Collections of Scientific Publications to X M L . Mathematics in Computer Science 3,
299-307 (2010), http: / / d x . d o i . org/10.1007/sl 1786-010-0024-7
17. Suzuki, M . , Tamari, F , Fukuda, R., Uchida, S., Kanahori, T.: I N F T Y — A n integrated
OCR system for mathematical documents. In: Vanoirbeek, C , Roisin, C , Munson, E.
(eds.) Proceedings of A C M Symposium on Document Engineering 2003. pp. 95-104.
A C M , Grenoble, France (2003)
18. Sylwestrzak, W., Borbinha, J., Bouche, T., Nowiňski, A., Sojka, P.: EuDML—Towards
the European Digital Mathematics Library. In: Sojka [13], pp. 11-24, http: / / d m i . c z /
dmlcz/702569
19. The LaTeXML project: The LaTeXML Developer Portal (Apr 2012), https: / / t r a c .
mathweb.org/LaTeXML/
20. The MathWorks, Inc.: M u P A D - Matlab (May 2012), h t t p : //www. mathworks. com/
di sc overy/mupad.html
21. Watt, S.M.: Mathematical Document Classification via Symbol Frequency Analysis.
In: Sojka, P. (ed.) Towards Digital Mathematics Library—Proceedings of D M L 2008.
pp. 29-40. Masaryk University, Birmingham, U K (Jul 2008), http://www.fi.muni.
cz/~sojka/dml-2008-program.xhtml
22. Wolfram: Mathematica Import/Export Format : M a t h M L (Apr 2012), h t t p : / /
reference.wolfram.com/mathematica/ref/format/MathML.html
23. Wolfram Alpha LLC: Wolfram Alpha (Apr 2012), http: //www. wolf ramalpha. com/
Building Corpora of Technical Texts
Approaches and Tools
Petr Sojka, Martin Liška, and Michal Růžička
Faculty of Informatics, Masaryk University
Botanická 68a, 602 00 Brno, Czech Republic
sojka@fi.muni.cz, m a r t i n . l i s k i @ m a i l . m u n i . c z , mruzicka@mail.muni.cz
Abstract. Building corpora of technical texts i n Science, Technology,
Engineering, and Mathematics (STEM) domain has its specific needs,
especially the handling of mathematical formulae. In particular, there is
no widely accepted format to represent and handle math.
We present an approach based on multiple representations of mathematical
formulae that has been used for math retrieval, similarity and clustering
of mathematical corpus. We provide an overview of our toolset, summarize
our experiments to date and propose further research directions
and approaches.
Key words: mathematical corpora; information retrieval of mathematics;
representation of mathematical formulae; math search and indexing
normalization of M a t h M L ; canonicalization
1 Introduction
Leading research in empirical linguistics builds on the large (e.g. web-scale) corpora
such as those created by Google (Google Books Corpus, Google Scholar)
or by the Sketch Engine (TenTen Corpora). Such corpora allow for natural language
processing (NLP) of a new quality level to solve such tasks as more relevant
information retrieval, document clustering, classification and similarity,
thesauri and ontology building, better word sense disambiguation, machine
translation and many others. However, in these research mainstream activities,
minority languages or domain specifics are neglected. Such a neglected 'language'
is the language of mathematics - typical in Science, Technology, Engineering,
and Mathematics (STEM) documents.
Mainstream NLP workflow for building corpora starts with tokenization,
which is usually not aware of mathematical formulae or equations. Math is
usually supported neither by optical character recognition (OCR) tools, nor
by applications that generate PDF or (X)HTML. The use and representation
of math on the web is far from settled. As a consequence, no mainstream tools
support this niche market of 'the Queen of sciences'.
In previous projects that involved building Digital Mathematics Libraries
(DML) such as DML-CZ [1] and EuDML [2], we had to deal with the fact that
NLP corpora tools were unable to handle corpora of math texts, let alone build
Aleš Horák, Pavel Rychlý (Eds.): Proceedings of Recent Advances in Slavonic Natural Language Processing,
RASLAN 2011, pp. 69-79,2011. © Tribun EU 2011
70 Petr Sojka, Martin Liška, Michal Růžička
them. We therefore devised some tools for adequate support of mathematical
formulae in NLP and information retrieval (IR) tasks. Proper semantic and
math-aware representation is a necessary prerequisite for efficient and effective
NLP processing of STEM corpora.
This task involved as the first step the design of math formulae representation
(Section 2). Then, to build mathematical corpora, we had to preprocess and
normalize heterogenious inputs (Section 3) into this new representation. It was
also necessary to design ways of math retrieval (index and search are crucial, cf.
Section 4). Our aim is to support math-aware document clustering, similarity
and disambiguation (Section 5). We summarize our findings in the Section 6.
2 Math Representations
Mathematicians and other authors of STEM documents encode quantities and
relations using formulae and equations in compact, often two-dimensional,
notation. These objects have to be represented in unique way in the global
STEM document handling system.
There are numerous ways of notating the same mathematical object, that
has evolved in some geographical location or language. This is an example of
different notations for a binomial coefficient:
When searching STEM documents, it should be possible to find the same objects
within a corpus, and assign them the same representation even though authors
have used different notation. As is the case with text handling, where words
with the same meaning are treated and indexed the same, formulae require the
same treatment.
The matter is complicated by the fact that there are different formats for
handling mathematics: TpX, MathML, OpenMath, etc.
Authors prefer the compact and logical notation of TgX. The American Mathematical
Society (AMS) extended standard plain TpX and BTgX notation with
AMS packages (so called AMSBT^C) for commutative diagrams, aligned equations,
etc. The namespace of AMSI^TpX macros is nowadays the de facto standard
for the typesetting of mathematical documents, and this namespace is also
supported in ithe metadata of DML-CZ (only this namespace is allowed and
supported there, e.g. by conversion to MathML).
TpX math notation is in such demand that even for Word there is plug-in
by Design Science that allows entering the formulae in TpX notation. This is
much quicker, and more convenient than choosing the symbols from numerous
menus and symbol tables. Nevertheless, using TpX notation for indexing
2.1 TEX
Building Corpora of Technical Texts: Approaches and Tools 71
purposes is a disaster, as an example of LaTeXSearch application by Springer
(http: //latexsearch. com) shows. Authors are so creative in macroexpansion
use or TpX language formatting that different notations cannot be coped with
by simple string similarity. A formulae structure and other types of similarity
has to be used in formulae representation for similarity computation. For this,
the tree structure of XML (MathML) is better, as it is understood by the majority
of math-aware software developers.
2.2 MathML
In the world of applications and software interfaces, MathML usually wins,
as it is supported by W3C and AMS. TpX's macro namespace extensibility
is a nightmare to support by software without the full TpX macroexpansion
complex engine, and here MathML clearly wins. MathML DTD allows easy
formulae validation and processing with XML tools. There are even recently
developed portable tools like Mathjax, a JavaScript library that displays
mathematics in web browsers, supporting both LTTHX and MathML markup as it
attempts to convert LTpX on-the-fly into appropriate markup language-HTML
or MathML.
2.3 Set of M-terms
A mathematical document contains mathematical formulae, which are integral
to the content of the document. As mentioned in the previous sections, these
formulae are usually represented in TpX if authored by humans, or in MathML
(presentation or mixed content-presentation) if produced by machines.
To be able to search for such structural information using a fulltext indexing
approach as in the Math Indexer and Searcher (MlaS) system [3,4], a convenient
representation needs to be selected. This representation needs to be a
trade-off between the TpX powered authors' part of the world and machinefriendly,
preserve-as-most-information-as-possible, structural and semantic notation
such as Content MathML. In MlaS system we opted for Presentation
MathML as it stands, we find, exactly halfway. It is relatively easy to obtain
by converting the author's TpX markup and it still holds the necessary structural
information for machine processing. It is still easily extensible by Content
MathML trees capturing the formulae semantics.
Such mathematical markup needs to be preprocessed before the indexing.
This is mainly to accommodate the best user search experience as possible. For
each formula in the text, the system produces several representations which are
stored in the index and are searchable in the same way as regular textual terms.
These are called M-terms.
M-terms are translated from XML to a linear string form. In this form they
are stored by the indexing core. This representation omits any XML markup
that would be redundant in such a form, such as start and end tags, and replaces
it with brackets to prevent ambiguity. Also most of the attributes setting the
visual behaviour of the expression can be left out, since it does not hold any
72 Petr Sojka, Martin Liška, Michal Růžička
information pertaining to the meaning of the formula. This representation
can be further compacted by substituting tag names for single characters to
decrease storage space requirements.
For example, simple expression a2
+ b in its XML form
<math>
<mrow>
<msup><mi>a</mi><mn>2</mn></msup>
<mo>+</mo>
<mi>b</mi>
</mrow>
</math>
is translated to the linear form mrow (msup (mi (a)mn(2))mo(+)mi (b)) and based
on a custom tag name dictionary, where mrow = R; msup = J; mi = I; mn = N
and mo = 0. This is further compacted to R(J(I(a)N(2))0(+) 1(b)). A set of
sub-M-terms is generated for each input formula. It consists of subformulaweight
pairs. For this particular expression, it is:
{
(mi(a),0.08166666),
(mn(2),0.08166666),
(msup(mi(a)mn(2)),0.11666667),
(mo(+),0.11666667),
(mi(b),0.11666667),
(mrow(mi(b)mo(+)msup(mi(a)mn(2))),0.16666667),
(msup(mi(l)mn(2)),0.093333334),
(inrow(mi(l)mo(+)msup(mi(2)mn(2))) ,0.13333334) ,
(msup(mi(a)mn(^f)) ,0.058333334),
(irrrow(mi(b)mo(+)msup(mi(a)mn(^f))) ,0.083333336) ,
(msup(mi(l)mn(l)),0.046666667),
(mrow(mi(l)mo(+)msup(mi(2)mn(^f))) ,0.06666667)
}
These formulae are derived from the original one and their level of similarity is
expressed by the weight factor.
This representation not only grabs the structural similarity of mathematical
formulae, it also copes with different variable names, and with mathematical
properties of operators (commutativity). As such, representation of formulae
by an M-term set with weights is directly useable for indexing or for document
similarity computations.
To provide these and other uses of this representation, we have set up a
RESTful web service, where for each input formula one can get a set of M-terms
as they would be indexed in the MlaS system. An example of use can be found
here:
http://aura.fi.muni.cz:8085/mias4gensim/mathprocess?mterm=<math><mrow>
<mi> a</mi><mo>+</mo><mi>b</mi> </mrow> </math>
Building Corpora of Technical Texts: Approaches and Tools 73
3 Mathematical Corpora
3.1 Normalization
When building mathematical corpora using MathML as a language for mathematical
formulae preservation, it emerges that it is very useful to process and
normalize MathML that is being stored. It is necessary as one mathematical formula
can be encoded in MathML in different forms-using different sequences
of characters in the source code-but its meaning is the same.
For example, the formula x2
+ y2
can be encoded in MathML in the form:
<math xmlns=" http://vvvw.w3.org/1998/Math/MatLiML''>
<msup>
<mi>x</mi>
<mn>2</mn>
</msup>
<mo>+</mo>
<msup>
<mi>y</mi>
<mn>2</mn>
</msup>
</math>
But some other author can use this form:
<math xmlns=" http://wvw.w3.org/1998/Math/MatLiML''>
<mrow>
<msup>
<mi>x< /mi><mn>2</mn></msup>
<mo>+</mo>
<msup>
<mi>y< /mi><mn>2</mn></msup>
</mrow>
</math>
To be able to find documents that contains our formula in any of these codings
we need one normalized form that will be stored in the index. Subsequently,
any query for this formula in any coding has to be transformed to the
normalized form at the beginning.
Moreover, examples of documents from the real world (PubMed Central
digital library workflow) show that validation of MathML source codes is not
enough. Elbow et al. [5] demonstrate a well-known fact that current authors'
main target is print output - consequently one can find MathML fragment
<mml :mn>7</mml :mn><mml :mn>5</mml :mn> as source code of the number '75'
for example. These anomalies have to be sorted out before publishing and
indexing in a repository.
For the semantically same formalae there exist infinitely many ways of
representing them in MathML. For NLP handling it would be convenient to
have one canonical representation of a formulae.
74 Petr Sojka, Martin Liška, Michal Růžička
3.2 Canonicalization
Proper MathML normalization (canonicalization) is not easy given that
MathML is a very complex markup language. Some existing tools we have
tested fail when run over a set of MathML test documents [6] that were designed
to cover a wide range of MathML features.
Our approach to MathML normalization has so far involved a trial use
of UMCL (Universal Maths Conversion Library; http: //inova. ufr- inf o-p6.
jussieu.fr/maths/umcl). [7,8] The main purpose of the UMCL tool set is
to enable transcription of the MathML formulae to Braille national codes.
Related to this task is also the need for MathML formulae unification. UMCL
transformation of the MathML to Canonical MathML is carried out using a set
of XSL stylesheets [9].
With minor modifications, the UMCL MathML transformation was used in
the WebMIaS interface [10] (see Section 4) that can be used to search over our
MREC corpus (see Section 3.3). This showed benefits of formulae normalization
in practice-search form x2
+ y2
formula using the first form of MathML code
from the previous section found no results. However, for the second form of
MathML - the form that is the result of UMCL XSL transformation from the
first form-there were 36,817 hits in MREC corpus version 2011.4.
Unfortunately, the MathML canonicalization module of the UMCL tool set
is not as powerful as we thought at the beginning. Using the W3C MathML Test
Suite mentioned in the previous section, some weak points in UMCL normalization
process have been identified. Among other things, there are problems
with MathML tags like 'mphantom', 'mfenced', 'mglyphe', 'mmultiscripts',
'mover' and 'mstyle' that are not properly converted. Furthermore, attributes
of MathML elements are not reported in the UMCL canonicalized MathML.
These problems were consulted with UMCL developers but no fast and
clear solution seems to be available. Due to these problems, UMCL in the
current version does not seem to be directly applicable to MREC corpus and
further research in this area is definitely necessary.
3.3 Corpus MREC
To provide a test platform for mathematical search tools, we are building a
corpus of mathematical texts. We call this corpus MREC.
MREC is based on arXMLiv [11]-a project of Michael Kohlhase's group at
Jacobs University Bremen. arXMLiv documents came from arXiv. org but have
been translated to XML by arXMLiv project. These documents cover different
STEM areas - Physics, Mathematics, Computer Science, Quantitative Biology,
Quantitative Finance and Statistics.
However, MREC is not an exact copy of the arXMLiv content. MREC contains
just a subset of the arXMLiv-arXMLiv puts transformed documents into
several classes - successful, complete with errors and incomplete, depending
on the results of the transformations. MREC contains papers from conversion
classes, successful and complete with errors (missing macros)-see Table 1. We
Building Corpora of Technical Texts: Approaches and Tools 75
have collected 439,423 documents in well-formed XHTML, containing mathematical
formulae in valid MathML.
Table 1. Documents collected from arXMLiv
arXMLiv transformation result class Quantity
successful (no problem) 65,874
successful (warning) 291,879
complete w i t h errors (missing macros) 81,670
All documents 439,423
Moreover, there were several modifications of the files that from our point
of view were necessary in order to make the documents well-formed and
valid. These modifications include removing unnecessary attributes, namespace
proxies, 'div' elements nested in 'span' elements and so on.
MREC consists of well-formed XHTML documents. MathML is used for
representation of mathematical formulae.
Although MREC is under constant development, it is necessary for both
archive and comparison purposes to produce a stable release versions. For
this reason, there are several version of MREC corpora available at http:
//nip.fi.muni.cz/projekty/eudml/MREC/.
The first public version of MREC, version 2011.3.324, consists of 324,060
documents. The resulting corpus size was 53 GB uncompressed, 6.7 GB
compressed. Documents contained 112,055,559 formulae in total, of which
2,129,261,646 mathematical expressions were indexed. The resulting index size
was approximately 45 GB.
The newer version of MREC, version 2011.4.439, consists of 439,423 scientific
documents containing 158,106,118 mathematical formulae. 2,910,314,146
expressions were indexed and the resulting size of the index is 63 GB. The sizes
of uncompressed and compressed corpora are 124 GB and 15 GB, respectively.
4 Math Retrieval
Searching functionality is nowadays a key form of getting orientated in the
vast amount of information "out there" and obtaining the information we seek.
Just as websites providing special content such as images and videos enable
searching for these tokens, portals providing mathematical content such as
EuDML [12] should also be able to search for the formulae.
In our view, the optimal way of doing so is to provide a simple Googlelike
interface where one can pose mathematical and textual query tokens one
alongside the other. Search results returned to a textual query can then be
finely constrained by adding a formula to the query and, in fact, vice-versa.
We present this approach in the WebMIaS interface [10].
76 Petr Sojka, Martin Liška, Michal Růžička
For example, by posting a simple query x + y in our web interface, the
system returns 36,817 results. Addition of one more keyword Euclid reduces the
number of results to only 97-all of them contain this textual term. Conversely,
searching only for Euclid returns 848 results and by adding x2
+ y2
expression,
we get the same 97 matches (MREC 2011.4.439).
To implement math-aware IR system in addition to the web-interface it was
necessary to create an index to be consulted during query evaluation. We use
our M-term representation for this, as described in detail in [3,4]. We have
evaluated the system's speed. As is shown in Table 2, the performance of the
MlaS system scales linearly. This gives feasible response times even for our
billions of indexed subformulae.
Table 2. Indexing scalability test results (run on 448 GiB RAM, eight 8-core 64bit
processors Intel Xeon™ X7560 2.26 GHz driven machine).
#Docs Input formulae Indexed formulae run-time [ms] C P U time [ms]
10,000 3,406,068 64,008,762 2,145,063 2,102,770
50,000 18,037,842 333,716,261 11,382,709 10,871,500
100,000 36,328,126 670,335,243 23,066,679 21,992,100
200,000 72,030,095 1,326,514,082 46,143,472 44,006,180
300,000 108,786,856 2,005,488,153 71,865,018 66,998,550
350,000 125,974,221 2,318,482,748 83,199,724 77,886,160
439,423 158,106,118 2,910,314,146 104,829,757 97,393,301
5 Further Research Directions in Math Similarity, Clustering
and Disambiguation
In mathematics, Mathematical Subject Classification (MSC) is used by most
journals today, being supported and developed by both Mathematical Reviews
(MR) and Zentralblatt Math (ZMath). Our research so far [13] has shown
that machine-learned classification and similarity tasks are tractable to be
supported by DMLs. However, previous research paid very little attention to
the representation of mathematics. Either textual tokens alone were used, or
the formulae were split into variables, constants and operators, and used in a
'bag of words' for documents. Such representation is insufficient given that it
does not convey the structure of formulae, and neither does it pay attention to
semantically similar formulae (e.g. written in different variable names, sorted
differently as a + b vs. b + a, etc.).
We are currently using the Gensim [14] system to evaluate the possibility
of using M-terms instead of the usual tokenization and comparing the effects
this new representation has on similarity and clustering improvements over
non math-aware representations. We believe that M-term representation will
Building Corpora of Technical Texts: Approaches and Tools 77
significantly improve the quality of document similarity metrics computed by
Gensim.
Further improvements could be achieved by employing cutting edge results
on semantic disambiguation. Symbol / might play the role (have meaning) of a
variable, functional, (linear) function, and potentially a dozen other meanings.
To have a greater relevance to searching and better document clustering, even
mathematical formulae should be disambiguated at this level, as authors are
usually reluctant to do so in the (LKTpX) sources or in Content MathML. Our
representation method is easily inclusive with respect to these refinementsone
just needs to add a notation and weighting for similarity of new terms
representing Content MathML (semantics).
There were attempts to bring NLP approaches to math corpora handling
recently [15,16]. The most consistent problem remains the high degree of ambiguity
in mathematical formulae and nonexistence of tagged disambiguated
math data.
There is a promising approach to distinguishing roles of words (math tokens)
which depends on the contexts of use in a corpus called LDA-fratnes [17].
It uses statistics to distinguish different roles based on different structural patterns
of word usage in corpora. We are considering the possibility of using
a fuzzy version of Formal Concept Analysis (FCA) [18] to identify the roles
of math tokens in formulae, and in combination with LDA-frames to disambiguate
them.
6 Summary and Conclusions
In this paper, we have identified and described the problems we have faced
when building nontrivial corpora of STEM documents MREC. We have suggested
M-term representation for math-aware indexing and similarity computations.
We have reported current results in imath-aware indexing and isearching.
We have discusses future research directions towards fully fledged mathaware
corpora processing like math-aware document similarity or disambiguation
of math symbols in formulae.
Acknowledgements This work has been partially supported by the Ministry
of Education of CR within the Center of Basic Research LC536 and by the
European Union through its Competitiveness and Innovation Programme
(Information and Communications Technologies Policy Support Programme,
"Open access to scientific information", Grant Agreement No. 250503).
References
1. Bartosek, M . , Lhotak, M , Rakosnik, J., Sojka, P., Sarfy, M : D M L - C Z : The Objectives
and the First Steps. In: Borwein, J., Rocha, E . M . , Rodrigues, J.F., eds.: C M D E 2006:
Communicating Mathematics i n the Digital Era. A . K. Peters, M A , U S A (2008) 69-79.
78 Petr Sojka, Martin Liška, Michal Růžička
2. Borbinha, J., Bouche, T., Nowiňski, A . , Sojka, P.: Project E u D M L — A First Year
Demonstration. In: Davenport, J.H., Farmer, W . M . , Urban, J., Rabe, F., eds.:
Intelligent Computer Mathematics. Proceedings of 18th Symposium, Calculemus
2011, and 10th International Conference, M K M 2011. Volume 6824 of Lecture Notes
in Artificial Intelligence, L N A I . , Berlin, Germany, Springer-Verlag (2011) 281-284
h t t p : / / d x . d o i . o r g / 1 0 . 1 0 0 7 / 9 7 8 - 3 - 6 4 2 - 2 2 6 7 3 - 1 _ 2 1 .
3. Sojka, P., Líška, M . : Indexing and Searching Mathematics i n Digital Libraries - A r chitecture,
Design and Scalability Issues. In: Davenport, J.H., Farmer, W . M . , Urban,
J., Rabe, F., eds.: Intelligent Computer Mathematics. Proceedings of 18th Symposium,
Calculemus 2011, and 10th International Conference, M K M 2011. Volume 6824
of Lecture Notes i n Artificial Intelligence, L N A I . , Berlin, Germany, Springer-Verlag
(2011) 228-243 h t t p : / / d x . d o i . o r g / 1 0 . 1 0 0 7 / 9 7 8 - 3 - 6 4 2 - 2 2 6 7 3 - 1 _ 1 6 .
4. Sojka, P., Líška, M . : The A r t of Mathematics Retrieval. In: Proceedings of the
A C M Conference on Document Engineering, DocEng 2011, Mountain View, C A ,
Association of Computing Machinery (2011) 57-60 h t t p : / / d o i . acm. org/10.1145/
2034691.2034703.
5. Elbow, A., Krick, B., Kelly, L.: P M C Tagging Guidelines: A case study i n normalization.
In: Proceedings of the Journal Article Tag Suite Conference 2011, National Center
for Biotechnology Information (2011) h t t p : / / w w w . n c b i . n l m . n i h . g o v / b o o k s /
NBK62090/#elbow-S8.
6. W 3 C : M a t h M L Test Suite (2010) h t t p : //www. w3. o r g / M a t h / t e s t s u i t e / .
7. Archambault, D., Stöger, B., Batušič, M . , Fahrengruber, C , Miesenberger, K.: A
software model to support collaborative mathematical work between Braille and
sighted users. In: Proceedings of the ASSETS 2007 Conference (9th International
A C M S I G A C C E S S Conference on Computers and Accessibility), A C M (2007) 115-
122 http://portal.acm.org/ft_gateway.cfm?id=1296864&type=pdf.
8. Archambault, D., Berger, F., Mogo, V : Overview of the "Universal Maths Conversion
Library". In: Pruski, A . , Knops, H . , eds.: Assistive Technology: From Virtuality to
Reality: Proceedings of 8th European Conference for the Advancement of Assistive
Technology i n Europe A A A T E 2005, Lille, France, Amsterdam, The Netherlands,
IOS Press (2005) 256-260.
9. Archambault, D . , Moqo, V : Canonical M a t h M L to Simplify Conversion of M a t h M L
to Braille Mathematical Notations. In: Miesenberger, K , Klaus, J., Zagler, W.,
Karshmer, A . , eds.: Computers Helping People w i t h Special Needs. Volume 4061 of
Lecture Notes i n Computer Science. Springer Berlin / Heidelberg (2006) 1191-1198
http://dx.doi.org/10.1007/11788713_172.
10. Líška, M . , Sojka, P., Růžička, M . , Mravec, P.: Web Interface and Collection for
Mathematical Retrieval. In: Sojka, P., Bouche, T., eds.: Proceedings of D M L 2011,
Bertinoro, Italy, Masaryk University (2011) 77-84 h t t p : //www. f i .muni. c z / ~ s o j k a /
dml-2011-program.html.
11. Stamerjohanns, H , Kohlhase, M . , Ginev, D., David, C , Miller, B.: Transforming
Large Collections of Scientific Publications to X M L . Mathematics i n Computer
Science 3 (2010) 299-307 h t t p : / / d x . d o i . o r g / 1 0 . 1 0 0 7 / s l l 7 8 6 - 0 1 0 - 0 0 2 4 - 7 .
12. Sylwestrzak, W., Borbinha, J., Bouche, T., Nowiňski, A . , Sojka, P.: E u D M L —
Towards the European Digital Mathematics Library. In: Sojka, P., ed.: Proceedings of
D M L 2010, Paris, France, Masaryk University (2010) 11-24 h t t p : / / d m l . c z / d m l c z /
702569.
13. Řehůřek, R., Sojka, P.: Automated Classification and Categorization of Mathematical
Knowledge. In: Autexier, S., Campbell, J., Rubio, J., Sorge, V , Suzuki, M . , Wiedijk,
E , eds.: Intelligent Computer Mathematics—Proceedings of 7th International C o n -
Building Corpora of Technical Texts: Approaches and Tools 79
ference o n Mathematical Knowledge Management M K M 2008. Volume 5144 of Lecture
Notes i n Computer Science L N C S / L N A I . , Berlin, Heidelberg, Springer-Verlag
(2008)543-557.
14. Řehůřek, R., Sojka, P.: Software Framework for Topic Modelling w i t h Large Corpora.
In: Proceedings of L R E C 2010 workshop N e w Challenges for N L P Frameworks,
Valletta, Malta, E L R A (2010) 45-50 h t t p : / / i s . m u n i . c z / p u b l i c a t i o n / 8 8 4 8 9 3 / e n ,
software available at h t t p : / / n i p . f i .muni. c z / p r o j e k t y / g e n s i m .
15. Anca, §.: Natural Language and Mathematics Processing for Applicable Theorem
Search. Master's thesis, Jacobs University, Bremen (2009) h t t p s : / / s v n . e e c s .
j a c o b s - u n i v e r s i t y . d e / s v n / e e c s / a r c h i v e / m s c - 2 0 0 9 / a a n c a . p d f .
16. Grigore, M . , Wolska, M . , Kohlhase, M . : Towards context-based disambiguation of
mathematical expressions. Math-for-Industry Lecture Note Series 22 (2009) 262-271.
17. Materna, J.: LDA-Frames: an Unsupervised Approach to Generating Semantic
Frames. In: Proceedings of C I C L I N G 2012, Springer-Verlag (2012) 12 pages,
submitted.
18. Bělohlávek, R.: Concept lattices and order i n fuzzy logic. Annals of Pure and
A p p l i e d Logic 128(1-3) (2004) 277-298.