OpenRaiser/Intern-Atlas huggingface dataset:
Measuring the similarity between implicit semantic relations from the web
Authors: Danushka Bollegala, Yutaka Matsuo, Mitsuru Ishizuka
Venue: Conference WWW 2009
Year: 2009

Measuring the similarity between semantic relations that hold among entities is an important and necessary step in various Web related tasks such as relation extraction, information retrieval and analogy detection. For example, consider the case in which a person knows a pair of entities (e.g. Google, YouTube), between which a particular relation holds (e.g. acquisition). The person is interested in retrieving other such pairs with similar relations (e.g. Microsoft, Powerset). Existing keyword-based search engines cannot be applied directly in this case because, in keyword-based search, the goal is to retrieve documents that are relevant to the words used in a query -- not necessarily to the relations implied by a pair of words. We propose a relational similarity measure, using a Web search engine, to compute the similarity between semantic relations implied by two pairs of words. Our method has three components: representing the various semantic relations that exist between a pair of words using automatically extracted lexical patterns, clustering the extracted lexical patterns to identify the different patterns that express a particular semantic relation, and measuring the similarity between semantic relations using a metric learning approach. We evaluate the proposed method in two tasks: classifying semantic relations between named entities, and solving word-analogy questions. The proposed method outperforms all baselines in a relation classification task with a statistically significant average precision score of 0.74. Moreover, it reduces the time taken by Latent Relational Analysis to process 374 word-analogy questions from 9 days to less than 6 hours, with an SAT score of 51%.
Relational duality: Unsupervised extraction of semantic relations between entities on the web
Authors: Danushka Bollegala, Yutaka Matsuo, Mitsuru Ishizuka
Venue: Conference WWW 2010
Year: 2010

Extracting semantic relations among entities is an important first step in various tasks in Web mining and natural language processing such as information extraction, relation detection, and social network mining. A relation can be expressed extensionally by stating all the instances of that relation or intensionally by defining all the paraphrases of that relation. For example, consider the ACQUISITION relation between two companies. An extensional definition of ACQUISITION contains all pairs of companies in which one company is acquired by another (e.g. (YouTube, Google) or (Powerset, Microsoft)). On the other hand we can intensionally define ACQUISITION as the relation described by lexical patterns such as X is acquired by Y, or Y purchased X, where X and Y denote two companies. We use this dual representation of semantic relations to propose a novel sequential co-clustering algorithm that can extract numerous relations efficiently from unlabeled data. We provide an efficient heuristic to find the parameters of the proposed coclustering algorithm. Using the clusters produced by the algorithm, we train an L1 regularized logistic regression model to identify the representative patterns that describe the relation expressed by each cluster. We evaluate the proposed method in three different tasks: measuring relational similarity between entity pairs, open information extraction (Open IE), and classifying relations in a social network system. Experiments conducted using a benchmark dataset show that the proposed method improves existing relational similarity measures. Moreover, the proposed method significantly outperforms the current state-of-the-art Open IE systems in terms of both precision and recall. The proposed method correctly classifies 53 relation types in an online social network containing 470; 671 nodes and 35; 652; 475 edges, thereby demonstrating its efficacy in real-world relation detection tasks.
High performance question/answering
Authors: Marius Pasca, Sanda M. Harabagiu
Venue: Conference SIGIR 2001
Year: 2001

In this paper we present the features of a Question/Answering (Q/A) system that had unparalleled performance in the TREC-9 evaluations. We explain the accuracy of our system through the unique characteristics of its architecture: (1) usage of a wide-coverage answer type taxonomy; (2) repeated passage retrieval; (3) lexico-semantic feedback loops; (4) extraction of the answers based on machine learning techniques; and (5) answer caching. Experimental results show the effects of each feature on the overall performance of the Q/A system and lead to general conclusions about Q/A from large text collections.
New perspectives and methods in link prediction
Authors: Ryan Lichtenwalter, Jake T. Lussier, Nitesh V. Chawla
Venue: Conference KDD 2010
Year: 2010

This paper examines important factors for link prediction in networks and provides a general, high-performance framework for the prediction task. Link prediction in sparse networks presents a significant challenge due to the inherent disproportion of links that can form to links that do form. Previous research has typically approached this as an unsupervised problem. While this is not the first work to explore supervised learning, many factors significant in influencing and guiding classification remain unexplored. In this paper, we consider these factors by first motivating the use of a supervised framework through a careful investigation of issues such as network observational period, generality of existing methods, variance reduction, topological causes and degrees of imbalance, and sampling approaches. We also present an effective flow-based predicting algorithm, offer formal bounds on imbalance in sparse network link prediction, and employ an evaluation method appropriate for the observed imbalance. Our careful consideration of the above issues ultimately leads to a completely general framework that outperforms unsupervised link prediction methods by more than 30% AUC.
New approaches to support vector ordinal regression
Authors: Wei Chu, S. Sathiya Keerthi
Venue: Conference ICML 2005
Year: 2005

