Advice Collection

I came across a useful collection of links for Ph.D. students. It offers dissertation advice, presentation advice, and more....I read some of these articles in the past but it is nice to have a central location for reference.

Neural Network Framework for Java

I spent the last month learning how to use Self-Organizing Maps (SOM) for my Neural Network course. I used a SOM to perform instance matching (which is not typically what it is used for) with the intention that possibly it could be used in a 2-level fashion or with some other supervised approach. Think of SOM as a clustering technique. It maps high dimensional data into a lower dimension (typically 2-D) space and it enables one to visually see the data in 2-D. The beauty of a SOM is that it is unsupervised which means you do not need to specify the desired output for your training set.

It outperformed K-Means when running comparison tests using the OAEI IIMB benchmark both in F-Measure scores and CPU time.


I used Encog for the Neural Net framework. I experienced a lot of memory issues but for the most part I was quickly running a SOM, K-Means and SVM comparison test.

For the next test, I think using Matlab, Weka or R might be a better approach. As much as I like to keep things nice and clean in the code. I quickly have memory issues as I increase the number of instances to test.

Code Sample for Encog SOM (based on the Encog example):

//Set of the training data, no desired output in this case
MLDataSet training = new BasicMLDataSet(trainingInput,null);

// Create the SOM neural network with an input count and an output count
// This is basically your input node size and output node size
// One point of improvement
SOM network = new SOM(inputNodeSIze,ouputNodeSize);

//reset the nework
network.reset();

//Here you specify your parameters i.e. learning rate and neighborhood function
//I used the NeighborhoodSingle here but clearly that is not the best choice
//Next round of tests will use a RBF and a GaussianFunction
//.7 for learning rate is not unreasonable
BasicTrainSOM train = new BasicTrainSOM(
network,
0.7,
training,
new NeighborhoodSingle());
//new NeighborhoodRBF(sizes, RBFEnum.Gaussian)

//store the winner in a space in the 2-d array reserved
//calling code will lump instances that have the same winner
//to determine which instances are 'similar'
double[][] newItems = new double[input.length][];
int i=0;
for (double[] item: input)
{
item[item.length-2]=network.winner(new BasicMLData(item));
newItems[i] =item;
i++;
}
Encog.getInstance().shutdown();

Paper Summary - Toward Conditional Models of Identity Uncertainty with Application to Proper Noun Coreference - Part 1

Toward Conditional Models of Identity Uncertainty
with Application to Proper Noun Coreference
A. McCallum and B. Wellner


This paper is interesting. They make the point that pairwise decisions may not always be independent of others. One may be able to resolve inconsistencies by using a dependence model. They mention work, Relational Probabilistic Model, which captures this dependence. However since it is a generative model, they state this could lead to complexities due to many features with varying degrees of granularity. They discuss Hidden Markov models and conditional random fields briefly and Relational Markov networks as a similar model but improved classification.

They then discuss their work specifically which is "three conditional undirected graphical
models for identity uncertainty" which make the coreference decisions. Their first model connects mentions, entity-assignments, and each attribute of the mention. Edges indicate dependence. There is the concept of a clique, parameters may be part of different cliques which results in patterns of parameters called clique templates. Parts of the graph that depend on a number of entities are removed and replaced with random variables indicating coreference (Read this paper again to make sure we are clear on this). Per-entity attribute nodes are removed and replaced with attributes of mention. They then use graph partitioning. There is a lot in this paper and really requires another read to understand their methods better.

Paper Summary - Disambiguation and Filter Methods in Using Web Knowledge for Coreference Resolution

Disambiguation and Filter Methods in Using Web Knowledge for Coreference Resolution
O. Uryupina and M. Poesio

