Readings on Knowledge Relationship Discovery

Two new TEAM members

2011-09-12T11:58:00.000-07:00

Two new TEAM members could be recruited by Mendeley and ELIKO in the TEAM project. Christian Prokopp starts at Mendeley working on topics models and their impact. Honghan Wu started at ELIKO and will focus on Linked Open Data and its usage in recommended systems. Their details can be found on the TEAM Research Page.

We are happy to have both on board for bringing our research project forward!

Kris Jack gives opening Keynote at the I-Know'11 Special Track on Recommendation, Data Sharing, and Research Practices in Science 2.0

2011-09-03T08:25:00.000-07:00

Next week the I-Know'11 conferences started, where the TEAM team organised the special track on Recommendation, Data Sharing, and Research Practices in Science 2.0. Kris Jack from Mendeley will give the opening keynote of the special track on "Mendeley: Crowed-Sourcing and Recommending Research on the Large Scale".

I am looking forward to hear his talk.

Author Disambiguation Presentation @ TIR Workshop

2011-09-03T08:09:00.000-07:00

This week i presented our work on author disambiguation at the TIR'11 workshop in Toulouse. The presentation outlined our findings on the need of very clean features and better model selection methods for disambiguating author names in the wild. Discussions raised the idea to use overlapping blocking methods and to apply outlier detection afterwards. That may be a nicer approach in solving the model selection problem.

Of course the presentation is also uploaded to the Mendeley based TEAM folder for sharing our documents in the project

All good things come to an end

2011-08-30T09:38:00.000-07:00

My secondment has finally come to an end. Overall it was a great experience. From my point of view, knowledge transfer worked perfectly in both directions. The achieved results are quite nice, since we could show that title extraction works reliably with support vector machines to be used in subsequent de-duplication methods. Detailed results will follow soon in a publication and a deliverable. For de-duplication, the comparison between finger printing and inverted index based methods has been triggered and will now be continued by James Hammerton in Graz. Ago Luberg from Eliko also addresses similar topics, but in the different scenario of knowledge acquisition from the web. So my work on that topics will fortunately continue.

Overall i see the TEAM project becoming more and more successful in establishing knowledge transfer among all participants.

Near-Duplicate-Detection, Metadata Extraction, Visualisation and other things

2011-06-23T08:36:00.000-07:00

Since there is so much interesting work to do at the secondment, i tend to forget writing blog posts on what I did. So this one will sum up the last 1.5 months, where i have investigated topics like near duplicate detection, metadata extraction and gave talks on visualisation of bibliographic data and metadata extraction.

Near duplicate detection is essential for the quality of a data set with many committers and sources, like it is the case in our use case. Fingerprinting is the traditional approach to near-duplicate detection, but it does not have the flexibility of a inverted index based approach. So i tried NDD using inverted indizes, in particular Lucene. Lucene is really lightning fast, which allows to achieve title lookups on a set of a 40 million metadata entries in in less than 200ms while still being able to add new titles in real time. Results in terms of accuracy are also promising, although a comparison with fingerprinting is still open. One particular question in the context of research paper management is how to recover from metadata extraction errors? Given a pdf and automatically extracted titles and authors, how good can we recover from errors? What accuracy can be achieved by metadata extraction using state-of-the-art methods like Conditional Random Fields?

Using Conditional Random Fields it was possible to rely on layout features like font-size, position etc. only to extract titles with an recall of appox. 0.8 and a precision of 0.7. Compared to state-of-the-art tools like ParsCit, which achieve similar accuracy but having more domain knowledge, that is quit good. Also experiments showed that metadata extraction, and hence near duplicate search, depend on the domain and the type of journal. Without re-training, ParsCit achieves great performance on IEEE Computer Science papers, but fails on Medical Papers from the BMJ. With the approach developed using Layout information, we can automatically adapt to different journal types and fields, which allows to improve accuracy and recall. I guess that is worth a publication. Working that out will take the rest of my secondment.

Near Duplicate Search on Sparse Metadata & Learn2Rank

2011-05-05T04:08:00.000-07:00

In the first month we focused on applying learning to rank to sparse metadata and to investigate the applicability of inverted index based metrics and lookups for near duplicate search. Results in both directions seem to be promising. Especially inverted indices using simple word grams or bi-word grams provide efficient near duplicate search facilities.