In this paper, we propose two new support vector approaches for ordinal regression, which optimize multiple thresholds to define parallel discriminant hyperplanes for the ordinal scales. Both approaches guarantee that the thresholds are properly ordered at the optimal solution. The size of these optimization problems is linear in the number of training samples. The SMO algorithm is adapted for the resulting optimization problems; it is extremely easy to implement and scales efficiently as a quadratic function of the number of examples. The results of numerical experiments on benchmark datasets verify the usefulness of these approaches.
Robust multi-class transductive learning with graphs
Authors: Wei Liu 0005, Shih-Fu Chang
Venue: Conference CVPR 2009
Year: 2009

Graph-based methods form a main category of semi-supervised learning, offering flexibility and easy implementation in many applications. However, the performance of these methods is often sensitive to the construction of a neighborhood graph, which is non-trivial for many real-world problems. In this paper, we propose a novel framework that builds on learning the graph given labeled and unlabeled data. The paper has two major contributions. Firstly, we use a nonparametric algorithm to learn the entire adjacency matrix of a symmetry-favored k-NN graph, assuming that the matrix is doubly stochastic. The nonparametric algorithm makes the constructed graph highly robust to noisy samples and capable of approximating underlying submanifolds or clusters. Secondly, to address multi-class semi-supervised classification, we formulate a constrained label propagation problem on the learned graph by incorporating class priors, leading to a simple closed-form solution. Experimental results on both synthetic and real-world datasets show that our approach is significantly better than the state-of-the-art graph-based semi-supervised learning algorithms in terms of accuracy and robustness.
Discriminant analysis with tensor representation
Authors: Shuicheng Yan, Dong Xu 0001, Qiang Yang 0001, Lei Zhang 0001, Xiaoou Tang, HongJiang Zhang
Venue: Conference CVPR 2005
Year: 2005

In this paper, we present a novel approach to solving the supervised dimensionality reduction problem by encoding an image object as a general tensor of 2nd or higher order. First, we propose a discriminant tensor criterion (DTC), whereby multiple interrelated lower-dimensional discriminative subspaces are derived for feature selection. Then, a novel approach called k-mode cluster-based discriminant analysis is presented to iteratively learn these subspaces by unfolding the tensor along different tensor dimensions. We call this algorithm discriminant analysis with tensor representation (DATER), which has the following characteristics: 1) multiple interrelated subspaces can collaborate to discriminate different classes; 2) for classification problems involving higher-order tensors, the DATER algorithm can avoid the curse of dimensionality dilemma and overcome the small sample size problem; and 3) the computational cost in the learning stage is reduced to a large extent owing to the reduced data dimensions in generalized eigenvalue decomposition. We provide extensive experiments by encoding face images as 2nd or 3rd order tensors to demonstrate that the proposed DATER algorithm based on higher order tensors has the potential to outperform the traditional subspace learning algorithms, especially in the small sample size cases.
Non-linear matrix factorization with gaussian processes
Authors: Neil D. Lawrence, Raquel Urtasun
Venue: Conference ICML 2009
Year: 2009

A popular approach to collaborative filtering is matrix factorization. In this paper we develop a non-linear probabilistic matrix factorization using Gaussian process latent variable models. We use stochastic gradient descent (SGD) to optimize the model. SGD allows us to apply Gaussian processes to data sets with millions of observations without approximate methods. We apply our approach to benchmark movie recommender data sets. The results show better than previous state-of-the-art performance.
Yago: A core of semantic knowledge
Authors: Fabian M. Suchanek, Gjergji Kasneci, Gerhard Weikum
Venue: Conference WWW 2007
Year: 2007

We present YAGO, a light-weight and extensible ontology with high coverage and quality. YAGO builds on entities and relations and currently contains more than 1 million entities and 5 million facts. This includes the Is-A hierarchy as well as non-taxonomic relations between entities (such as HASONEPRIZE). The facts have been automatically extracted from Wikipedia and unified with WordNet, using a carefully designed combination of rule-based and heuristic methods described in this paper. The resulting knowledge base is a major step beyond WordNet: in quality by adding knowledge about individuals like persons, organizations, products, etc. with their semantic relationships - and in quantity by increasing the number of facts by more than an order of magnitude. Our empirical evaluation of fact correctness shows an accuracy of about 95%. YAGO is based on a logically clean model, which is decidable, extensible, and compatible with RDFS. Finally, we show how YAGO can be further extended by state-of-the-art information extraction techniques.
Optimal scanning for faster object detection
Authors: Nicholas J. Butko, Javier R. Movellan
Venue: Conference CVPR 2009
Year: 2009