They describe how they use Wikipedia and Yago to increase their Coreference Resolution performance. They use BART to support their efforts. Their classification consists of a anaphor and a potential antecedent, as they describe. Using their associated feature vectors, they use a 'maximum entropy classifier' to determine coreference. They used Wikipedia to improve their aliasing algorithm, which would perform string matching functions. They use Wikipedia based information as a feature, and to disambiguate mentions. They use Yago to supplement their efforts when there are too few features to make any reasonable decisions related to coreference. Yago information is also incorporated as a feature. They tested using ACE with reasonable scores.

Using these publicly available knowledge bases appears to improve performance (2-3% in this case). Something to think about....

Stanford Online AI Course

This course is offered for Fall 2011 semester and the instructors are Sebastian Thrun and Peter Norvig. It should be a good class. The formal title is "Introduction to Artificial Intelligence".

Join

Boom Time In Silicon Valley?

In case you missed this over the weekend, apparently in Silicon Valley the next big boom is occurring, at least according to the LA Times.

For those keeping their eye on the market for that special time to start-up, this may be good news. Still too early to know for sure.

Intuition

There was an interesting question posed on the Linked In AGI group discussion board:
Has anyone put out a suggestion on how to impliment an "Intuition" engine?

Responses were also quite interesting...

Has anyone successfully built an intuition engine? The responses ranged from a weak description of how one might do this to long detailed descriptions of current research that has been ongoing for many years.

If this sounds interesting you may want to join the Linked In group AGI — Artificial General Intelligence.

Or go to the AGI Conference in August .

Linked Data Paper Summary

"Linked Data - The Story So Far", C. Bizer, T. Heath, T. Berners-Lee, 2009, http://eprints.ecs.soton.ac.uk/21285/1/bizer-heath-berners-lee-ijswis-linked-data.pdf


My work will support working with linked data so I am attempting to build a better understanding of this topic.

This paper is good for providing a very basic understanding of linked data. If you are new to the concept of linked data, this is a good starting paper to read. It provides basic principles, examples, and isn't too technical.

If you already have a good understanding of the basics, skip this paper. I read it in about 10 minutes and it was pretty much just a review of what I already knew.

Hadoop Meet-up - Large Scale Graph Processing On HBase and Map/Reduce on Greenplum

I attended the Hadoop Meet-up on Tuesday titled "Large Scale Graph Processing On HBase and Map/Reduce on Greenplum". You can view the event here.

I attended this event for two reasons: It has been a couple of years since I worked intimately with Hadoop and I wanted to see how others are using it. I was also hoping the discussion on Large Scale Graph Processing would be useful for my research.

Though the presentations were somewhat stimulating, I didn't find much I could use for my work.

Canopy Clustering

"Efficient Clustering of High Dimensional Data Sets with Application to Reference Matching", McCallum,Nigam,Ungar,http://www.kamalnigam.com/papers/canopy-kdd00.pdf

This paper discusses a different type of clustering, titled canopy clustering. It is an interesting idea. There are basically two thresholds, using a 'cheap distance metric', we evaluate a list of points. Threshold 1 is > than Threshold 2. Pick one point to compare with all the other points in the list. When the distance between the two points falls within T1 put the points into a canopy. If the distance falls within T2 then remove point from list. We generate the canopies this way and work through the list until empty.

We can then apply our second level of clustering to each canopy and are pretty much guaranteed that if two points do not fall into the same canopy then they are likely not to be co-referent and therefore do not need to be evaluated.

This is efficient and elegant. Currently the only implementation that I found of canopy clustering is in Mahout. I am building my own implementation though to get a feel for how well it works.

SimHash: Hash-based Similarity Detection

"SimHash: Hash-based Similarity Detection", Sadowski, Levin, 2007.

This paper outlines a hash algorithm that can be used for similarity detection. Most hash algorithm are designed to offer low collision and hash values for similar strings can vary quite a bit. This hash basically sets out to achieve the opposite, higher collision and hash keys for similar strings are similar if not the same.