Next, learn to rank will find its way into tag recommendation in particular and recommendation in general. Basically, will learn to rank outperform traditional recommendation approaches? Lets see.

Starting my research stay at Mendeley

2011-04-07T11:33:00.000-07:00

Finally i started my research stay at Mendeley. We settled and i got the first impressions on how everything is working here, the city, the people and of course, colleagues at Mendeley.

The talks i did with people here helped to narrow down the research topics towards Learning-to-Rank and stochastic machine learning and identified possible application areas. Next week i will give a talk on that particular topic and maybe i will have first results. I am looking forward in presenting the possible research ideas and their application, as well as research topics my group in Graz is currently addressing.

[Topic] Centroid based Classification

2009-05-05T23:35:00.001-07:00

[1] claimed a very high increase in accuracy due to the use of a different centroid weighting scheme. The weighting scheme extracts the "discriminative" features. The increase is around 0.7-0.10 F1 measure.

[2] Analyzes centroid based learning approaches in detail. k-nn, c4.5 and centroid base approaches are compared. The success of centroid based approaches is explained as comparing the inter class similarity distribution (=Length of the centroid) vs. the average similarity of a new item to all documents (interpretation of centroid based cosine similarity). While the average similarity of a new items do not take term dependencies into account and suffer similar drawbacks than naive bayes algorithms (over estimate of positive term co-occurrences, underestimate of negative term co-occurrences), the second term (=centroid length) addresses the co-occurrence aspect. (see Section 5 of the paper for details)

Further the paper provides: statistical testing of classification results (resampled t-test and sign test)

[1] Guan, Hu and Zhou, Jingyu and Guo, Minyi (2009) A Class-Feature-Centroid Classifier for Text Categorization. In: 18th International World Wide Web Conference, April 20th-24th, 2009, Madrid, Spain.

http://www2009.eprints.org/21/

[2] Han, E. and Karypis, G. 2000. Centroid-Based Document Classification: Analysis and Experimental Results. In Proceedings of the 4th European Conference on Principles of Data Mining and Knowledge Discovery (September 13 - 16, 2000). D. A. Zighed, H. J. Komorowski, and J. M. Zytkow, Eds. Lecture Notes In Computer Science, vol. 1910. Springer-Verlag, London, 424-431.

http://portal.acm.org/citation.cfm?id=669671

[Paper] A comparative Study of Two Short Text Semantic Similarity Measures

2009-05-01T02:57:00.001-07:00

    Book Series -
    Book Title - Agent and Multi-Agent Systems: Technologies and Applications
    Chapter Title - A Comparative Study of Two Short Text Semantic Similarity Measures
    First Page - 172
    Last Page - 181
    Copyright - 2008
    Author - James Oâ€™Shea
    Author - Zuhair Bandar
    Author - Keeley Crockett
    Author - David McLean
    DOI - 10.1007/978-3-540-78582-8_18
    Link - http://www.springerlink.com/content/v0867641u342pm2

James O’Shea¹, Zuhair Bandar¹, Keeley Crockett¹ and David McLean¹

(1)	Department of Computing and Mathematics, Manchester Metropolitan University, Chester St., Manchester, M1 5GD, United Kingdom

Abstract

This paper describes a comparative study of STASIS and LSA. These measures of semantic similarity can be applied to short texts for use in Conversational Agents (CAs). CAs are computer programs that interact with humans through natural language dialogue. Business organizations have spent large sums of money in recent years developing them for online customer self-service, but achievements have been limited to simple FAQ systems. We believe this is due to the labour-intensive process of scripting, which could be reduced radically by the use of short-text semantic similarity measures. “Short texts” are typically 10-20 words long but are not required to be grammatically correct sentences, for example spoken utterances and text messages. We also present a benchmark data set of 65 sentence pairs with human-derived similarity ratings. This data set is the first of its kind, specifically developed to evaluate such measures and we believe it will be valuable to future researchers.

Keywords Natural Language - Semantic Similarity - Dialogue Management - User Modeling - Benchmark - Sentence

Important Points

Discussion and summary of different kinds of similarities (Taxonomic, related, goal derived and radial)
Introduction of a (small) test corpora and how the corpora was created. This includes some discussion on how humans rate.
Statement that co-occurrence measures yield also high similarity values for antonyms

[Paper] Sentence Similarity Based on Semantic Nets and Corpus Statistics

2009-04-21T01:51:00.001-07:00