Recent years have seen the development of fast and accurate algorithms for detecting objects in images. However, as the size of the scene grows, so do the running-times of these algorithms. If a 128×102 pixel image requires 20 ms to process, searching for objects in a 1280×1024 image will take 2 s. This is unsuitable under real-time operating constraints: by the time a frame has been processed, the object may have moved. An analogous problem occurs when controlling robot camera that need to scan scenes in search of target objects. In this paper, we consider a method for improving the run-time of general-purpose object-detection algorithms. Our method is based on a model of visual search in humans, which schedules eye fixations to maximize the long-term information accrued about the location of the target of interest. The approach can be used to drive robot cameras that physically scan scenes or to improve the scanning speed for very large high resolution images. We consider the latter application in this work by simulating a “digital fovea” and sequentially placing it in various regions of an image in a way that maximizes the expected information gain. We evaluate the approach using the OpenCV version of the Viola-Jones face detector. After accounting for all computational overhead introduced by the fixation controller, the approach doubles the speed of the standard Viola-Jones detector at little cost in accuracy.
Decomposing a scene into geometric and semantically consistent regions
Authors: Stephen Gould, Richard Fulton, Daphne Koller
Venue: Conference ICCV 2009
Year: 2009

High-level, or holistic, scene understanding involves reasoning about objects, regions, and the 3D relationships between them. This requires a representation above the level of pixels that can be endowed with high-level attributes such as class of object/region, its orientation, and (rough 3D) location within the scene. Towards this goal, we propose a region-based model which combines appearance and scene geometry to automatically decompose a scene into semantically meaningful regions. Our model is defined in terms of a unified energy function over scene appearance and structure. We show how this energy function can be learned from data and present an efficient inference technique that makes use of multiple over-segmentations of the image to propose moves in the energy-space. We show, experimentally, that our method achieves state-of-the-art performance on the tasks of both multi-class image segmentation and geometric reasoning. Finally, by understanding region classes and geometry, we show how our model can be used as the basis for 3D reconstruction of the scene.
Relevance assessment: are judges exchangeable and does it matter
Authors: Peter Bailey, Nick Craswell, Ian Soboroff, Paul Thomas, Arjen P. de Vries, Emine Yilmaz
Venue: Conference SIGIR 2008
Year: 2008

We investigate to what extent people making relevance judgements for a reusable IR test collection are exchangeable. We consider three classes of judge: "gold standard" judges, who are topic originators and are experts in a particular information seeking task; "silver standard" judges, who are task experts but did not create topics; and "bronze standard" judges, who are those who did not define topics and are not experts in the task.
Softrank: optimizing non-smooth rank metrics
Authors: Michael J. Taylor, John Guiver, Stephen Robertson, Tom Minka
Venue: Conference WSDM 2008
Year: 2008

We address the problem of learning large complex ranking functions. Most IR applications use evaluation metrics that depend only upon the ranks of documents. However, most ranking functions generate document scores, which are sorted to produce a ranking. Hence IR metrics are innately non-smooth with respect to the scores, due to the sort. Unfortunately, many machine learning algorithms require the gradient of a training objective in order to perform the optimization of the model parameters,and because IR metrics are non-smooth,we need to find a smooth proxy objective that can be used for training. We present a new family of training objectives that are derived from the rank distributions of documents, induced by smoothed scores. We call this approach SoftRank. We focus on a smoothed approximation to Normalized Discounted Cumulative Gain (NDCG), called SoftNDCG and we compare it with three other training objectives in the recent literature. We present two main results. First, SoftRank yields a very good way of optimizing NDCG. Second, we show that it is possible to achieve state of the art test set NDCG results by optimizing a soft NDCG objective on the training set with a different discount function
Segment-based stereo matching using graph cuts
Authors: Li Hong, George Chen 0001
Venue: Conference CVPR 2004
Year: 2004

In this paper we present a new segment-based stereo matching algorithm using graph cuts. In our approach, the reference image is divided into non-overlapping homogeneous segments and the scene structure is represented as a set of planes in the disparity space. The stereo matching problem is formulated as an energy minimization problem in the segment domain instead of the traditional pixel domain. Graph cuts technique is used to fast approximate the optimal solution, which assigns the corresponding disparity plane to each segment. Experiments demonstrate that the performance of our algorithm is comparable to the state-of-the-art stereo algorithms on various data sets. Furthermore, strong performance is achieved in the conventionally difficult areas such as: textureless regions, disparity discontinuous boundaries and occluded portions.
High-accuracy stereo depth maps using structured light
Authors: Daniel Scharstein, Richard Szeliski
Venue: Conference CVPR 2003
Year: 2003