If you cannot use term frequency and need a numeric representation of a string for statistical processing, what process can be used? Using an integer-based hash is one way to achieve this, though in my opinion it is not the most sophisticated of approaches.

An implementation of this algorithm showed that it is a reasonable approach for hashing strings with the intent to determine similarity. I found minor issues which I will address by altering the algorithm.

Results showed that this is a reasonable approach....

Narrowing the Modeling Gap: A Cluster-Ranking Approach to Coreference Resolution

"Narrowing the Modeling Gap: A Cluster-Ranking Approach to Coreference Resolution"
Journal of Artificial Intelligence Research 40 (2011) 469–521 Submitted 06/10; published 02/11
Altaf Rahman altaf@hlt.utdallas.edu
Vincent Ng vince@hlt.utdallas.edu
Human Language Technology Research Institute
University of Texas at Dallas
800 West Campbell Road; Mail Station EC31
Richardson, TX 75080-3021 U.S.A.
http://www.jair.org/media/3120/live-3120-5478-jair.pdf

-Long paper, very thorough
-A lot of history, use the citations in this paper
-Learn more about "centering algorithms"
-Describes three different models, mention-pair,entity-mention and mention-ranking
-Outlines key features and deficiencies of each
-In particular the transitivity property is not addressed in the mention-pair model so clustering is used
-Mention-ranking outperforms mention-pair
-Describe a cluster-ranking approach combines both models
-Use lexicalization and knowledge of anaphoricity
-Used ACE for experiments

Interesting:

1. 
   "Specifically, a classifier that is trained on
   coreference-annotated data is used to determine whether a pair of mentions is co-referring
   or not. However, the pairwise classifications produced by this classifier (which is now commonly
   known as the mention-pair model) may not satisfy the transitivity property inherent
   in the coreference relation, since it is possible for the model to classify (A,B) as coreferent,
   (B,C) as coreferent, and (A,C) as not coreferent. As a result, a separate clustering mechanism
   is needed to coordinate the possibly contradictory pairwise classification decisions and
   construct a partition of the given mentions."
   
2. 
   Read about Lappin and Leass’s algorithm
   
3. 
   Read about centering algorithms
   
4. 
   "the distinction between
   classification and ranking applies to discriminative models but not generative models.
   Generative models try to capture the true conditional probability of some event. In the context
   of coreference resolution, this will be the probability of a mention having a particular
   antecedent or of it referring to a particular entity (i.e., preceding cluster). Since these probabilities
   have to normalize, this is similar to a ranking objective: the system is trying to raise
   the probability that a mention refers to the correct antecedent or entity at the expense of
   the probabilities that it refers to any other. Thus, the antecedent version of the generative
   coreference model as proposed by Ge et al. (1998) resembles the mention-ranking model,
   while the entity version as proposed by Haghighi and Klein (2010) is similar in spirit to the
   cluster-ranking model."
   

Linux on Windows

If you aren't aware of wubi yet. It is actually a great way to run Linux on Windows Ubuntu flavor. The installation is easy and you can control how much disk space you want to use. I am slowly rebuilding my laptops to run Linux but in the meantime this is a nice way to keep Windows and run Linux too.

Get it

Hadoop + SPARQL

I began working with cloud computing about 2 years ago because of my interest in using this environment for semantic web applications. It seems to be of interest to others too.

https://opencirrus.org/content/sparql-query-over-hadoop-very-large-rdf-dataset
http://portal.acm.org/citation.cfm?id=1779599.1779605
http://cs264.org/projects/web/Rohloff_Kurt/rohloff/index.html

Paper Summary - A Framework for Combining Ontology and Schema Matchers with Dempster-Shafer

"Paper Summary - A Framework for Combining Ontology and Schema Matchers with Dempster-Shafer", P. Besana


This is a short paper about using Dempster-Shafer for ontology mapping. They have a tool based on their work: PyontoMap. This paper is really relevant so the summary will be deferred.