Li, Y., McLean, D., Bandar, Z. A., O'Shea, J. D., and Crockett, K. 2006. Sentence Similarity Based on Semantic Nets and Corpus Statistics. IEEE Trans. on Knowl. and Data Eng. 18, 8 (Aug. 2006), 1138-1150. DOI= http://dx.doi.org/10.1109/TKDE.2006.130

ABSTRACT

Sentence similarity measures play an increasingly important role in
text-related research and applications in areas such as text mining,
Web page retrieval, and dialogue systems. Existing methods for
computing sentence similarity have been adopted from approaches used
for long text documents. These methods process sentences in a very
high-dimensional space and are consequently inefficient, require human
input, and are not adaptable to some application domains. This paper
focuses directly on computing the similarity between very short texts
of sentence length. It presents an algorithm that takes account of
semantic information and word order information implied in the
sentences. The semantic similarity of two sentences is calculated using
information from a structured lexical database and from corpus
statistics. The use of a lexical database enables our method to model
human common sense knowledge and the incorporation of corpus statistics
allows our method to be adaptable to different domains. The proposed
method can be used in a variety of applications that involve text
knowledge representation and discovery. Experiments on two sets of
selected sentence pairs demonstrate that the proposed method provides a
similarity measure that shows a significant correlation to human
intuition.

Points made:

Sentence Similartiy based on path length and depth in the WordNet hierarchy.
Word order similarity. The metric seems to work rather well.
Data Sets: Brown Corpus (Content&Statistical Information), WordNet (Semantics)
The paper points to a dataset created for estimating sentence similarity

Overall, good to read. Provides good resources to

Sentiment Detection and Opinion Mining

2009-04-21T01:26:00.001-07:00

Sentiment detection and opinion mining is currently a hot topic of extracting subjective opinions and assertions from web portals. A good survey is provided by Pang and Lee. The survey addresses several aspects of this field. Most important in the field of knowledge discovery and text mining is the question how algorithms for analysing unstructured texts written by web users differs with standard text mining tasks like text classification, named entity recognition. From the survey i have taken the following points

A smaller number of classes compared to text classification (e.g. positive, ambivalent, negativ vs. Topic hierarchies)
Higher dependency on subjective writing stile (e.g. sacarsm)
Higher dependency on common sense knowledge: Sentiments can be expressed using non sentiment words and comparing to very good/very bad situation (it feels like driving a car at 360 kmh)
High degree of subjectivity: Given the above sentence, some people may like it, some may not
Order effects might overthrough frequency effects

Sentiment Tasks

Polarity Opinion Classification: Deterine whether a piece of text is good or bad
Rating inference/ordinal regeression: Determine the scale of goodness/badness
Subjectivity Detection: Detect whether a piece of text contains subjective/objective material
Joint Topic/Sentiment analysis

Facts

Machine Learning using Unigram Models can achieve over 80% accuracy (Pang et. al. Thumbs Up! Sentiment Classification using Machine Learning)
Templates are more stable among domains (compared to IE)
Finding correct keywords expressing sentiments seems to be hard ("Go read the book" in movie vs. book domain)
Unclear whether bigrams help or not
POS Tagging can be considered as a rough version of WSD
Syntax has found to be usefull (dependency tree)
Negations count (as second feature, by transforming words e.g. NOT, deeper modelling)

[Paper] Sentence Similartiy Based on Semantic Nets and Corpus Statistics

2009-04-21T01:25:00.001-07:00

ABSTRACT

Sentence similarity measures play an increasingly important role in text-related research and applications in areas such as text mining, Web page retrieval, and dialogue systems. Existing methods for computing sentence similarity have been adopted from approaches used for long text documents. These methods process sentences in a very high-dimensional space and are consequently inefficient, require human input, and are not adaptable to some application domains. This paper focuses directly on computing the similarity between very short texts of sentence length. It presents an algorithm that takes account of semantic information and word order information implied in the sentences. The semantic similarity of two sentences is calculated using information from a structured lexical database and from corpus statistics. The use of a lexical database enables our method to model human common sense knowledge and the incorporation of corpus statistics allows our method to be adaptable to different domains. The proposed method can be used in a variety of applications that involve text knowledge representation and discovery. Experiments on two sets of selected sentence pairs demonstrate that the proposed method provides a similarity measure that shows a significant correlation to human intuition.

Points made:

Sentence Similartiy based on path length and depth in the WordNet hierarchy.
Word order similarity. The metric seems to work rather well.
Data Sets: Brown Corpus (Content&Statistical Information), WordNet (Semantics)
The paper points to a dataset created for estimating sentence similarity

Overall, good to read and very detailed. Provides good resources to sentence similarities

Recurrent Neural Networks for Robust Real-World Text Classiﬁcation

2009-02-26T03:45:00.001-08:00

Garen Arevian
2007 IEEE/WIC/ACM International Conference on Web Intelligence

ABSTRACT

This paper explores the application of recurrent neural networks for
the task of robust text classification of a real-world benchmarking
corpus. There are many well-established approaches which are used for
text classification, but they fail to address the challenge from a more
multi-disciplinary viewpoint such as natural language processing and
artificial intelligence. The results demonstrate that these recurrent
neural networks can be a viable addition to the many techniques used in
web intelligence for tasks such as context sensitive email
classification and web site indexing.

Noteworthy

Use of recurrent neural networks (Elman Networks) with a context layer, able to consider word orders
Further references for NN's in text mining
Title based semantic representation (at least pointers to prior literature on the topic)
Word order was not important
The claim made that NNs acn outperform other classifiers is very strong and does not hold in general

Information Retrieval System Evalution: Effort, Sensitivity, and Reliabilitiy

2009-02-16T09:06:00.001-08:00

Information Retrieval System Evaluation: Effort, Sensitivity, and Reliability
Mark Sanderson, Justin Zobel

The paper is excellent in terms of comparing IR Systems and the difference in MAP and other measures. A must read for evaluation.

Abstract: The effectiveness of information retrieval systems is measured by comparing performance on a common set of queries and documents. Significance tests are often used to evaluate the reliability of such comparisons. Previous work has examined such tests, but produced results with limited application. Other work established an alternative benchmark for significance, but the resulting test was too stringent. In this paper, we revisit the question of how such tests should be used. We find that the t-test is highly reliable (more so than the sign or Wilcoxon test), and is far more reliable than simply showing a large percentage difference in effectiveness measures between IR systems. Our results show that past empirical work on significance tests over-estimated the error of such tests. We also re-consider comparisons between the reliability of precision at rank 10 and mean average precision, arguing that past comparisons did not consider the assessor effort required to compute such measures. This investigation shows that assessor effort would be better spent building test collections with more topics, each assessed in less detail.

Important Aspects Covered:

Brief introduction to statistical significance testing in IR (how and why)
Summary of results found by Zobel and Vorhees/Buckley: 8-9% MAP difference on 25 topics (conf = 95%)m, 5-6% MAP difference on 50 topics (conf = 95%)
Impact of significance testing on projecting MAP accuracy.
Large difference in MAP does not necessarily imply a statistical significant difference, especially on small topic set sizes (e.g. 25). At its worst, comparison must be significant and the difference for MAP must be higher than 10%.
T-Test produces lower error rates than sign and Wilcoxon test
MAP is more reliable than P@10, but building a reliably P@10 only collection should be cheaper (From an assessors point of view). However, the stability of shallow pool sizes is unclear, not yet tested.

Mini How-to write a KRD/KDD Research Paper

2009-01-29T08:45:00.001-08:00

I recently stumbled over the ACM SIG KDD 09 Call for Papers, which contains a excellent and comprehensive guid on writing an good research paper...at least for data intensive domains ;)

You can find the link here. The important part is also cited below:

" In writing your paper, we suggest you try to address the following questions, credited to George Heilmeier:

What are you trying to do? Articulate your objectives using absolutely no jargon.
How is it done today, and what are the limits of current practice?
What's new in your approach and why do you think it will be successful?
Who cares?
If you're successful, what difference will it make?
What are the risks and the payoffs? (in other words, what are the limitations and strengths of your work)
What
are the midterm and final "exams" to check for success? (in other
words, what are the measures of evaluation and evidence of success)

In light of the above principles, we suggest
the following guidelines for the paper content. Note that the headings
and the structure below are meant to be general categories; please
exercise your discretion and creativity to make the paper as
comprehensible as possible to the readers and reviewers.

Abstract

Try to include the following:

Motivation: one or two sentences on the problem and it significance;
Results: a short paragraph on approach and results;
Availability: a link to code, data, and supplementary materials,
or a statement why this is not possible.

Motivation & Significance

What is the problem and why is it important or significant?