Progress in stereo algorithm performance is quickly outpacing the ability of existing stereo data sets to discriminate among the best-performing algorithms, motivating the need for more challenging scenes with accurate ground truth information. This paper describes a method for acquiring high-complexity stereo image pairs with pixel-accurate correspondence information using structured light. Unlike traditional range-sensing approaches, our method does not require the calibration of the light sources and yields registered disparity maps between all pairs of cameras and illumination projectors. We present new stereo data sets acquired with our method and demonstrate their suitability for stereo algorithm evaluation. Our results are available at http://www.middlebury.edu/stereo/.
Covering trees and lower-bounds on quadratic assignment
Authors: Julian Yarkony, Charless C. Fowlkes, Alexander Ihler
Venue: Conference CVPR 2010
Year: 2010

Many computer vision problems involving feature correspondence among images can be formulated as an assignment problem with a quadratic cost function. Such problems are computationally infeasible in general but recent advances in discrete optimization such as tree-reweighted belief propagation (TRW) often provide high-quality solutions. In this paper, we improve upon these algorithms in two ways. First, we introduce covering trees, a variant of TRW which provide the same bounds on the MAP energy as TRW with far fewer variational parameters. Optimization of these parameters can be carried out efficiently using either fixed-point iterations (as in TRW) or sub-gradient based techniques. Second, we introduce a new technique that utilizes bipartite matching applied to the min-marginals produced with covering trees in order to compute a tighter lower-bound for the quadratic assignment problem. We apply this machinery to the problem of finding correspondences with pairwise energy functions, and demonstrate the resulting hybrid method outperforms TRW alone and a recent related subproblem decomposition algorithm on benchmark image correspondence problems.
Using relative novelty to identify useful temporal abstractions in reinforcement learning
Authors: Özgür Simsek, Andrew G. Barto
Venue: Conference ICML 2004
Year: 2004

We present a new method for automatically creating useful temporal abstractions in reinforcement learning. We argue that states that allow the agent to transition to a different region of the state space are useful subgoals, and propose a method for identifying them using the concept of relative novelty. When such a state is identified, a temporally-extended activity (e.g., an option) is generated that takes the agent efficiently to this state. We illustrate the utility of the method in a number of tasks.
Modeling online reviews with multi-grain topic models
Authors: Ivan Titov, Ryan T. McDonald
Venue: Conference WWW 2008
Year: 2008

In this paper we present a novel framework for extracting the ratable aspects of objects from online user reviews. Extracting such aspects is an important challenge in automatically mining product opinions from the web and in generating opinion-based summaries of user reviews [18, 19, 7, 12, 27, 36, 21]. Our models are based on extensions to standard topic modeling methods such as LDA and PLSA to induce multi-grain topics. We argue that multi-grain models are more appropriate for our task since standard models tend to produce topics that correspond to global properties of objects (e.g., the brand of a product type) rather than the aspects of an object that tend to be rated by a user. The models we present not only extract ratable aspects, but also cluster them into coherent topics, e.g., 'waitress' and 'bartender' are part of the same topic 'staff' for restaurants. This differentiates it from much of the previous work which extracts aspects through term frequency analysis with minimal clustering. We evaluate the multi-grain models both qualitatively and quantitatively to show that they improve significantly upon standard topic models.
Data summaries for on-demand queries over linked data
Authors: Andreas Harth, Katja Hose, Marcel Karnstedt, Axel Polleres, Kai-Uwe Sattler, Jürgen Umbrich
Venue: Conference WWW 2010
Year: 2010

Typical approaches for querying structured Web Data collect (crawl) and pre-process (index) large amounts of data in a central data repository before allowing for query answering. However, this time-consuming pre-processing phase however leverages the benefits of Linked Data -- where structured data is accessible live and up-to-date at distributed Web resources that may change constantly -- only to a limited degree, as query results can never be current. An ideal query answering system for Linked Data should return current answers in a reasonable amount of time, even on corpora as large as the Web. Query processors evaluating queries directly on the live sources require knowledge of the contents of data sources. In this paper, we develop and evaluate an approximate index structure summarising graph-structured content of sources adhering to Linked Data principles, provide an algorithm for answering conjunctive queries over Linked Data on theWeb exploiting the source summary, and evaluate the system using synthetically generated queries. The experimental results show that our lightweight index structure enables complete and up-to-date query results over Linked Data, while keeping the overhead for querying low and providing a satisfying source ranking at no additional cost.