Paper Summary - BeliefOWL: An Evidential Representation in OWL Ontology

Amira Essaid and Boutheina Ben Yaghlane, BeliefOWL: An Evidential Representation in OWL Ontology, pages 77-80, International Semantic Web Conference, International Workshop on Uncertainty Reasoning for the Semantic Web, Washington DC, USA, 2009.


This paper is very short, only 4 pages. It starts with a discussion of how uncertainty is represented currently in ontologies using either probabilistic or fuzzy approaches. It then proposed the Dempster-Shafer approach as another option. They discuss the work by :
Ben Yaghlane,B.: Uncertainty representation and reasoning in directed evidential
networks, PhD thesis, Institut Sup´erieur de Gestion de Tunis Tunisia, 2002.

which is work related to representing uncertainty using a DAG. I haven't read this paper yet but it certainly seems like a good read.

This paper then goes on with a presentation of BeliefOWL, their uncertainty extension to OWL.


They define two classes to represent prior evidence:


- enumerates different masses and has object property which specifies the relation between itself and .


- expreses prior evidence and has property



They define two classes which represent conditional evidence:


- has an object property of


- conditional evidence with property



They construct an evidential network by translating the OWL ontology into a DAG. They then assign masses to nodes in the DAG. Details of this work are mentioned but briefly.

Overall I don't know if this helps my work in anyway except to see some uses of DS with ontologies.

Paper Summary - Uncertainty in Ontologies: Dempster-Shafer Theory for Data Fusion Applications

"Uncertainty in Ontologies: Dempster-Shafer Theory for Data Fusion Applications", A.
Bellenger1 and S. Gatepaille, Defence and Security Information Processing, Control and Cognition department, France

This paper is relevant to my work because they use DS to represent uncertainty in ontologies. They do this by creating an upper ontology that contains the DS measures calculated i.e mass, belief, plausibility, etc.


The paper starts with a background in data fusion and gives some examples of how uncertainty is captured in ontologies and why it is important to represent uncertainty. They define uncertainty as "incomplete knowledge, including incompleteness, vagueness, ambiguity, and others". In addition to the natural occurrence of uncertainty in data, it is also a product of fusing data which may be acquired from different sources.

This is an interesting statement: " If the user/application is not able to decide in favor of a single alternative (due to insufficient trust in the respective information sources), the aggregated statement resulting from the fusion of multiple
statements is typically uncertain. The result needs to reflect and weight the different information inputs appropriately, which typically leads to uncertainty."

This is the common in military applications and in general knowledge bases because one attempts to acquire supporting data for entities in the knowledge base from various sources that can be unreliable.

They briefly discuss the shortcomings in current traditional methods to handle uncertainty in ontologies. They state that since ontologies are designed to contain concepts and relations only that describe asserted facts about the world, that they are not designed to handle uncertainty. The facts asserted are assumed to be 'true'. Therefore even information that is not certain to be 'true' are stored and lead to errors or inaccurate information. There is not a standard way to handle uncertainty currently (can read more on this).

They discuss how probability is used as a way to represent uncertainty in ontologies. They discuss some existing work in this area including (BayesOWL). The problem with this approach in particular is that it does not account for OWL properties, instances of the ontologies or the data types. There are also extensions to DL (Pronto is one of them), however performance is a problem. There are also Fuzzy approaches that exist.

They then discuss using DS. DS is presented as a generalized probability theory, however books related to this topic are not exactly is agreement with this representation. Masses are calculated and the sum of these masses make up the beliefs. It is also noted that is supports combining evidence from different sources which makes it especially useful for fusing data from different sources. They note work that actually use DS to handle the inconsistencies produced by mapping ontologies. However it also highlights a relevant paper that translates an OWL taxonomy into a directed evidential network.