Problem Statement

Formal definition of the problem with any preliminary concepts.

Prior Work & Limitations

What are the existing approaches, and their limitations?

Theory/Algorithm

Discuss the main theoretical or algorithmic ideas of the paper;
Mention the main theorems (if any), the intuition behind those, and their
practical application. Move the proofs to the appendix, unless the
proof itself is the main contribution;
Discuss your algorithmic solution (if any) at the conceptual level with
pseudo-code, to convey the main ideas. Move minute (but
practically important) implementation details to the appendix;
Discuss why you chose certain paths, and discuss unfruitful
paths that you discarded. In other words, give both the
theoretical and/or algorithmic "insights" into your work.

Experiments or other Evidence of Success

Complete parameter settings and data descriptions should be
provided (including any links to public resources);
Clearly specify the experimental procedure, including evaluation
measures;
Compare to prior solutions, or at least to "strawman" solutions;
Clearly discuss the results and what they mean;
Only include the most relevant experiments here, using the
appendix to provide any additional results (say on minor parameter
tuning of your method, etc).

Discussion and Future Work

Describe insights you gained, the limitations and applicability of
your work, and directions for future research. Every solution has
limitations, which should be explicitly mentioned.

References

Include the most relevant works, making sure all citations are complete
(including editors, publishers, page numbers, etc.).

APPENDIX

You should use the appendix for supporting details. For example, you
may use it to convey detailed technical/practical aspects of your
implementation. You may use the appendix for theorem proofs, or for
additional experimental results. Include include pointers in the
main paper to relevant sections in the appendix.

The appendix is an integral part of the paper, since it will provide
details that are important for a proper appreciation of your work
(e.g., for replicating or extending it, or for comparison).
However, it should be possible on a first read-through to get a good
understanding of the paper's contribution from the main part alone.
Structuring the paper in this way provides a service to the reader,
by separating main ideas from technical details."

Text classification datasets with splits

2009-01-25T09:19:00.000-08:00

...can be found here. It is the 20 Newsgroup data set and the TDT2.

Statistical Machine Translation

2009-01-23T00:15:00.001-08:00

I recently stumbled over a reasonable good survey on Statistical Machine Translation from Lopez [1] . Starting with the IBM Model 3 and 4 it explains the critical steps of machine translation like
1. selection of the translational model (e.g. Transducers, Synchronous Context Free grammars)
2. Parametrization of the model, i.e. what are the parameters which can be learned (e.g. fertility of words, word alignment etc.)
3. Parameter estimation, i.e. how to estimate the values of parametrization (e.g. using generative or discriminative statistical models)
4. Decoding, which is simply translating new text based on the selected and parametrized model

Overall, it contains some interesting detail insights on problems like how to deal with sequences and the difference between discriminative and generative statistical models (see also CRF Introduction). Worthy to read.

Open Source Resources:
[Moses] http://www.statmt.org/moses/
[Overview] http://opentranslation.aspirationtech.org/index.php/Open_Source_Translation_Tools

[1] Lopez, A. 2008. Statistical machine translation. ACM Comput. Surv. 40, 3 (Aug. 2008), 1-49. DOI= http://doi.acm.org/10.1145/1380584.1380586

Conditional Random Fields and Graphical Models

2008-12-25T05:17:00.001-08:00

I am currently reading into the topic of Conditional Random Fields, Hidden Markov Models in particular and Graphical Models in general. A perfect tutorial on this topics is provided by Sutton and McCallum [1]. It is more than readworthy and gives
a basic introduction to relational learning for graphical models
an overview on CRF and HMM as well as their application
Generative vs. descriptive models (i.e. Naive Bayes vs. Linear Regression)
Parameter estimation, backward-forward estimation and application of gneral and linear chain CRF's
Application of general CRF's (i.e. skip chain CRF) for information extraction
A must read for everybody interested in information extraction and relational learning state-of-the-art

[1] Introduction to Conditional Random Fields for Relational Learning
Charles Sutton and Andrew Mccallum MIT Press, (2006)

What is it for?

2008-12-21T03:10:00.000-08:00
This blog gathers stuff I read on knowledge relationship discovery or in more detail on machine learning, natural language processing, semantic technologies and all those stuff.
Entries will be mostly used for personal recall of stuff i stumbled over in the past, so all entries may not be self contained and may require some know-how in the above fields. However, if you can take away something you are welcome