List of papers
UNSUPERVISED LEARNING / MANIFOLD
@article{gongD-zhao-medioni-12icml-multiple-manifold-structure-learning,
title={Robust Multiple Manifolds Structure Learning}, [pdf]
}}
@InProceedings{leQ-ranzato-ngA-12icml_high-level-features-large-scale-unsupervised,
author = {Quoc Le and Marc'Aurelio Ranzato and Rajat Monga and Matthieu Devin and Kai Chen and Greg Corrado and Jeff Dean and Andrew Ng},
title = {Building high-level features using large scale unsupervised learning}, [pdf]
}}
@InProceedings{kulis-jordan-12icml_revisiting-k-means-bayesian-nonparametric,
author = {Brian Kulis and Michael Jordan},
title = {Revisiting k-means: New Algorithms via Bayesian Nonparametrics}, [pdf]
}}
@inproceedings{chua-marsland-guesgen-11ijc_unsupervised-data-streams-patterns-w-edit-distance,
title={Unsupervised learning of patterns in data streams using compression and edit distance}, [pdf]
}}
@inproceedings{ackerman-benDavid-11_how-to-select-hierarchical-clustering-algo,
title={Discerning linkage-based algorithms among hierarchical clustering methods}, [pdf]
}}
@inproceedings{lawrence-11_spectral-dimensionality-reduction-via-maximum-entropy-NLDR-MDS,
title={Spectral dimensionality reduction via maximum entropy}, [pdf]
}}
@inproceedings{netzer-ng-11_digits-in-images-unsupervised-feature-learning,
title={Reading digits in natural images with unsupervised feature learning}, [pdf]
}}
@inproceedings{ciresan-meier-11ijc_convolutional-NN-for-image-classification,
title={Flexible, high performance convolutional neural networks for image classification}, [pdf]
}}
@article{nair-hinton-09_3d-object-recog-deep,
title={3D object recognition with deep belief nets},
author={Vinod Nair and Geoffrey E. Hinton},
journal={Advances in Neural Information Processing Systems},
volume={22},
pages={1339--1347},
year={2009},
abstract= {
3D object database : NORB
---review 2013 Vishal K Gupta
Overview:
Recent advancement in DBNs have showed that it is possible to learn multiple
layers of non-linear features without actually using labelled data. Object
recognition is one of the prominent challenges of artificial intelligence
these days and and DBNs on account of their unsupervised feature learning
have contributed a lot in this field. Greedy layerwise training is performed
i.e training is done for one layer at a time as "Restricted Boltzman Machine"
using "Contrastive Divergence". Fine tuning of the net is done using
supervised backpropagation after pretraining.
=> Restricted Boltzman Machine: An invariant of Boltzman Machine, with the
restriction that each connection must be between a hidden unit and a
visible unit, unlike recurrent network (having connections among hidden
units also). Its a kind of model which is generative in nature and tries
to learn probability distribution over its set of inputs[1][2].
=> Contrastive Divergence: It is one of the methods for trainig RBNs which is
also fast enough. We propose a probability distribution and try to fit the
input data to that probability distribution by using many cycles of Markov
Chain Monte Carlo sampling. Since using many cycles of MCMC sampling is
time consuming, we use few cycles of sampling in order to compute
approximate gradient instead of computing accurate gradient. The intution
behind this is that after a few iterations data will have moved from the
target distribution towards proposed distribution[1][2][3].
Theory Explained:
Till now DBNs only comprises of two types of observed units i.e one for the
label of the object and one for the penultimate feature vector irrespective
of what is happening at the hidden level(hidden layer). This paper presented
a Third-Order RBM as the top level model in which a joint distribution is
moddled taking hidden unit also into consideration.The figure below presents
a rough idea of initial and present approach.
In this way the parameters form a 3D tensor instead of a matrix as in earlier
case.
An energy function is defined for the model which is given by
where W is a scaleable parameter. And the probability of full configuration
is given by the following equation, where Z represents the partition
function.
Defining label vector as a discrete random variable having K states represented as 1-of-K encoding, it is observed that k-th component of label is if "1", then k-th slice of the tensor defines our energy function.
So we infer that the distribution that we are trying to model is P(l|v) for classification purpose and P(v,l|h) and P(h|v,l) for learning based on Contrastive Divergence. Once l is observed the model reduces back to an RBM with parameters as k-th slice of 3D tensor. The whole computation takes place in O(NvNhNl)
=>Learning:
Contrastive Divergence learning is bascically formulated for bipartite architectured RBM as maximum likelihood learning is intractable. In this paper CD learning is extended for third order RBM also. Maximum likelihood gradient is computed by MCMC algorithm till the sampling chain reaches equilibrium. However, CD learning uses only three half steps of this chain initialized from a training data instead of randomly initializing.
==>Algorithm:
1) For a given training pair {v+,lk+=1}, we sample h+~P(h|v+,lk+=1).
2) Compute the produt D+=v+h+T.
3) Sample {v-,l-}~P(v,l|h+). Let lm-=1.
4) Sample h- ~ P(h|v-,lm-) = 1.
5) Compute the outer product D- = v-h-T.
After all this we will get W.,.,k matrix which is Nh x Nv corresponding to k-th slice of 3D Tensor.
(delta)Wg = D+ - D-.
Therefore, W.,.,knew = W.,.,kold + n*(delta)W.,.,k , where n is the learning rate.
Another method of updating the parameters is through discriminative update rule: ML learning of P(l|v)
1) Compute logP(lc = 1|v+).
2) Hybrid Learning Rule is given by
The two main advantages of learning as explained above are:
1) It avoids slow mixing of the CD learning P(v,l).
2) And it allows learning from both labelled as well as unlabelled data.
Putting it other way, we can say that it optimizes conditional distributions
in place of joint distribution, like optimizing pseudo-likelihood. For
improving discriminative performance, we are using binary features that are
only rarely active.Error measure is performed by comparing and cross checking
entropy between the desired and actual distributions. Evaluation and
Validation of the model:
The NORB Database consisted of five objects namely animals, humans,planes,
trucks, and cars. Normalized version of the data base has been used. Each
training example is a stereo pair of gray-scale images, size: 96x96.Based on
the above explained algorithm different models are built like shallow models
and deep models.It is obvious that deep model must perform better than
shallow model. Introducing even one pre-trained layer, trained greedily,
decreased the error rate a lot as compared to shallow model. It has been
observed that third order RBM outperformed standard RBM top level model
having same number of hidden units. Comparing "hybrid learning rule" and "CD"
learning rule for the top level RBN, there is not much difference cited
between the two error rates, however, hybrid is better.
Conclusion:
The two main points to conclude are:
1) Using generative model in object recognition gives a lot better result
because it produces a representation of the input image which gives more
acurate result as compared to raw pixels.
2) Including P(v|l) in the learning rule along with P(l|v) from trainig the
top level model improved the performace of the classification task.
References:
[1] Wikipedia
[2] www.deeplearning.net
[3] http://www.robots.ox.ac.uk/~ojw/files/NotesOnCD.pdf
[4] Images are taken from the review paper itself.
---
We introduce a new type of top-level model for Deep Belief Nets and evaluate
it on a 3D object recognition task. The top-level model is a third-order
Boltzmann machine, trained using a hybrid algorithm that combines both
generative and discriminative gradients. Performance is evaluated on the
NORB database (normalized-uniform version), which contains stereo-pair
images of objects under different lighting conditions and viewpoints. Our
model achieves 6.5% error on the test set, which is close to the best published
result for NORB (5.9%) using a convolutional neural net that has
built-in knowledge of translation invariance. It substantially outperforms
shallow models such as SVMs (11.6%). DBNs are especially suited for
semi-supervised learning, and to demonstrate this we consider a modified
version of the NORB recognition task in which additional unlabeled images
are created by applying small translations to the images in the database.
With the extra unlabeled data (and the same amount of labeled data as
before), our model achieves 5.2% error.
[pdf]
}}
@article{yangJ-huangT-10eccv_efficient-sparse-coding-mixture-model,
title={Efficient highly over-complete sparse coding using a mixture model}, [pdf]
}}
@InProceedings{tangY-salakhutdinov-hinton-12icml_deep-mixtures-factor-analysers,
author = {Yichuan Tang and Ruslan Salakhutdinov and Geoffrey Hinton},
title = {Deep Mixtures of Factor Analysers}, [pdf]
}}
@InProceedings{varoquaux-gramfort-12icml_small-sample-fmri-spatial-clustering,
author = {Gael Varoquaux and Alexandre Gramfort and Bertrand Thirion},
title = {Small-sample brain mapping: sparse recovery on spatially correlated designs with randomization and clustering}, [pdf]
}}
@InProceedings{chen-carson-12icml_information-theoretic-linear-discriminant-analysis,
author = {Minhua Chen and William Carson and Miguel Rodrigues and Robert Calderbank and Lawrence Carin},
title = {Communications Inspired Linear Discriminant Analysis}, [pdf]
}}
@InProceedings{boots-gordon-12icml_two-manifold-merging-from-separate-views,
author = {Byron Boots and Geoff Gordon},
title = {Two-Manifold Problems with Applications to Nonlinear System Identification}, [pdf]
}}
SUPERVISED ACTION / SEQUENCE CLASSIFICATION
@inproceedings{kaiser-12_learning-game-rules-from-videos,
title={Learning Games from Videos Guided by Descriptive Complexity}, [pdf]
}}
@inproceedings{blasiak-rangwala-11ijc_hmm-variant-for-sequence-classifiction,
title={A hidden markov model variant for sequence classification}, [pdf]
}}
@inproceedings{kerr-11_activity-recognition-w-FSM,
title={Activity recognition with finite state machines}, [pdf]
}}
@inproceedings{albanese-subrahmanian=11ijcai_finding-unexplained-activity-in-video,
title={Finding unexplained activities in video}, | ∈ E}, i.e., sigm(∈ E)ρ() = 1;
* {v ∈ V | there doesn’t exist v’ ∈ V s.t. ∈ E} = ∅, i.e., there
exists at least one start node in the activity definition
Unexplained Activity Probability Model
We start by noting that the definition of probability of an activity occurring in a video can implicitly involve
conflicts.
Possible world A possible world is a set of activity occurrences which do not conflict with one another,
i.e., an action symbol in a frame cannot belong to two distinct activity occurrences in the same world.
!~* To denote the transitive closure of !~(conflict).!~* is an equivalence relation and determines a partition
of O into equivalence classes O1, . . ., Om.
A Conflict-Based Partitioning (CBP) of v (w.r.t. l) is a sequence <(v1,l1), . . . , (vm, lm)> such that:
• v1 …. vm = v;
• li is the restriction of l to vi, i.e., it is a labeling of vi s.t ∀f ∈ vi, _i(f) = _(f), for 1 ≤ i ≤ m; and
• O(vi, li) = Oi, for 1 ≤ i ≤ m.
Totally unexplained activities theorem : Let be a UAP instance. Given (f, s) s.t. f ∈ v and
s ∈ _(f), let ε = sigma(o∈O s.t. (f,s)∈o) p∗(o) *Weight(o)/sigma(oj∈C(o)) Weight(oj). Ifε > 1−τ, then there
does not exist a sequence S occurring in v s.t. (f, s) ∈ S and PT (S) ≥ τ .
Partially unexplained activities theorem: Let<(v1, l1), . . . , (vm, lm)> be a CBP and
be the sub-videos containing a sequence S occurring in v. Let v∗ = vi ・ . . . ・ vi+n and _∗ be a labeling for
v∗ s.t., for every f ∈ v∗, l∗(f) = l(f). IP (S) computed w.r.t. v and l is equal to IP (S) computed w.r.t. v∗ and l∗.
Algorithms are developed for finding the unexplained activities using the above theorems.
---
Consider a video surveillance application that monitors some location. The
application knows a set of activity models (that are either normal or
abnormal or both), but in addition, the application wants to find video
segments that are unexplained by any of the known activity models — these
unexplained video segments may correspond to activities for which no previous
activity model existed. In this paper, we formally define what it means for a
given video segment to be unexplained (totally or partially) w.r.t. a given
set of activity models and a probability threshold. We develop two algorithms
– FindTUA and FindPUA – to identify Totally and Partially Unexplained
Activities respectively, and show that both algorithms use important pruning
methods. We report on experiments with a prototype implementation showing
that the algorithms both run efficiently and are accurate.
[pdf]
}}
@inproceedings{abolhassani-clark-11ijc_gaze-based-task-classification-w-HMMs,
title={Visual task inference using hidden markov models}, , where y∈Y is a task label (e.g.,
reading, counting etc.) and Q is the vector containing the observation
sequence of fixation locations (q1,q2, ..., qT) sampled from a stochastic
process(not deterministic) {qt} in discrete time t ={1,2, ..., T} over random
image locations; hence discrete-state-space S=[s1,s2, ..., sN],so that
qi =sj|i∈[1,T],j∈[1,N]
We can then find the probability of task y for a given input sequence Q using
Bayes’ s Rule
To to get the likelihood term, we propose two models here. They are:
* Bottom-Up Models
* Top-Down Models
Bottom-Up Models:
This is task-independent. It is based only on the input image. i.e in this
model we assume that the observation qi are conditionally independent. So our
equation (2) reduces as follows.
P(Q|y)= P(Q) = P(q1,q2,...,qT) = P(q1).P(q2)...P(qT)
This is called Naïve Bayes Assumption.
In this model, location with highest salience is taken as the current Focus
Of Attention(FOA).
But this gives very poor results.
--Top Down Models--
So from above observation we came to know that attention is not just
saliency-dependent, rather it depends mainly on the ongoing task and saliency
of the targets.
This is task dependent method.
So Likelihood term from equation(2) can be modified as:
P(Q|y) = P(q1,q2,...,qT|y) = P(q1|y)P(q2|y)...P(qT|y)
Even here we can observe that we are still assuming Naïve Bayes Assumption
and observations are conditionally independent. So there are still some
problems with Top-Down Model.
--Hidden Markov Model--
So to allow dependencies between the attributes q1,q2,q3,……,qT we propose
first-order, discrete-time, discrete-state-space Markov chains to model the
attention. According to this model, the
Likelihood term from equation(2) now becomes as follows:
P(Q|y) = P(q1,q2,...,qT) = P(q1|y)P(q2|q1,y)...P(qT|qT−1,y)
So this allows dependencies between consecutive fixations and make inferences
about the task.
By plugging in this likelihood term in equation(1) we can infer the task.
However, in real life, human attention generally deviates from the locus of
fixation and also due to the factors like equipment bias etc, it leads to
covert attention and so makes FOA covert and so hard to track. To solve this
Hidden Markov Models (HMMs).
--HMMs: (To deal with Covert Attention)--
A typical discrete-time, continuous HMM λ can be defined by a set of parameters λ = (A,B,Π)
where A is the state transition probabilities, B is the Observation pdf and Π is initial state distribution.
HMMs mainly deal with 3 problems: evaluation, decoding and training. They can be solved using
forward, Viterbi and Baum-Welch algorithms respectively. Evaluation gives probability of observing the
sequence given the HMM, i.e.,P(O|λ) where O represents the sequence of observations.
In our model, covert attention is represented by the hidden states of a
task-dependent HMM λy(where λy is equivalent to y. i.e both of them represent
a specific task). Fixation locations, thus, will correspond to the
observations of an HMM and can be used in training task-dependent models and
evaluating the probability P(O|λy). And finally O corresponds to Q in our
equation (1). So (1) is modified...
So, after training the task-dependent HMM λy for each task, we can calculate
the likelihood term P(O|λy) by applying the parameters of λy to the forward
algorithm.
So in this way, we can make inferences about the task when we are given an
eye-trajectory as input by plugging in the Likelihood term in the final
equation shown and the task y that has maximum P(λy|O) value is regarded as
the required task that should be given as output.
---
It has been known for a long time that visual task, such as reading, counting
and searching, greatly influences eye movement patterns. Perhaps the best
known demonstration of this is the celebrated study of Yarbus showing that
different eye movement trajectories emerge depending on the visual task that
the viewers are given. The objective of this paper is to develop an inverse
Yarbus process whereby we can infer the visual task by observing the
measurements of a viewer’s eye movements while executing the visual task. The
method we are proposing is to use Hidden Markov Models (HMMs) to create a
probabilistic framework to infer the viewer’s task from eye movements.
[pdf]
}}
@article{taylor-hinton-roweis-11_distributed-models-high-dim-time-series,
title={Two Distributed-State Models For Generating High-Dimensional Time Series},
author={Taylor, G.W. and Hinton, G.E. and Roweis, S.T.},
journal={Journal of Machine Learning Research},
volume={12},
pages={1025--1068},
year={2011}
annote = {
[models activity as low-dimensional models; can actually generate animations]
ABSTRACT:
In this paper we develop a class of nonlinear generative models for
high-dimensional time series. We first propose a model based on the
restricted Boltzmann machine (RBM) that uses an undirected model with binary
latent variables and real-valued "visible" variables. The latent and visible
variables at each time step receive directed connections from the visible
variables at the last few time-steps. This "conditional" RBM (CRBM) makes
on-line inference efficient and allows us to use a simple approximate learning
procedure. We demonstrate the power of our approach by synthesizing various
sequences from a model trained on motion capture data and by performing
on-line filling in of data lost during capture. We extend the CRBM in a way
that preserves its most important computational properties and introduces
multiplicative three-way interactions that allow the effective interaction
weight between two variables to be modulated by the dynamic state of a third
variable. We introduce a factoring of the implied three-way weight tensor to
permit a more compact parameterization. The resulting model can capture
diverse styles of motion with a single set of parameters, and the three-way
interactions greatly improve its ability to blend motion styles or to
transition smoothly among them. Videos and source code can be found at
http://www.cs.nyu.edu/Ëœgwtaylor/publications/jmlr2011
[pdf]
}}
@inproceedings{leQ-zou-ngA-11_learning-hierarchical-temporal-action-recognition,
title={Learning hierarchical invariant spatio-temporal features for action recognition with independent subspace analysis}, [pdf]
}}
@article{luiYM-12_matrix-manifolds-for-computer-vision,
title={Advances in matrix manifolds for computer vision}, [pdf]
}}
@InProceedings{jawanpuria-nath-12icml_convex-feature-learning-for-latent-task-structure,
author = {Pratik Jawanpuria and J. Saketha Nath},
title = {A Convex Feature Learning Formulation for Latent Task Structure Discovery},
booktitle = {Proceedings of the 29th International Conference on Machine Learning (ICML-12)},
series = {ICML '12},
year = {2012},
editor = {John Langford and Joelle Pineau},
location = {Edinburgh, Scotland, GB},
isbn = {978-1-4503-1285-1},
month = {July},
publisher = {Omnipress},
address = {New York, NY, USA},
pages= {137--144},
Abstract: This paper considers the multi-task learning problem and in the
setting where some relevant features could be shared across few related
tasks. Most of the existing methods assume the extent to which the given
tasks are related or share a common feature space to be known apriori. In
real-world applications however, it is desirable to automatically discover
the groups of related tasks that share a feature space. In this paper we aim
at searching the exponentially large space of all possible groups of tasks
that may share a feature space. The main contribution is a convex formulation
that employs a graph-based regularizer and simultaneously discovers few
groups of related tasks, having close-by task parameters, as well as the
feature space shared within each group. The regularizer encodes an important
structure among the groups of tasks leading to an efficient algorithm for
solving it: if there is no feature space under which a group of tasks has
close-by task parameters, then there does not exist such a feature space for
any of its supersets. An efficient active set algorithm that exploits this
simplification and performs a clever search in the exponentially large space
is presented. The algorithm is guaranteed to solve the proposed formulation
(within some precision) in a time polynomial in the number of groups of
related tasks discovered. Empirical results on benchmark datasets show that
the proposed formulation achieves good generalization and outperforms
state-of-the-art multi-task learning algorithms in some cases.
video: http://icml.cc/discuss/2012/90.html
pratik.j, saketh@cse.iitb.ac.in
[pdf]
}}
SUPERVISED LEARNING
@InProceedings{takeda-mitsugi-kanamori-12_unified-robust-classification,
author = {Akiko Takeda and Hiroyuki Mitsugi and Takafumi Kanamori},
title = {A Unified Robust Classification Model}, [pdf]
}}
@inproceedings{maX-luoP-11ijc_combining-supervised-unsupervised-via-embedding,
title={Combining supervised and unsupervised models via unconstrained probabilistic embedding}, [pdf]
}}
@article{agarwal-daume-11ijc_geometric-view-of-conjugate-priors,
title={A geometric view of conjugate priors}, [pdf]
}}
@inproceedings{xiaoY-liuB-11ijc_similarity-based-positive-and-unlabeled-learning,
title={Similarity-based approach for positive and unlabelled learning}, [pdf]
}}
@inproceedings{liYF-HuJH-12aaai_what-patterns-trigger-what-labels,
title={Towards Discovering What Patterns Trigger What Labels},
author={Yu-Feng Li and Ju-Hua Hu and Yuan Jiang and Zhi-Hua Zhou},
booktitle={Twenty-Sixth AAAI Conference on Artificial Intelligence},
year={2012},
pages = {1012-1018},
annote = {
multiple labels are associated with each object, with many overlaps.
perhaps a label relates to some subset of features in each object.
how does one create models of categories from this?
formulate the problem as a convex optimization problem.
abstract:
In many real applications, especially those involving data objects with
complicated semantics, it is generally desirable to discover the relation
between patterns in the input space and labels corresponding to different
semantics in the output space. This task becomes feasible with MIML
(Multi-Instance Multi-Label learning), a recently developed learning
framework, where each data object is represented by multiple instances and is
allowed to be associated with multiple labels simultaneously. In this paper,
we propose KISAR, an MIML algorithm that is able to discover what instances
trigger what labels. By considering the fact that highly relevant labels
usually share some patterns, we develop a convex optimization formulation and
provide an alternating optimization solution. Experiments show that KISAR is
able to discover reasonable relations between input patterns and output
labels, and achieves performances that are highly competitive with many
state-of-the-art MIML algorithms.
[pdf]
}}
LANGUAGE / NLP
@article{collobert-weston-11_nlp-from-scratch,
title={Natural language processing (almost) from scratch}, [pdf]
}}
@article{chen-mooney-11_interpret-NLP-navigation-instructions-from-observations,
title={Learning to interpret natural language navigation instructions from observations}, [pdf]
}}
MACHINE LEARNING in NLP
@inproceedings{naradowsky-goldwater-09_improving-morphology-induction-via-spelling,
title={Improving morphology induction by learning spelling rules}, [pdf]
}}
@article{bod-smets-12_empiricist-approach-to-nativism-via-unsupervised-TSG,
title={Empiricist solutions to nativist puzzles by means of unsupervised TSG},
b.) *the vampire who I read a book which was about is dangerous--`the
vampire' is moved‟ out of the complex NP `a book which was about ‟, which is not allowed.
(a.) [the vampire X is dangerous] o [who I read X] o [a book about] ranking:
1,714,906
(b.) [the vampire X is dangerous] o [who I read X] o [a book which X] o [was
about] ranking: 1,906,597
The problem of Extraposition from NP
Example:
(a.) that Jacob picked Bella up who loves Edward is possible
(b.) *that Jacob picked Bella up is possible who loves Edward
(a‟) [X is possible] o [that Jacob picked X] o[Bella up X] o [who loves Edward] ranking: 1,080,535
(b‟) [X is possible X] o [that Jacob picked X] o[Bella up] o [who loves Edward] ranking: 1,111,155
The problem of Topicalization: Example, the topicalization in (a) is fine but in (b) it is not.
(a) Stephenie's book I read [X I read] o [Stephenie‟s book] ranking: 608 + 2,784 = 3,392
(b) *Stephenie's I read book [Stephenie‟s X book] o [I read] ranking: 3,139 +
488 = 3,627
The problem of Left dislocation: The phenomenon of Left dislocation provides a particular challenge to nativist approaches
since it shows that there are grammatical sentences that do not obey the Coordinate Structure Constraint (Adger 2003;
Borsley 2004).
In Left dislocation the moved constituent must be moved to the left of the main clause. Instead, movement merely to the left
of a subordinate clause results in an ungrammatical sentence.(Ross 1967)
Example:
(a) Edward, that you love him is obvious -- grammatical, `Edward' is moved to the left of the main clause.
(b) *that Edward, you love him is obvious--ungrammatical, `Edward' is only moved to the left of the subordinate
clause `that you love '.
TSG has no problem in distinguishing between these two alternatives, as is shown below
(a‟) [Edward X is obvious] o [that you love him] ranking: 590,659 + 57,785 = 648,444
(b‟) [that X is obvious] o [Edward you love him] ranking: 876,625 + 415,940 = 1,292,565
Conclusion:
Unsupervised TSG can capture virtually all phenomena related to wh-questions
in a simple and uniform way . The questionfrom where the preferences may
eventually come? should be answered within the field of language evolution.
The model only ranks alternative sentences (for a certain phenomenon)
,ideally rather than selecting from given sentences, we would like to have a
model that starts with a certain meaning representation for which next the
best sentence is generated. In the absence of such a semantic component, the
model selects directly from the set of possible sentences as they are
provided in the literature as alternatives.
Furthermore, this model can be extended to cover other phenomena that fall
out of the scope of the traditional nativist account . Thus it is an
alternative approach that can model all the hard phenomena on the basis of
just one principle (the best-ranked derivation), for at least these
phenomena, Arguments from Poverty of Stimulus can no longer be invoked.
Hence argument (of the Poverty of the Stimulus) is refuted by this model.
Acknowledgement:
http://www-personal.umich.edu/~jlawler/aue/ross.html
http://www.ego4u.com/en/cram-up/grammar/relative-clauses
http://en.wikipedia.org/wiki/Topicalization
http://en.wikipedia.org/wiki/Extraposition
http://en.wikipedia.org/wiki/Dislocation_(syntax)
---
abstract:
While the debate between nativism and empiricism exists since several
decades, surprisingly few common learning problems have been proposed for
assessing the two opposing views. Most empiricist researchers have focused on
a relatively small number of linguistic problems, such as Auxiliary Fronting
or Anaphoric One. In the current paper we extend the number of common test
cases to a much larger series of problems related to wh-questions, relative
clause formation, topicalization, extraposition from NP and left
dislocation. We show that these hard cases can be empirically solved by an
unsupervised tree-substitution grammar inferred from child-directed input in
the Adam corpus (Childes database).
[pdf]
}}
@InProceedings{matuszek-fitzgerald-zettlemoyer-12icml_joint-language-and-perception-learning,
author = {Cynthia Matuszek and Nicholas FitzGerald and Luke Zettlemoyer and Liefeng Bo and Dieter Fox},
title = {A Joint Model of Language and Perception for Grounded Attribute Learning}, [pdf]
}}
@inproceedings{deCruys-korhonen-12coling_tensor-factorization-for-unsup-lexical-acquisition,
title = {Multi-way Tensor Factorization for Unsupervised Lexical [pdf]
}}
@inproceedings{wu-kashioka-12coling_factored-language-model-from-recurrent-NN,
title = {Factored Language Model based on Recurrent Neural Network}, [pdf]
}}
@inproceedings{socher-linCC-NgA-11_parsing-natural-scenes-w-RNNs,
title={Parsing natural scenes and natural language with recursive neural networks}, [pdf]
}}
@inproceedings{wang-mahadevan-11ijc_heterogeneous-domain-manifold-alignment,
title={Heterogeneous domain adaptation using manifold alignment}, [pdf]
}}
LANGUAGE GENERATION
@inproceedings{ontanon-zhu-11ijc_domain-knowlwedge-story-generation,
title={On the role of domain knowledge in analogy-based story generation}, [pdf]
}}
@article{wang-li-ogihara-12_generating-storylines-picture-text,
title={Generating Pictorial Storylines via Minimum-Weight Connected Dominating Set Approximation in Multi-View Graphs}, [pdf]
}}
GRAMMAR EVOLUTION
@inproceedings{beuls-hofer-11ijc_emergence-of-grammatical-agreement-in-language-games,
title={Simulating the emergence of grammatical agreement in multi-agent language games}, [pdf]
}}
IMAGE / VIDEO DESCRIPTION
@article{barbu-siskind-12_video-in-sentences-out,
title={Video In Sentences Out}, [pdf]
}}
@inproceedings{bergsma-vanDurme-11ijc_learning-bilingual-lexicons-using-image-similarity,
title={Learning bilingual lexicons using the visual similarity of labeled web images}, [pdf]
}}
@inproceedings{narayanaswamy-siskind-11_visual-language-for-estimating-object-pose,
title={A visual language model for estimating object pose and structure in a generative visual domain}, [pdf]
}}
@inproceedings{luW-zettlemoyer-08_generative-parsing-NL-to-meaning,
title={A generative model for parsing natural language to meaning representations}, [pdf]
}}
TEXT / DOCUMENT DATA MINING
@shahaf-guestrin-10_connecting-dots-between-news
shahaf-guestrin-11ijc_connecting-between-news articles,
title={Connecting the dots between news articles},
2013 review ankit modi ~amodi/cs365/hw2/Research_Paper_Summary.pdf
This paper aims at fighting information overload by providing a structured,
easy way to navigate between topics. Given two news articles, the explained
system automatically finds a coherent chain linking them together. Concepts
of Coherence and Influence were used to do so. Coherence is a measure of
activation patterns of a word while Influence measures the role of a word in
connecting two articles.
Given a set of chronologically ordered articles/documents d1, d2,…, dn and a
set of words w1, w2,…, wn.
Coherence (d1…dn) = min i=1…n-1 Σw Influence (di,di+1 | w)
Firstly, a bipartite directed graph, G = (V,E) is constructed. The vertices V
= VD ∪ VW correspond to documents and words. For every word w in document d,
both edges (w, d) and (d,w) are added. Edge weights(TF IDF weights may be
used) represent strength of correlation between a word and a document. This
graph was used to define Influence. Variable node-activew,i indicatess the
activation level of w during transition from di to di+1. Variable
words-initw,i indicates the initialisation level of w during transition from
di to d_i+1.
A linear programming model was used to attain the objective. LP had 4 modules
as follows :
1. Chain restriction : It ensures a proper chain i.e. it starts with source s, ends
with target t, has k nodes and k-1 edges.
node-active1 = 1, node-activen = 1
Σi node-activei = k
Σi,j next-nodei,j = k-1
Σi next-nodei,j = node-activej
; j ≠ s
Σj next-nodei,j = node-activei
; i ≠ t
∀i>=j next-nodei,j = 0 (ensuring chain’s chronological order)
∀i
@inproceedings {chambers-jurafsky-11_template-script-extraction-from-text,
title = {Template-based information extraction without the templates}, [pdf]
}}
@InProceedings{mnih-tehYW-12icml_neural-probabilistic-language-models,
author = {Andriy Mnih and Yee Whye Teh},
title = {A fast and simple algorithm for training neural probabilistic language models}, [pdf]
}}
@inproceedings{teh-06_hierarchical-bayesian-language-model,
title={A hierarchical Bayesian language model based on Pitman-Yor processes},
author={Teh, Yee Whye},
booktitle={Proceedings of the 21st International Conference on Computational Linguistics and the 44th annual meeting of the Association for Computational Linguistics},
pages={985--992},
year={2006},
annote =
}}
@inproceedings{shahaf-guestrin-11ijc_connecting-between-news articles,
title={Connecting the dots between news articles}, [pdf]
}}
@InProceedings{pachauri-collins-singh-12icml_matching-using-domain-knowledge,
author = {Deepti Pachauri and Maxwell Collins and Vikas Singh and Risi Kondor},
title = {Incorporating Domain Knowledge in Matching Problems via Harmonic Analysis},
booktitle = {Proceedings of the 29th International Conference on Machine Learning (ICML-12)},
series = {ICML '12},
year = {2012},
editor = {John Langford and Joelle Pineau},
location = {Edinburgh, Scotland, GB},
isbn = {978-1-4503-1285-1},
month = {July},
publisher = {Omnipress},
address = {New York, NY, USA},
pages= {1271--1278},
annote = {
--review 2013 Amit Kumar ~akkumar/cs365/hw2/report.pdf
Matching two objects in machine learning is a tough task. This can be solved
by reducing it to some form of QAP.[2] The quadratic assignment problem (QAP)
is a combinatorial optimization problems. [1] The QAP is very hard to
solve. It is a problem of matching two weighted graphs G and G' with
adjacency matrices A and A', to maximize the overlap between them.
Summary
In this paper author gives an algorithm to solve Matching problem by solving
QAP problem based on the learning a modified objective function f from a set
of prior “training” QAP instances. At test time, only a sample set (training
set) X is known, and a prediction function f : X → Y maps it to a predicted
label from the label space.[3] There is one property of this function, the
inverse map of f can be expressed, which makes this f learnable.[2] This
function is expressed as the graph correlation between the two graphs G and
G'.[2] We can use features such as Euclidean distance between interested
points,
Shape context features etc for establishing relationship between the vertices
of G.[2] They transformed the learning problem using ideas from the theory of
non-commutative Fourier analysis on the symmetric group. [2]
Contributions
The contribution of this paper is the parameter learning framework for a
class of combinatorial problems where the solution is a candidate in the
symmetric group Sn . We show how the representation theory of Sn makes the
procedure computationally tractable, and how Branch and Bound schemes can be
modified to learn information relevant for problem instances coming from an
application of interest.[2]
Uses
In computer vision this can be helpful in finding the correspondence between
multiple images of the same scene taken from different viewpoint.[2] This can
be useful for matching a face from the set of samples of faces. This can also
be useful for identifying object.
In machine learning, In aligning examples before a meaningful similarity
measure can be computed between them.
REFERENCES
1. wikipedia page of quadratic assignment problem:
http://en.wikipedia.org/wiki/Quadratic_assignment_problem
2. pachauri-collins-singh-12icml_matching-using-domain-knowledge
3. wikipedia page of Structured SVM
http://en.wikipedia.org/wiki/Structured_SVM
Abstract: Matching one set of objects to another is a ubiquitous task in
machine learning and computer vision that often reduces to some form of the
quadratic assignment problem (QAP). The QAP is known to be notoriously hard,
both in theory and in practice. Here, we investigate if this difficulty can
be mitigated when some additional piece of information is available: (a) that
all QAP instances of interest come from the same application, and (b) the
correct solution for a set of such QAP instances is given. We propose a new
approach to accelerating the solution of QAPs based on learning parameters
for a modified objective function from prior QAP instances. A key feature of
our approach is that it takes advantage of the algebraic structure of
permutations, in conjunction with special methods for optimizing functions
over the symmetric group \m{\Sb_n} in Fourier space. Experiments show that in
practical domains the new method can significantly outperform existing
approaches.
pachauri,mcollins@cs.wisc.edu risi@uchicago.edu vsingh@biostat.wisc.edu
discussion+video on ICML pages
[pdf]
}}
@inproceedings{caragea-silvescu-mitra-12_hashing-and-abstraction-sparse-high-D-features,
title={Combining Hashing and Abstraction in Sparse High Dimensional Feature Spaces}, [pdf]
}}
@inproceedings{fangJ-mitra-12aaai_table-header-detection-document,
title={Table Header Detection and Classification}, [pdf]
}}
@inproceedings{heZ-chenC-heX-12_document-summarization-based-on-reconstruction,
title={Document Summarization Based on Data Reconstruction}, [pdf]
}}
@inproceedings{zhangR-gao-12_generating-coherent-summaries-w-text-aspects,
title={Generating Coherent Summaries with Textual Aspects}, [pdf]
++++
}}
@article{chuang-11_text-patterns-semantic-class-learning,
title={Text Patterns and Compression Models for Semantic Class Learning}, [pdf]
}}
@inproceedings{nori-bollegala-12_multinomial-relations-social-data,
title={Multinomial Relation Prediction in Social Data: A Dimension Reduction Approach},
author={Nozomi Nori and Danushka Bollegala and Hisashi Kashima},
booktitle={Twenty-Sixth AAAI Conference on Artificial Intelligence},
year={2012}
pages= {115-121},
annote = {
####
--- review 2013 Pulkit Jain (10543) ~pulkitj/cs365/hw2/HW2.pdf
--Problem Addressed--
The explosion of internet in the recent days has led to emergence of social
data. Web services that produce/operate with this data involve social actions
such as tagging, annotating and other actions which involve heterogeneous and
multiple objects. User actions are modeled as relations. Prediction of these
actions is important for many fundamental services such as search engines and
recommendation systems. The work done addresses the action prediction problem
using dimensionality reduction approach.
--Proposed Solution--
The solution proposed is based upon reduction of a relation instance into
multiple binomial instances and using attribute information of involved
objects.
* Nonlinear dimensionality reduction is applied to binomial relations which
embeds objects and relations into a common subspace where each object is
close to the relation it participates in.
* Minimizing distances (Euclidian distance metric used) between the
embedding of objects and relations results in solving an optimization
problem which is formulated as a generalized eigenvalue problem. This
gives us exact solutions that are globally optimal and are robust to the
sparse data.
* Incorporating the attribute information in the solution only requires
replacing the low dimensional embedding used previously by linear
projections of the attribute information to obtain embedding in the
required subspace. This addresses the “cold start” problem where the
sparsity of data is high.
Thus the input to the process/algorithm followed includes sets of objects
that can participate in relations, and a set of observed relation
instances. The output obtained is a list of other possible relations amongst
the objects sorted in order of likelihood of the relation.
Input: S1, S2…SK - Set of Objects
O (⊂ S1 X S2 X…..X SK) - Set of Observed Relation Instances
Φ1, Φ2... ΦK - K matrices representing object attributes
Output: S1 X S2 X…..X SK \ O - Possible relations sorted in order of likelihood
--Results/Contributions--
* Datasets from Twitter for prediction of “favorite” and “retweet” actions
and del.icio.us (a social tagging service) were used for measuring the
performance.
* The data was also tested against the existing PARAFAC and TUCKER tensor
decomposition methods along with the proposed solutions to build
comparisons.
* The proposed solution showed highest robustness when the data was sparse
in terms of the relation instances.
* The solution did not perform well when tested against data that was sparse
in relations that involved particular objects, but the performance was
high when attribute information of objects was used along with the
relation information.
* Overall, the proposed solution is highly robust to data sparsity in
comparison to the existing methods of prediction using tensor
decompositions.
REFERENCES
[1] Nozomi Nori;Danushka Bollegala; Hisashi Kashima 2012. Multinomial Relation Prediction in Social Data.
A Dimension Reduction Approach. In Proceedings of the Twenty-Sixth AAAI Conference on Artificial
Intelligence.
[2] Lin, Y.-R.; Sun, J.; Castro, P.; Konuru, R.; Sundaram, H.;and Kelliher, A. 2009. Metafac: community
discovery via relational hypergraph factorization. In Proceedings of the 15th ACM SIGKDD International
Conference on Knowledge Discovery and Data Mining.
[3] CP Decomposition, Wikipedia. http://en.wikipedia.org/wiki/CP_decomposition
[4]Tucker Decomposition,
Wikipedia. http://en.wikipedia.org/wiki/Tucker_decomposition
---
abstract:
The recent popularization of social web services has made them one of the
primary uses of the World Wide Web. An important concept in social web
services is social actions such as making connections and communicating with
others and adding annotations to web resources. Predicting social actions
would improve many fundamental web applications, such as recommendations and
web searches.
One remarkable characteristic of social actions is that they involve multiple
and heterogeneous objects such as users, documents, keywords, and
locations. However, the high-dimensional property of such multinomial
relations poses one fundamental challenge, that is, predicting multinomial
relations with only a limited amount of data.
In this paper, we propose a new multinomial relation prediction method, which
is robust to data sparsity. We transform each instance of a multinomial
relation into a set of binomial relations between the objects and the
multinomial relation of the involved objects. We then apply an extension of a
low-dimensional embedding technique to these binomial relations, which
results in a generalized eigenvalue problem guaranteeing global optimal
solutions. We also incorporate attribute information as side information to
address the “cold start” problem in multinomial relation prediction.
Experiments with various real-world social web service datasets demonstrate
that the proposed method is more robust against data sparseness as compared
to several existing methods, which can only find sub-optimal solutions.
}}
@inproceedings{heZ-chenC-heX-12_document-summarization-based-on-reconstruction,
title={Document Summarization Based on Data Reconstruction},
author={Zhanying He and Chun Chen and Jiajun Bu and Can Wang and Lijun Zhang and Deng Cai and Xiaofei He},
booktitle={Twenty-Sixth AAAI Conference on Artificial Intelligence},
year={2012},
annote= {
Outstanding Paper Award
ROUGE score - measures effectiveness.
interesting multi-technique comparison fig.1
---
search engines can provide users with snippets as the previews of
the document contents (Turpin et al. 2007; Huang, Liu, and
Chen 2008; Cai et al. 2004; He et al. 2007). News sites usually describe hot news topics in concise headlines to facilitate browsing. Both the snippets and headlines are specific
forms of document summary in practical applications.
Most of the existing generic summarization approaches use a ranking model to
select sentences from a candidate set (Brin and Page 1998; Kleinberg 1999;
Wan and Yang 2007). These methods suffer from a severe problem that top
ranked sentences usually share much redundant information. Although there are
some methods (Conroy and O’leary 2001; Park et al. 2007; Shen et al. 2007)
trying to reduce the redundancy, selecting sentences which have both good
coverage and minimum redundancy is a non-trivial task.
Previous studies have shown that there is psychological and physiological evidence for parts-based representation in the human brain (Palmer 1977; Wachsmuth, Oram,
and Perrett 1994; Cai et al. 2011). Naturally, a document
summary should consist of the parts of sentences. With the
nonnegative constraints, our method leads to parts-based reconstruction so that no redundant information needs to be
subtracted from the combination.
Extensive experiments on summarization benchmark data sets DUC 2006 and DUC
2007 demonstrate the effectiveness of our proposed approach.
--Document Summarization based on Data Reconstruction (DSDR)--
minimizes the reconstruction error
for summarization. The algorithm procedure of DSDR is as
follows:
- After stemming and stop-word elimination, we decompose the document into
individual sentences and create a weighted term-frequency vector for
every sentence. All the sentences form the candidate set.
- For any sentence in the document, DSDR selects the related sentences from
the candidate set to reconstruct the given sentence by learning a
reconstruction function for the sentence.
- For the entire document (or, a set of documents), DSDR aims to find an
optimal set of representative sentences to approximate the entire
document (or, the set of documents), by minimizing the reconstruction
error.
--
ABSTRACT
Document summarization is of great value to many real world applications,
such as snippets generation for search results and news headlines
generation. Traditionally, document summarization is implemented by
extracting sentences that cover the main topics of a document with a minimum
redundancy. In this paper, we take a different perspective from data
reconstruction and propose a novel framework named Document Summarization
based on Data Reconstruction (DSDR). Specifically, our approach generates a
summary which consist of those sentences that can best reconstruct the
original document. To model the relationship among sentences, we introduce
two objective functions: (1) linear reconstruction, which approximates the
document by linear combinations of the selected sentences; (2) nonnegative
linear reconstruction, which allows only additive, not subtractive, linear
combinations. In this framework, the reconstruction error becomes a natural
criterion for measuring the quality of the summary. For each objective
function, we develop an efficient algorithm to solve the corresponding
optimization problem. Extensive experiments on summarization benchmark data
sets DUC 2006 and DUC 2007 demonstrate the effectiveness of our proposed
approach.
[pdf]
}}
@inproceedings{jans-bethard-12_skip-grams-for-predicting-scripts,
title={Skip n-grams and ranking functions for predicting script events},
author={Jans, B. and Bethard, S. and Vulic, I. and Moens, M.F.},
booktitle={Proceedings of the thirteenth conference of the European chapter of the association for computational linguistics (EACL 2012)},
year={2012}
annote = {
---2013 review chirag gupta ~gchirag/cs365/hw2/assignment2_10212.pdf
Improving the following:
* Identification of events from narrative script
* Gathering statistics from the event chains
* Choose ranking functions for predicting script events
Corpus Used: Reuters Corpus, Volume 1
Andrew Lang Fairy Tale Corpus
--Procedure--
Model takes as input a partial script and produces as output a ranked list of
events for that script.
I. They filtered out the non-narrative articles out of the corpuses.
II. Identifying event chains from the script
As in the previous works of Chambers and Jurafsky in 2008 and 2009, and
in Mcintyre and Lapata in 2009 and 2010, the following are used:
Stanford Parser for identifying the dependency structure.
OpenNLP coreference engine for identifying entities in each article.
Finally event chains were constructed using all noun phrases associated
with that entity and any subject/object dependencies with a verb were
retrieved.
Either all, long or the longest event chains can be used for training a model.
III. Gathering event chain statistics
Regular bigrams, 1-skip bigrams and 2-skip bigrams are three strategies for
collecting bigrams. On these bigrams event pair counts and various
conditional probability calculations are done to gather statistics.
IV. Ranking methods used
Pointwise Mutual Information (PMI) used by Chambers and Jurafsky
Ordered PMI
Bigram probabilities of language modelling
V. Evaluation Metrics
Given an event chain of n events, n cloze tests are run, each time removing
one of the n events to form a partial script.
Given a partial script as input, accurate event prediction will be one that
ranks the missing event highly in its output guess list.
Average rank and Recall@N are two such metrics. Better results are with
lower average ranks and higher Recall@N values. N=50 is used in this
research.
--Results:--
On Reuters corpus: all chains, 2-skip bigrams and bigram probabilities gave the
best results.
On Fairy Tale corpus: long chains performed the best.
1-skip and 2-skip bigrams performed equally well.
Mixed results for bigram probabilities and PMI.
Main contributions:
* Used Skip-grams for the first time and showed that it is better than
n-grams approach used previously.
* Proposed bigram probabilities method for ranking events in a given partial
script.
* A new evaluation procedure Recall@N is also introduced.
References:
[1] Bram Jans, Steven Bethard, Ivan Vulić, and Marie-Francine Moens. Skip
N-grams and Ranking Functions for Predicting Script Events. In
Proceedings of the 13th Conference of the European Chapter of the
Association for Computational Linguistics, 2012.
[2] http://en.wikipedia.org/wiki/Dependency_grammar Dependency Parsing
[3] http://en.wikipedia.org/wiki/Coreference Coreference resolution
---
In this paper, we extend current state-of-theart research on unsupervised
acquisition of scripts, that is, stereotypical and frequently observed
sequences of events. We design, evaluate and compare different methods for
constructing models for script event prediction: given a partial chain of
events in a script, predict other events that are likely to belong to the
script. Our work aims to answer key questions about how best to (1) identify
representative event chains from a source text, (2) gather statistics from
the event chains, and (3) choose ranking functions for predicting new script
events. We make several contributions, introducing skip-grams for collecting
event statistics, designing improved methods for ranking event predictions,
defining a more reliable evaluation metric for measuring predictiveness, and
providing a systematic analysis of the various event prediction models.
[pdf]
see also [chambers-jurafsky-11_template-script-extraction-from-text.pdf]
}}
####
@InProceedings{prasse-sawade-12icml_identifying-regular-expressions-in-email-spam,
author = {Paul Prasse and Christoph Sawade and Niels Landwehr and Tobias Scheffer},
title = {Learning to Identify Regular Expressions that Describe Email Campaigns},
booktitle = {Proceedings of the 29th International Conference on Machine Learning (ICML-12)},
series = {ICML '12},
year = {2012},
editor = {John Langford and Joelle Pineau},
location = {Edinburgh, Scotland, GB},
isbn = {978-1-4503-1285-1},
month = {July},
publisher = {Omnipress},
address = {New York, NY, USA},
pages= {441--448},
---review 2013 Gurpreet Singh Khanuja(10277) ~gurpreet/cs365/hw2/hw2_10277.pdf
This paper actually address the problem of generating the regular
expressions from the given strings that matches the regular expression
that a person would have written to correctly identify the given
message. The motivation behind this was to automate the task of an
email service postmaster who make regular expressions to blacklist
email campaigns as writing the regular expression was very time
consuming process.
So here is the problem setting model:
First we search for a predictive model which maps the set of emails
which belong to some campaign x to some set of regular expression y.
The output of this predictive model would be as close as possible to the
regular expression what a human postmaster would have written to
identify the given email campaign.
fw : x → ŷ
To learn such a predictive model, the training data consist of campaign x
and regular expression y which was created by the postmaster.
Also the model should be with minimal risk R which minimizes the
expected loss.
R[fw] = ʃʃ Δ(y, fw(x), x) p(x, y) dxdy
The loss function Δ(y, fw(x), x) measures the syntactic and semantic
deviation between the two regular expressions, fw(x) and the one given by the
postmaster for the campaign x. This can be done by comparing the parse trees
of the two regular expressions.
[eqn]
To find the optimal regular expression, we would be computing
fw(x) = arg maxyϵƳ wT Ψ(x,y)
then we approximate this maximum by the maximum over a
constrained, finite search space to alleviate the intraceability of the
problem caused due to to infinite space of all regular expression.
[1]And this constrained search space initially contains an alignment of all
strings in x which is defined below.
DEFINITION 1(Alignment) – The set of alignments Ax of a batch of strings
x contains all concatenations in which strings from ∑+ and the wildcard
symbol “(.*)” alternate, and that generate all elements of x.
Thus after the further computations, the maximization over all y can be
decomposed into n maximization problems which can be solved in O(n
x |ƳD| ).
Then the algorithm is optimized by minimizing the regularised empirical
risk, for l2 regulariser Ω(w) = (1/2C)||w||2.
And they refer to this learning procedure as Rex-SVM.
References
[1] Prasse, Sawade, Landwher and Scheffer. “Learning to Identify
Regular Expressions that Describe Email Campaigns”.
Abstract: This paper addresses the problem of inferring a regular expression
from a given set of strings that resembles, as closely as possible, the
regular expression that a human expert would have written to identify the
language. This is motivated by our goal of automating the task of postmasters
of an email service who use regular expressions to describe and blacklist
email spam campaigns. Training data contains batches of messages and
corresponding regular expressions that an expert postmaster feels confident
to blacklist. We model this task as a learning problem with structured output
spaces and an appropriate loss function, derive a decoder and the resulting
optimization problem, and a report on a case study conducted with an email
service.
discussion+video on ICML pages
[pdf]
}}
ROBOTICS
@inproceedings{hart-scassellati-12aaai-mirror-perspective-w-humanoid-robot,
title={Mirror Perspective-Taking with a Humanoid Robot},
author={Hart, Justin W and Scassellati, Brian},
booktitle={Twenty-Sixth AAAI Conference on Artificial Intelligence},
year={2012}
annote = {
The robot goes upto a mirror and waves its hand - and is able to tell whether
it is itself or not.
---review by Valcarcel Xavier ~xavier/cs365/hw2.html
The “mirror test” was invented in 1970 by Gallup in order to measure the
self-consciousness of babies or animals. It consists of putting the
individual in front of a mirror, and if he recognizes the reflection as him
by looking to his body through the mirror, the test has succeeded. Only very
intelligent animals like chimpanzee dolphins or elephant or human older than
18 months are able to pass this test[1]. An alternative to this test is to
see if the individual can use the mirror as an instrument, some more species
are able to pass this test, but they are still rare.
The goal of this paper is to develop the perspective-taking model in order to
create in the future a system able to pass the “mirror test” .
If a robot can pass this test only with the observations that it does, it
could be a big step in the way how robots represents themselves in their own
environment, and use mirror for special reasoning.
--Architecture--
6 modules:
- End-Effector Model,
- Perceptual Model,
- Perspective-Taking Model,
- Structural Model,
- Appearance Model, and
- Functional Model
This paper develops the Perspective-Taking Model using the working
implementation of the 2 previous models. The goal of the Perspective-Taking
Model is to construct a 3D representation of the objects seen in the
reflection of the mirror, at their real place. In the experiment shown in
this paper, the robot will observe its end-effector through the mirror, and
then with the self-knowledge calculate the position of its end-effector.
To achieve that, the first thing is to determine the position and orientation
of the mirror plane. The robot will move its end-effector (in some position)
in front of the mirror without seen it directly, and will record some data
using the End-Effector Model and the Perceptual Model. The End-effector model
permits to compute the position of the end-effector using the known positions
and angles of the joints in the arm. The Perceptual Model permits to compute
the position of the end-effector by looking at it (using the stereo with 2
cameras). If the robot looks at the reflection of the end-effector, the
Perceptual Model calculates the position of the end effector behind the
mirror. So if we have a sample of know positions of the end-effector, and
virtual positions behind the mirror, we can know how the mirror plane
is. Indeed, the virtual positions in the reflection and the real position of
the end-effector are symmetric about the mirror plane.
When we know the position and the orientation of mirror plane compared to the
2 cameras, we can compute the real position of end-effector only by looking
at the reflection and calculating the symmetry.
In the experiment, they used 50 poses of the arm for the training, and 100
for the testing. The results are quite good, because even with only 10 arm
poses the error distance between the position calculated with the
Perspective-Taking Model and position calculated with the End-Effector Model
is less than 5cm. Those results are really encouraging in order to realize a
robot able to pass the “mirror test” .
[1] 1st page of the paper “Mirror Perspective-Taking with a Humanoid Robot”
by Justin W. Hart and Brian Scassellati
---
Abstract
The ability to use a mirror as an instrument for spatial reasoning enables an
agent to make meaningful inferences about the positions of objects in space
based on the appearance of their reflections in mirrors. The model presented
in this paper enables a robot to infer the perspective from which objects
reflected in a mirror appear to be observed, allowing the robot to use this
perspective as a virtual camera. Prior work by our group presented an
architecture through which a robot learns the spatial relationship between
its body and visual sense, mimicking an early form of self-knowledge in which
infants learn about their bodies and senses through their interactions with
each other. In this work, this self-knowledge is utilized in order to
determine the mirror’s perspective. Witnessing the position of its
end-effector in a mirror in several distinct poses, the robot determines a
perspective that is consistent with these observations. The system is
evaluated by measuring how well the robot’s predictions of its end-effector’s
position in 3D, relative to the robot’s egocentric coordinate system, and in
2D, as projected onto it’s cameras, match measurements of a marker tracked by
its stereo vision system. Reconstructions of the 3D position end-effector,
as computed from the perspective of the mirror, are found to agree with the
forward kinematic model within a mean of 31:55mm. When observed directly by
the robot’s cameras, reconstructions agree within 5:12mm. Predictions of the
2D position of the end-effector in the visual field agree with visual
measurements within a mean of 18:47 pixels, when observed in the mirror, or
5:66 pixels, when observed directly by the robot’s cameras.
}}
@inproceedings{kalakrishnan-righetti-11iros_learning-force-control-policies-compliant-manipulation,
title = {Learning force control policies for compliant manipulation }, [pdf]
}}
@article{sharon-stern-12_multi-agent-path-finding-conflict-based,
title={Conflict-based search for optimal multi-agent path finding}, [pdf]
}}
@inproceedings{slowinski-guerin-11_modeling-from-probability-clusters,
title={Learning regions for building a world model from clusters in probability distributions}, [pdf]
}}
@inproceedings{natarajan-joshi-tadepalli-11ijc_imitation-learning-boosting,
title={Imitation learning in relational domains: A functional-gradient boosting approach},
author={Natarajan, S. and Joshi, S. and Tadepalli, P. and Kersting, K. and Shavlik, J.},
booktitle={Proceedings of the Twenty-Second international joint conference on Artificial Intelligence-Volume Volume Two},
pages={1414--1420},
year={2011},
annote = {
####
---review 2013 Ritesh Gautam ~gritesh/cs365/hw2.html
the authors have used the method of Functional-Gradient
Boosting by Friedman which is similiar to the Adaboost algorithm by Freund and
Schapire for supervised learning in relational domains.
--Tree Boosting for Relational Imitation learning (TBRIL)--
The goal of the algorithm is to produce a policy for our learning model using
as input the set of states (S), the set of actions (A) and the set of
features (f) which describes the relation between the states and the action
to be used at any time,where a policy is a mapping from features to actions
given the time step i and the trajectory j.
They use a training set to provide the algorithm with a policy to learn and
later produce it for other instances of features.
The algorithm has a function TBoost that iterates over actions generating
examples for each action using the GenExamples function. The generated
examples are provided to the regression tree learner to calculate the value
of the current model in each step.finally after all the gradient steps we get
the changed value of the gradient, Λ for each action.
---
abstract:
Imitation learning refers to the problem of learning how to behave by
observing a teacher in action. We consider imitation learning in relational
domains, in which there is a varying number of objects and relations among
them. In prior work, simple relational policies are learned by viewing
imitation learning as supervised learning of a function from states to
actions. For propositional worlds, functional gradient methods have been
proved to be beneficial. They are simpler to implement than most existing
methods, more efficient, more naturally satisfy common constraints on the
cost function, and better represent our prior beliefs about the form of the
function. Building on recent generalizations of functional gradient boosting
to relational representations, we implement a functional gradient boosting
approach to imitation learning in relational domains. In particular, given a
set of traces from the human teacher, our system learns a policy in the form
of a set of relational regression trees that additively approximate the
functional gradients. The use of multiple additive trees combined with
relational representation allows for learning more expressive policies than
what has been done before. We demonstrate the usefulness of our approach in
several different domains.
[pdf]
}}
@inproceedings{kober-oztop-11ijc_reinforcement-learning-for-robot-movements,
title={Reinforcement learning to adjust robot movements to new situations}, [pdf]
}}
@inproceedings{erdogan-veloso-11ijc_action-selection-robocup,
title={Action Selection via Learning Behavior Patterns in Multi-Robot Systems},
author={Can Erdogan and Manuela Veloso},
booktitle={IJCAI Proceedings-International Joint Conference on Artificial Intelligence},
volume={22},
number={1},
pages={192},
year={2011},
abstract = {
---review 2013 sugam anand
This paper presents a technique which tries to capture the strategies which
influences the behavior patterns of teams in Robocup Small Size
league.Moreover It also presents an algorithm to select actions to counter
attack the oppostion moves during an episode .The paper is divided into
mainly two parts first they formalise a model which represents the location
and temporal data of robots using trajectories in 2-d image .In second part
they present a notion of trajectory similarity . They model the behaviour of
oppostion by implementing a variant of agglomerative hierarchical clustering
.On basis of this clustering it classifies the behaviour as it occurs in
realtime. and also gives algorithm which autonomously generates moves.Authors
have implemented they research on CMDragons -The SSL Team of CMU and the
results were outstanding.
Note :They have made nonresponsive assumption which means that opposition
will not try to adapt to different strategy (which is influenced by us ) when
we are trying analyize its behaviour patterns and will only be executing a
preplanned strategy
Some Definitions
behaviour pattern : A cluster of similiar sets of trajectories as obtained in
realtime or present from previous match database
Trajectory:A vector of points recorded within a time frame tn-t0 such that
Episode : E[t0,tn] is a time frame during which they want to analyze the
behaviour of opposition and hence deducing its strategies.It begins at t0
when free or indirect kick is given by the referee box until stop commands
tn.
Referee calls : F:free kick I:indirect kick p:penalty k:kickoff S:start
s:stop
Active Agent:It basically corresponds to those robots which either handles
the ball during starting of episode or those who go into opposite half to
align themselves to receive pass.
Trajectory Analysis
The above defined trajectory is represented as 2-d images and then shape
matching algorithms can give notion of similarity between sets of
trajectories. The shape matching approach used is based on hausdorff distance
metric.
Consider two set of trajectories Sx and Sy over some time frame Tx and Ty,
for measuring similarity between them we calculate hausdorff distance between
them as E(p,q)= euclidean distance between points p and q Then they have
formulated they similarity function considering optimisation and inversion
Clustering Techniques
With the help of similarity function they partition the sets of trajectories
into clusters each representing a behaviour.They have also mapped each
cluster with an apprppriate action They have also modified their similarity
function to classify a set of trajectories which starts at t0 and and ends at
tk >tn. Because it lies in two timeframes for which we have clusters there
lies a problem whether to classify it in ci or ci+1
Now to measure the distance between a set of trajectories S and some
clustering ci of cluster C,they compute based on this they classify S into
Some cluster. Moreover, to compare two sets of trajectories stretching over
diffrent timeframes,if they have to be compared with one complete and other
incomplete,they applied a heuristic and modified similarity function
[red] is function which shortens the complete trajectory so that it can be
compared to the short one. Due to small dataset they had to implement a
variant of hierarchical clustering because outliers can significantly affect
the partitioning .Also density based clustering cannot cluster such data and
gives large variance in densities.
Classification in Realtime And Selecting Actions
The paper finally concludes with explanation of classification during game
and Algorithm to select optimum actions. The SelectAction algorithm takes as
input current state of the game and it then extracts the behaviour patterns
from the state and it classifies the pattern into cluster according to it and
this cluster has a action associated with it which is then executed if
applicable. Functions used
getObservedPattern : Returns the behaviour pattern observed during an
episode.
onlineClassifier : Classifies the behaviour pattern into cluster using
existing database
getOptimalAction : Returns the most appropriate action which could be
performed in that scenario.
Applicable : Returns the feasiblity of above returned action ie ,if it could
be executed before it becomes outdated.
With the nonresponsive assumption they have been able to get success rate of
70-80% .Here success is associated with successful interception of opposition
pass.
Comments
Since they assumed that opposite team will not modify its strategies during
gameplay which is fair assumption but if we force to have matches between
teams with same algorithms then it might lead to "chicken and egg "problem.
Both team will try to adjust its passes with the history.And the passing team
will know about the moves which was intercepted in previous scenario ,hence
now both will react in strange manner
---
The RoboCup robot soccer Small Size League has been running since 1997 with
many teams successfully competiting and very effectively playing the
games. Teams of five robots, with a combined autonomous centralized
perception and control, and distributed actuation, move at high speeds in the
field space, actuating a golf ball by passing and shooting it to aim at
scoring goals. Most teams run their own pre-defined team strategies, unknown
to the other teams, with flexible game-state dependent assignment of robot
roles and positioning. However, in this fast-paced noisy real robot league,
recognizing the opponent team strategies and accordingly adapting one's own
play has proven to be a considerable challenge. In this work, we analyze
logged data of real games gathered by the CMDragons team, and contribute
several results in learning and responding to opponent strategies. We define
episodes as segments of interest in the logged data, and introduce a
representation that captures the spatial and temporal data of the multi-robot
system as instances of geometrical trajectory curves. We then learn a model
of the team strategies through a variant of agglomerative hierarchical
clustering. Using the learned cluster model, we are able to classify a team
behavior incrementally as it occurs. Finally, we define an algorithm that
autonomously generates counter tactics, in a simulation based on the real
logs, showing that it can recognize and respond to opponent strategies.
[pdf]
}}
@inproceedings{macalpine-stone-12_omnidirectional-humanoid-robocup-winner,
title={Design and optimization of an omnidirectional humanoid walk: A winning approach at the RoboCup 2011 3D simulation competition}, [pdf]
}}
@article{hawes-klenk-12_spatial-regions-based-on-context,
title={Towards a Cognitive System That Can Recognize Spatial Regions Based on Context},
author={Nick Hawes and Matthew Klenk and Kate Lockwood and Graham S. Horn, G.S. and Kelleher, J.D.},
year={2012}
booktitle={Twenty-Sixth AAAI Conference on Artificial Intelligence},
annote = {
a phrase such as "the front of the classroom" is determined not by geometry
per se, but in terms of the objects present in the room (chairs, a desk, a
whiteboard), their role in this context (seats for students to watch a
teacher who writes on the whiteboard) and their configuration in space (the
seats point toward the whiteboard). These regions as are named
context-dependent spatial regions (CDSRs), and an attempt is made with a
mobile robot to understand them.
####
---review 2013 Ayush Varshney (10183) February 26, 2013
Synopsis
The paper describes a cognitive system that can recognize spatial regions
based on the context they are presented to the system. To understand the
problem take this example:
Command: Find the position for the refree in a stadium
The solution depends on the game being played in the stadium which in itself
can be determined by the relative position of players, ball, etc. Such areas
are referred to as Context Dependent Spatial
Regions CDSRs in this paper. The cognitive system described in this paper can
learn CDSRs by using semantic labels, Qualitative Spatial Representations
(QSRs) and analogy.
Introduction
The paper describes, in specific the problem of making a bot find the front
of the classroom based on the configuration of objects such as tables and
chairs present in the room (‘the context’). The work is based on Dora, a
mobile cognitive robot with a pre-existing multi-layered spatial model [1].
Dora uses vision to recognize pre-trained 3D object models and prepares a
metric map which basically a set of lines in 2D global coordinate frame.
The strengths of 8 spatial relations between that object (detected by Dora)
and each of the objects adjacent to it (adjacency being determined using a
Voronoi Diagram [2]) is calculated. For this, the spatial relationships (s)
between adjacent objects is calculated as:
[EQN]
Where
d: the distance between the landmark’s centroid and the adjacent object’s
location
ɵ: the inner angle between the direction vector of the relation and the
vector from the origin (the landmark’s centroid) to the neighbour’s location.
This helps in QSR Extraction.2
Methods Used
• Representing CDSRs
Anchor Points are used to represent CDSRs [3]. These are symbolic
descriptions which link a conceptual entity to a perceived entity. The
perceived objects are the room and the ones recognized by Dora. Anchor points
are created from the entities perceived using Unary Functions like
YMinXFewestFn. Example of CDSR representation:
* Using Analogy
To save the user from the pain of training for all the contexts the system
uses analogy. For example if the Bot is trained where the front of a
classroom after perceiving a class and objects in it, it is capable of
recognizing the front – of any other class of the same structure.
Structure-Mapping Engine [4] is employed to perform analogical matching in
the system.
Example System Run
• Setup
The approach was simulated on six class rooms and two simulated studio
apartments. The base and target representations were created by making Dora
wander around two different classrooms and a map created. QSRs are generated
using map and object data.
• Evaluation [5]3
These results support the hypothesis that anchor points can provide a
symbolic representation on top of sensor data for context-dependent spatial
regions, and, when combined with qualitative spatial relations, they
facilitate learning from a single example through analogical transfer
References
[1]M.H.C. Gretton; M. Gobelbecker. “Dora, a Robot Exploiting Probabilistic Knowledge under Uncertain
Sensing for Efficient Object Search”
[2] Book: Spatial Tessellations – Concepts and Applications of Voronoi Diagrams: Second Ed. Wiley ISBN 0-
471-98635-6 Page: 441-446
[3] Klenk, M.; Hawes, N.; Lockwood, K.; Horn, G.S.; Kelleher, J.D.; "Using Anchor Points to Define and Transfer
Spatial Regions Based on Context"
[4] Falkenhainer, B.; Forbus K.D.; Gentner, D.; “The Structure-Mapping Engine: Algorithm and Examples”
[5] Klenk, M.; Hawes, N.; Lockwood, K.; Horn, G.S.; Kelleher, J.D.; "Towards
a Cognitive System That can Recognize Spatial Regions Based on Context"
abstract:
In order to collaborate with people in the real world, cognitive systems must
be able to represent and reason about spatial regions in human
environments. Consider the command “go to the front of the classroom”. The
spatial region mentioned (the front of the classroom) is not perceivable
using geometry alone. Instead it is defined by its functional use, implied by
nearby objects and their configuration. In this paper, we define such areas
as context-dependent spatial regions and present a cognitive system able to
learn them by combining qualitative spatial representations, semantic labels,
and analogy. The system is capable of generating a collection of qualitative
spatial representations describing the configuration of the entities it
perceives in the world. It can then be taught context-dependent spatial
regions using anchor points defined on these representations. From this we
then demonstrate how an existing computational model of analogy can be used
to detect context-dependent spatial regions in previously unseen rooms. To
evaluate this process we compare detected regions to annotations made on maps
of real rooms by human volunteers.
[pdf]
}}
ATTENTION
@inproceedings{jiang-crookes-12_visual-saliency-estimation-via-manifold-learning,
title={Visual Saliency Estimation through Manifold Learning}, [pdf]
}}
@inproceedings{borji-itti-12_object-based-top-down-attention,
title={An Object-Based Bayesian Framework for Top-Down Visual Attention}, [pdf]
}}
BRAIN-INTERFACE
@inproceedings{chung-cheung-11ijc_hierarchical-brain-computer-interface,
title={A hierarchical architecture for adaptive brain-computer interfacing}, [pdf]
}}
LOGIC
@inproceedings{hinrichs-forbus-12_learning-qualitative-models-by-demonstration,
title={Learning Qualitative Models by Demonstration},
author={Hinrichs, T.R. and Forbus, K.D.},
booktitle={Twenty-Sixth AAAI Conference on Artificial Intelligence},
year={2012},
annote =
---review 2013 gurpreet ~gpskalra/cs365/hw2/paper_summary.pdf
based on 'Qualitative Process Theory" [2] which is useful for giving a
qualitative representation of quantities in terms of inequalities. They
de ne a quantitative model as a directed acyclic graph of in
uences between
quantities conditioned by active processes that drive change [3]. They then
use this model to guide the behavior of a player (Playing Freeciv) through
demonstration.
Their work and objectives are summarized below:
* Decomposing goals into subgoals and nding the shortest path from a legal
action to the goal using back propogation. [1]
* During the demonstration of the game,learn the user's motivation in
taking an action,the causes behind game events, quantity changes that
happen due to actions within a turn, and across turns and thus
construct a qualitative model. [3]
* Learn direct and indirect qualitative in
uences using Quantitative
Process theory and Microtheory Inheritance. [3]
* Learn to reach legal actions using hierarchical task network [3]
* Learning quantitative relations through three sub tasks: Identifying the
independent variable, identifying the dependent variable,and
incrementally inducing the function. [3]
Creating software agents that learn interactively requires the ability to
learn from a small number of trials, extracting general, flexible knowledge
that can drive behavior from observation and interaction. We claim that
qualitative models provide a useful intermediate level of causal
representation for dynamic domains, including the formulation of strategies
and tactics. We argue that qualitative models are quickly learnable, and
enable model based reasoning techniques to be used to recognize,
operationalize, and construct more strategic knowledge. This paper describes
an approach to incrementally learning qualitative influences by demonstration
in the context of a strategy game. We show how the learned model can help a
system play by enabling it to explain which actions could contribute to
maximizing a quantitative goal. We also show how reasoning about the model
allows it to reformulate a learning problem to address delayed effects and
credit assignment, such that it can improve its performance on more strategic
tasks such as city placement
[pdf]
}}
@inproceedings{benferhat-hue-11ijc_interval-based-possibilistic-logic,
title={Interval-based possibilistic logic}, [pdf]
benferhat-hue-11ijc_ashudeep-review
}}
GAME PLAY
@article{barker-korf-12_solving-peg-solitaire,
title={Solving Peg Solitaire with Bidirectional BFIDA}, [pdf]
}}
VISION: OBJECT RECOGNITION
@article{hinton-srivastava-12_NN-prevents-co-adaptation-of-feature-detectors,
title={Improving neural networks by preventing co-adaptation of feature detectors},
author={Hinton, G.E. and Srivastava, N. and Krizhevsky, A. and Sutskever, I. and Salakhutdinov, R.R.},
journal={arXiv preprint arXiv:1207.0580},
year={2012},
annote = {
imagenet = more than 1000 object classes, organized in a hierarchy based on
wordnet, with 1000s of images in most classes.
RESULT:
winning entry in imagenet challenge 2010 was based on deep-NN with error rate
of 47.2% on the test set. The current state-of-the-art result on this dataset
is 45.7%. We achieved comparable performance of 48.6% error using a single
neural network with five convolutional hidden layers interleaved with
“max-pooling” layer followed by two globally connected layers and a final
1000-way softmax layer. All layers had L2 weight constraints on the incoming
weights of each hidden unit. Using 50% dropout in the sixth hidden layer
reduces this to a record 42.4%.
---
When a large feedforward neural network is trained on a small training set,
it typically performs poorly on held-out test data. This “overfitting” is
greatly reduced by randomly omitting half of the feature detectors on each
training case. This prevents complex co-adaptations in which a feature
detector is only helpful in the context of several other specific feature
detectors. Instead, each neuron learns to detect a feature that is generally
helpful for producing the correct answer given the combinatorially large
variety of internal contexts in which it must operate. Random “dropout” gives
big improvements on many benchmark tasks and sets new records for speech and
object recognition.
[pdf]
}}
@article{krizhevsky-hinton-12-imagenet-convolutional-NN-deep,
title={ImageNet classification with deep convolutional neural networks},
@inproceedings{geiger-lauer-11cvpr_generative-3D-urban-scene-understanding,
title={A generative model for 3d urban scene understanding from movable platforms},
author={Geiger, A. and Lauer, M. and Urtasun, R.},
booktitle={Computer Vision and Pattern Recognition (CVPR), 2011 IEEE Conference on},
pages={1945--1952},
year={2011},
organization={IEEE}
[see their followup work in CVPR12 : geiger-lenz-12_autonomous-driving]
Traffic scene modeling - given a sequence of surveillance images, infers
traffic flow, and identifies streets, number of streets at a junction,
traffic behaviour, and also scene features such as
buildings, etc..
basic inferencing based on extension of metropolis-hastings algo called
Reversible Jump-Markov chain Monte Carlo (MCMC).
main idea: enables comparisons of different probabilistic models w different
topologies (and diff density distributions) by constructing a bijection
(jump) between them via addl states. Reversible Jump = RJ-MCMC
---13 365 Anant Raj:
Presented model is generative so sampling can be done from it. Since the
described approach is very general and takes into account both the dynamic
features and static features. So by putting constraints on dynamic features
static scene can be anaysed and vice versa. They have described the result of
camparison between the GP regression and the presented approach[3]. Also this
approach can be used in improving the object detection result and semantic
scene segmentation due to it's geometrical and topological constraints. It is
more likly a car to be on the road in place of home or indoors. Same case
goes with the scene also.
[pdf]
}}
@inproceedings{parkhi-vedaldi-zisserman-jawahar-12_cats-and-dogs,
title={Cats and dogs},
author={Parkhi, O.M. and Vedaldi, A. and Zisserman, A. and Jawahar, CV},
booktitle={Computer Vision and Pattern Recognition (CVPR), 2012 IEEE Conference on},
pages={3498--3505},
year={2012},
annote = {
We investigate the fine grained object categorization problem of determining
the breed of animal from an image. To this end we introduce a new annotated
dataset of pets, the Oxford-IIIT-Pet dataset, covering 37 different breeds of
cats and dogs. The visual problem is very challenging as these animals,
particularly cats, are very deformable and there can be quite subtle
differences between the breeds.
We make a number of contributions: first, we introduce a model to classify a
pet breed automatically from an image. The model combines shape, captured by
a deformable part model detecting the pet face, and appearance, captured by a
bag-of-words model that describes the pet fur. Fitting the model involves
automatically segmenting the animal in the image. Second, we compare two
classification approaches: a hierarchical one, in which a pet is first
assigned to the cat or dog family and then to a breed, and a flat one, in
which the breed is obtained directly. We also investigate a number of animal
and image orientated spatial layouts.
These models are very good: they beat all previously published results on the
challenging ASIRRA test (cat vs dog discrimination). When applied to the task
of discriminating the 37 different breeds of pets, the models obtain an
average accuracy of about 59%, a very encouraging result considering the
difficulty of the problem.
[pdf]
}}
@article{vezhnevets-ferrari-12_weakly-supervised-semantic-segmentation,
title={Weakly Supervised Structured Output Learning for Semantic Segmentation},
author={Vezhnevets, A. and Ferrari, V. and Buhmann, J.M.}
booktitle={Computer Vision and Pattern Recognition (CVPR), 2012 IEEE Conference on},
year={2012},
annote = {
[semantic segmentation = assign a label for each pixel:
(e.g. "dog", "car" or "road").]
standard approach: fullly supervised (every pixel is
manually labeled) [1, 2, 3, 4, 5] --> high annotation cost.
weakly supervised methods: [6,7]
tests on label-me dataset. comparisons only within own algorithms. ]
ABSTRACT
We address the problem of weakly supervised semantic segmentation. The
training images are labeled only by the classes they contain, not by their
location in the image. On test images instead, the method must predict a
class label for every pixel. Our goal is to enable segmentation algorithms to
use multiple visual cues in this weakly supervised setting, analogous to what
is achieved by fully supervised methods. However, it is difficult to assess
the relative usefulness of different visual cues from weakly supervised
training data. We define a parametric family of structured models, where each
model weighs visual cues in a different way. We propose a Maximum Expected
Agreement model selection principle that evaluates the quality of a model
from the family without looking at superpixel labels. Searching for the best
model is a hard optimization problem, which has no analytic gradient and
multiple local optima. We cast it as a Bayesian optimization problem and
propose an algorithm based on Gaussian processes to efficiently solve it. Our
second contribution is an Extremely Randomized Hashing Forest that represents
diverse superpixel features as a sparse binary vector. It enables using
appearance models of visual classes that are fast at training and testing and
yet accurate. Experiments on the SIFT-flow data-set show a significant
improvement over previous weakly supervised methods and even over some fully
supervised methods.
We formulate semantic segmentation as
a pairwise CRF, as in other works [1, 7, 5, 6]. The task of
the model is to infer latent superpixel labels in training images
and learn appearance models of classes.
Our second contribution is an improved representation
of the appearance models of semantic classes:
xtremely Randomized Hashing Forest (ERHF).
[pdf]
}}
@inproceedings{kavukcuoglu-ranzato-lecun-09cvpr_learning-invariant-features,
title={Learning invariant features through topographic filter maps}, [pdf]
}}
@inproceedings{schulz-behnke-11_object-segmentation-deep-convolutional-net,
title={Object-class segmentation using deep convolutional neural networks}, [pdf]
}}
@InProceedings{tangY-salakhutdinov-hinton-12icml_deep-lambertian-albedo-learning,
author = {Yichuan Tang and Ruslan Salakhutdinov and Geoffrey Hinton},
title = {Deep Lambertian Networks},
booktitle = {Proceedings of the 29th International Conference on Machine Learning (ICML-12)},
series = {ICML '12},
year = {2012},
editor = {John Langford and Joelle Pineau},
location = {Edinburgh, Scotland, GB},
isbn = {978-1-4503-1285-1},
month = {July},
publisher = {Omnipress},
address = {New York, NY, USA},
pages= {1623--1630},
annote = {
Abstract: Visual perception is a challenging problem in part due to
illumination variations. A possible solution is to first estimate an
illumination invariant representation before using it for recognition. The
object albedo and surface normals are examples of such representation. In
this paper, we introduce a multilayer generative model where the latent
variables include the albedo, surface normals, and the light
source. Combining Deep Belief Nets with the Lambertian reflectance
assumption, our model can learn good priors over the albedo from 2D
images. Illumination variations can be explained by changing only the
lighting latent variable in our model. By transferring learned knowledge from
similar objects, albedo and surface normals estimation from a single image is
possible in our model. Experiments demonstrate that our model is able to
generalize as well as improve over standard baselines in one-shot face
recognition.
discussion+video: http://icml.cc/discuss/2012/791.html
[pdf]
}}
COMPUTER-AIDED INSTRUCTION
@inproceedings{singh-gulwani-12_automatically-generating-algebra-problems.
title= {Automatically Generating Algebra Problems}, [pdf]
}}
MULTI-AGENT SYSTEMS
@inproceedings{brooks-iba_11ijc-emergence-and-convergence-of-norms,
title={Modeling the emergence and convergence of norms},
author={Brooks, L. and Iba, W. and Sen, S.},
booktitle={Proceedings of the Twenty-Second international joint conference on Artificial Intelligence-Volume Volume One},
pages={97--102},
year={2011},
abstract = {
In many multi-agent systems, the emergence of norms is the primary factor
that determines overall behavior and utility. Agent simulations can be used
to predict and study the development of these norms. However, a large number
of simulations is usually required to provide an accurate depiction of the
agents’ behavior, and some rare contingencies may still be overlooked
completely. The cost and risk involved with agent simulations can be reduced
by analyzing a system theoretically and producing models of its behavior. We
use such a theoretical approach to examine the dynamics of a population of
agents playing a coordination game to determine all the norms to which the
society can converge, and develop a system of linear recurrence relations
that predict how frequently each of these norms will be reached, as well as
the average convergence time. This analysis produces certain guarantees about
system behavior that canot be provided by a purely empirical approach, and
can be used to make predictions about the emergence of norms that numerically
match those obtained through large-scale simulations.
doi: 10.5591/978-1-57735-516-8/IJCAI11-028
[pdf]
}}
@inproceedings{levy-markovitch-12_machine-learning-from-metaphor,
title={Teaching Machines to Learn by Metaphors}, [pdf]
}}