The rest of the paper discusses their approach and how they use DS for modeling and reasoning. The point they make about uncertainty and why probabilistic methods can't represent it accurately is p-methods do not represent the absence of information very well. One needs to specify prior and conditional probabilities. They argue this leads to a minimax error due to is nature of symmetry prior probability assignment (.5) when information is not available. With DS missing information is not applied unless obtained indirectly. It allows one to specify a degree of ignorance (some define this as an upper and lower bound). They find this property to be appealing.


Probabilistic approaches use singletons only where DS allows one to use composites in addition to singletons. This is powerful. With probability theory there is a relationship between an event and its negation, DS does not imply a relationship between an event and its negation, it only models beliefs associated with a class.

They mention an additional point that I find makes this approach appealing. DS provides a way to combine evidence from different sources. This makes it especially useful for fusion.

They state, "the evidence theory is much more flexible than the probability theory". This is a strong statement and I'm not sure if it is completely true based on other papers that show how both Bayesian and DS can produce similar results.

Ok the paper ends with their approach. They discuss their proposed model which is an upper ontology representing the uncertainty. A DS_Concept which is a subclass of OWL:Thing has a DS_Mass, DS_Belief, DS_Plausibility, and a DS_Source. The Uncertain_Concept represents a concept that is part of the set. There is an object property is_either which has a range of owl:Thing so that all instances can be used.

This paper isn't cited by anyone else but I think there are good ideas proposed here and I am using this paper in my 601 work.

Papers To Read

http://www.dsto.defence.gov.au/publications/2563/DSTO-TR-1436.pdf
http://www.isif.org/fusion/proceedings/fusion03CD/special/s31.pdf
http://uima.apache.org/downloads/releaseDocs/2.3.0-incubating/docs/pdf/tutorials_and_users_guides.pdf
http://www.autonlab.org/tutorials/bayesnet09.pdf
http://spiedl.aip.org/getabs/servlet/GetabsServlet?prog=normal&id=PSISDG004051000001000255000001&idtype=cvips&gifs=yes&ref=no
http://www2.research.att.com/~lunadong/publication/fusion_vldbTutorial.pdf
http://www.aaai.org/aitopics/pmwiki/pmwiki.php/AITopics/Uncertainty
http://www.cs.cmu.edu/afs/cs/academic/class/15381-s07/www/slides/032207probAndUncertainty.pdf
cox's theorem
http://www.britannica.com/bps/additionalcontent/18/35136768/Data-Fusion-for-Traffic-Incident-Detection-Using-DS-Evidence-Theory-with-Probabilistic-SVMs
http://data.semanticweb.org/workshop/ursw/2009/paper/main/5/html
http://portal.acm.org/citation.cfm?id=1698790.1698821
http://volgenau.gmu.edu/~klaskey/papers/LaskeyCostaJanssen_POFusion.pdf
http://www.slideshare.net/rommelnc/ursw-2009-probabilistic-ontology-and-knowledge-fusion-for-procurement-fraud-detection-in-brazil
http://www.eurecom.fr/~troncy/Publications/Troncy_Straccia-eswc06.pdf
http://www.glennshafer.com/assets/downloads/articles/article48.pdf
http://www.fusion2008.org/tutorials/tutorial05.pdf
http://www.google.com/url?sa=t&source=web&ct=res&cd=5&ved=0CCcQFjAE&url=http%3A%2F%2Fciteseerx.ist.psu.edu%2Fviewdoc%2Fdownload%3Fdoi%3D10.1.1.62.9835%26rep%3Drep1%26type%3Dpdf&rct=j&q=dempster+shafer+tutorial&ei=UprNS4m9K4P88Ab5v-GVAQ&usg=AFQjCNFUUt_xSeT2QOkrqYvsLySWOllqCw&sig2=RLqpJoODSs1kgLFK869Ikw
http://www.cs.cf.ac.uk/Dave/AI2/node87.html
http://www.autonlab.org/tutorials/bayesnet09.pdf
http://sinbad2.ujaen.es/sinbad2/files/publicaciones/186.pdf
http://www.ensieta.fr/belief2010/papers/p133.pdf
http://www.gimac.uma.es/ipmu08/proceedings/papers/057-MerigoCasanovas.pdf
http://www.sas.upenn.edu/~baron/journal/jdm7803.pdf
http://classifier4j.sourceforge.net/usage.html
http://sunsite.informatik.rwth-aachen.de/Publications/CEUR-WS/Vol-527/paper1.pdf

Research Paper Summary - A General Data Fusion Architecture

H Carvalho, W Heinzelman, A Murphy, and C Coelho. A
general data fusion architecture. In Int. Conf. on Info. Fusion,
pages 1465–1472, 2003.


This is a short paper that describes an architecture for data fusion. What they are proposing is a taxonomy that defines 3 types of fusion: data oriented, variable oriented, and a mixture of the two. They are making a clear distinction between data as a measurement of the environment and variable as determined by feature extraction.

They describe examples of sensor data and state that the data needs to be pre-processed before fused. The pre-processing can involve conversions of a signal or filtering or handling noise. After pre-processing the data can be fused and they are proposing a 3-level data fusion framework. They begin by classifying the data as defined by the taxonomy. Basically when the fusion occurs defines what type of fusion we are dealing with (data, variable or mixture).

They go into a few examples of using this architecture. In general, the paper is not detailed enough to understand if the approach is viable. It is high level and short. It does provide additional information about the formalities of data fusion which is useful.

Paper Summary - A New Technique for Combining Multiple Classifiers using The Dempster-Shafer Theory of Evidence

Al-Ani, A. & Deriche, M. (2002) A new technique for combining multiple classifiers using the dempster shafer theory of evidence. In Journal of Artificial Intelligence Research, 17, (pp. 333—361)

This paper describes a new technique based on Dempster-Shafer to combine classifiers. The basic premise is that different types of features may be used depending upon the application. With different features, the same classifier may not always be best. So based on the features, a different classifier may outperform others. By combining classifiers they propose this is an efficient way to achieve the best classification results.

There are two problems defined by others, how to determine which classifiers to use and how to combine the classifier results to get the best results. They are addressing the second question in this paper.


They categorize the output of classification algorithms into 3 levels:

• the abstract - outputs a unique label


• the rank - ranks all labels with label at top as first choice


• the measurement levels - attributes to each class a value reflecting degree of confidence that input belongs to class

They state the measurement level contains the 'highest amount of information' and they use this level for their work.

Two combination scenarios mentioned:

• all use the same representation of input pattern


• each uses its own representation

Relating to item 2 they found from another study that using a joint probability distribution using the sum rule gave the best results. They also quote a study that used weighted sums, and another that used a cost function to minimize MSE in conjunction with A NN. In this same study that used NN, a number of NNs were used to produce linear combination. Combining the results from the NN, they used Dempster-Shafer theory. They give a few other approaches and then the rest of the paper discusses their approach.

They combine classifier results using a number of different feature sets. Each feature set is used to train a classifier. For some input x, each classifier will produce a vector that conveys the degree of confidence that the classifier has for each class given the input.

They then discuss DS. DS is said to represent uncertainties better than probabilistic techniques such as Bayesian. For classifier combination, they stress this is important since there usually exists "a certain level of uncertainty associated with the performance of each classifier". Other classifier combination methods that use DS theory do not accurately estimate the evidence of classifiers, they state and believe that their approach which uses gradient descent learning minimizes the MSE between the combined output and target output of the training set.

They then go into detail about the math behind DS and about their approach.

Note DS Belief and Plausibility formulas from wikipedia:

Belief:

Plausibility:

Note DS Rule of combination:


where:



I need to return to this to describe their method. It is detailed and involves a lot of math.

Why am I reviewing this document. Well, this is a little off topic but I thought any exposure to methods that use DS will help me understand it better.