OpenRaiser/Intern-Atlas huggingface dataset:
Learning associative markov networks
Authors: Benjamin Taskar, Vassil Chatalbashev, Daphne Koller
Venue: Conference ICML 2004
Year: 2004

Markov networks are extensively used to model complex sequential, spatial, and relational interactions in fields as diverse as image processing, natural language analysis, and bioinformatics. However, inference and learning in general Markov networks is intractable. In this paper, we focus on learning a large subclass of such models (called associative Markov networks) that are tractable or closely approximable. This subclass contains networks of discrete variables with K labels each and clique potentials that favor the same labels for all variables in the clique. Such networks capture the "guilt by association" pattern of reasoning present in many domains, in which connected ("associated") variables tend to have the same label. Our approach exploits a linear programming relaxation for the task of finding the best joint assignment in such networks, which provides an approximate quadratic program (QP) for the problem of learning a margin-maximizing Markov network. We show that for associative Markov network over binary-valued variables, this approximate QP is guaranteed to return an optimal parameterization for Markov networks of arbitrary topology. For the nonbinary case, optimality is not guaranteed, but the relaxation produces good solutions in practice. Experimental results with hypertext and newswire classification show significant advantages over standard approaches.
A Curve Evolution Approach for Image Segmentation Using Adaptive Flows
Authors: Haihua Feng, David A. Castañón, William Clement Karl
Venue: Conference ICCV 2001
Year: 2001

In this paper, we develop a new active contour model for image segmentation using adaptive flows. This active contour model can be derived from minimizing a limiting form of the Mumford-Shah functional, where the segmented image is assumed to consist of piecewise constant regions. This paper is an extension of an active contour model developed by Chan-Vese. The segmentation method proposed in this paper adaptively estimates mean intensities for each separated region and uses a single curve to capture multiple regions with different intensities. The class of imagery that our new active model can handle is greater than the bimodal images. In particular, our method segments images with an arbitrary number of intensity levels and separated regions while avoiding the complexity of solving a full Mumford-Shah problem. The adaptive flow developed in this paper is easily formulated and solved using level set methods. We illustrate the performance of our segmentation methods on images generated by different modalities.
Conformal deskewing of non-planar documents
Authors: Michael S. Brown, Charles J. Pisula
Venue: Conference CVPR 2005
Year: 2005

This paper presents an approach that uses conformal mapping to parameterize a document's 3D shape to a 2D plane. Using this conformal parametrization, a restorative mapping between an image of the distorted document and a "flattened" representation of the document can be computed and used to deskew the image. Our experiments show that arbitrarily distorted documents can be restored to within a single pixel of their true planar format. In addition, surface points can be constrained to map to specified locations in the restored 2D plane.
Direct method for reconstructing shape from shading
Authors: Paul Dupuis, John Oliensis
Venue: Conference CVPR 1992
Year: 1992

An approach to shape-from-shading that is based on a connection with a calculus of variations/optimal control problem is proposed. An explicit representation corresponding to a shaded image is given for the surface; uniqueness of the surface (under suitable conditions) is an immediate consequence. The approach leads naturally to an algorithm for shape reconstruction that is simple, fast, provably convergent (in many cases, provably convergent to the correct solution), and does not require regularization. Given a continuous image, the algorithm can be proved to converge to the continuous surface solution as the image sampling frequency is taken to infinity. Experimental results are presented for synthetic and real images.< <ETX xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">></ETX>
Geometric and photometric restoration of distorted documents
Authors: Mingxuan Sun 0001, Ruigang Yang, Yun Lin 0011, George V. Landon, W. Brent Seales, Michael S. Brown
Venue: Conference ICCV 2005
Year: 2005

We present a system to restore the 2D content printed on distorted documents. Our system works by acquiring a 3D scan of the document's surface together with a high-resolution image. Using the 3D surface information and the 2D image, we can ameliorate unwanted surface distortion and effects from non-uniform illumination. Our system can process arbitrary geometric distortions, not requiring any pre-assumed parametric models for the document's geometry. The illumination correction uses the 3D shape to distinguish content edges from illumination edges to recover the 2D content's reflectance image while making no assumptions about light sources and their positions. Results are shown for real objects, demonstrating a complete framework capable of restoring geometric and photometric artifacts on distorted documents
Constructing virtual documents for ontology matching
Authors: Yuzhong Qu, Wei Hu, Gong Cheng
Venue: Conference WWW 2006
Year: 2006

On the investigation of linguistic techniques used in ontology matching, we propose a new idea of virtual documents to pursue a cost-effective approach to linguistic matching in this paper. Basically, as a collection of weighted words, the virtual document of a URIref declared in an ontology contains not only the local descriptions but also the neighboring information to reflect the intended meaning of the URIref. Document similarity can be computed by traditional vector space techniques, and then be used in the similarity-based approaches to ontology matching. In particular, the RDF graph structure is exploited to define the description formulations and the neighboring operations. Experimental results show that linguistic matching based on the virtual documents is dominant in average F-Measure as compared to other three approaches. It is also demonstrated by our experiments that the virtual documents approach is cost-effective as compared to other linguistic matching approaches.
A large-scale evaluation and analysis of personalized search strategies
Authors: Zhicheng Dou, Ruihua Song, Ji-Rong Wen
Venue: Conference WWW 2007
Year: 2007

Although personalized search has been proposed for many years and many personalization strategies have been investigated, it is still unclear whether personalization is consistently effective on different queries for different users, and under different search contexts. In this paper, we study this problem and get some preliminary conclusions. We present a large-scale evaluation framework for personalized search based on query logs, and then evaluate five personalized search strategies (including two click-based and three profile-based ones) using 12-day MSN query logs. By analyzing the results, we reveal that personalized search has significant improvement over common web search on some queries but it also has little effect on other queries (e.g., queries with small click entropy). It even harms search accuracy under some situations. Furthermore, we show that straightforward click-based personalization strategies perform consistently and considerably well, while profile-based ones are unstable in our experiments. We also reveal that both long-term and short-term contexts are very important in improving search performance for profile-based personalized search strategies.
Better than the real thing? iterative pseudo-query processing using cluster-based language models
Authors: Oren Kurland, Lillian Lee, Carmel Domshlak
Venue: Conference SIGIR 2005
Year: 2005

We present a novel approach to pseudo-feedback-based ad hoc retrieval that uses language models induced from both documents and clusters. First, we treat the pseudo-feedback documents produced in response to the original query as a set of pseudo-query that themselves can serve as input to the retrieval process. Observing that the documents returned in response to the pseudo-query can then act as pseudo-query for subsequent rounds, we arrive at a formulation of pseudo-query-based retrieval as an iterative process. Experiments show that several concrete instantiations of this idea, when applied in conjunction with techniques designed to heighten precision, yield performance results rivaling those of a number of previously-proposed algorithms, including the standard language-modeling approach. The use of cluster-based language models is a key contributing factor to our algorithms' success.
Analyses of multiple evidence combination
Authors: Jong-Hak Lee
Venue: Conference SIGIR 1997
Year: 1997

Recent work suggests that significant improvements in retrieval performance can be achieved by combining multiple representations of an information need.
Exploiting hierarchical relationships in conceptual search
Authors: Devanand Ravindran, Susan Gauch
Venue: Conference CIKM 2004
Year: 2004

As the number of available Web pages grows, users experience increasing difficulty finding documents relevant to their interests. One of the underlying reasons for this is that most search engines find matches based on keywords, regardless of their meanings. To provide the user with more useful information, we need a system that disambiguates queries by including information about the user&apos;s conceptual framework. This is the goal of KeyConcept, a conceptual search engine. During indexing, KeyConcept classifies documents into concepts selected from a manuallyconstructed concept hierarchy. During retrieval, KeyConcept ranks documents based on a combination of keyword and conceptual similarity. This paper describes the system architecture and discusses the results of experiments that evaluate the effect of exploiting the hierarchical relationships between concepts during retrieval. Our results confirm that conceptual match significantly improves the precision of the search results over keyword match alone. In addition, the use of the concept hierarchy to prune irrelevant search results also significantly increases precision. Finally, we show that the two used together, conceptual search and pruning, significantly outperforms either used alone.
Optimal auction design for agents with hard valuation problems
Authors: David C. Parkes
Venue: Conference IJCAI 1999
Year: 1999

As traditional commerce moves on-line more business transactions will be mediated by software agents, and the ability of agent-mediated electronic marketplaces to efficiently allocate resources will be highly dependent on the complexity of the decision problems that agents face; determined in part by the structure of the marketplace, resource characteristics, and the nature of agents' local problems. We compare auction performance for agents that have hard local problems, and uncertain values for goods. Perhaps an agent must solve a hard optimization problem to value a good, or interact with a busy and expensive human expert. Although auction design cannot simplify the valuation problem itself, we show that good auction design can simplify meta-deliberation - providing incentives for the "right" agents to deliberate for the "right" amount of time. Empirical results for a particular cost-benefit model of deliberation show that an ascending-price auction will often support higher revenue and efficiency than other auction designs. The price provides agents with useful information about the value that other agents hold for the good.
Scalable collaborative filtering using cluster-based smoothing
Authors: Gui-Rong Xue, Chenxi Lin, Qiang Yang, Wensi Xi, Hua-Jun Zeng, Yong Yu, Zheng Chen
Venue: Conference SIGIR 2005
Year: 2005

Memory-based approaches for collaborative filtering identify the similarity between two users by comparing their ratings on a set of items. In the past, the memory-based approach has been shown to suffer from two fundamental problems: data sparsity and difficulty in scalability. Alternatively, the model-based approach has been proposed to alleviate these problems, but this approach tends to limit the range of users. In this paper, we present a novel approach that combines the advantages of these two approaches by introducing a smoothing-based method. In our approach, clusters generated from the training data provide the basis for data smoothing and neighborhood selection. As a result, we provide higher accuracy as well as increased efficiency in recommendations. Empirical studies on two datasets (EachMovie and MovieLens) show that our new proposed approach consistently outperforms other state-of-art collaborative filtering algorithms.
Good abandonment in mobile and pc internet search
Authors: Jane Li, Scott B. Huffman, Akihito Tokuda
Venue: Conference SIGIR 2009
Year: 2009

Query abandonment by search engine users is generally considered to be a negative signal. In this paper, we explore the concept of good abandonment. We define a good abandonment as an abandoned query for which the user's information need was successfully addressed by the search results page, with no need to click on a result or refine the query. We present an analysis of abandoned internet search queries across two modalities (PC and mobile) in three locales. The goal is to approximate the prevalence of good abandonment, and to identify types of information needs that may lead to good abandonment, across different locales and modalities. Our study has three key findings: First, queries potentially indicating good abandonment make up a significant portion of all abandoned queries. Second, the good abandonment rate from mobile search is significantly higher than that from PC search, across all locales tested. Third, classified by type of information need, the major classes of good abandonment vary dramatically by both locale and modality. Our findings imply that it is a mistake to uniformly consider query abandonment as a negative signal. Further, there is a potential opportunity for search engines to drive additional good abandonment, especially for mobile search users, by improving search features and result snippets.
Inferring search behaviors using partially observable Markov (POM) model
Authors: Kuansan Wang, Nikolas Gloy, Xiaolong Li
Venue: Conference WSDM 2010
Year: 2010

This article describes an application of the partially observable Markov (POM) model to the analysis of a large scale commercial web search log. Mathematically, POM is a variant of the hidden Markov model in which all the hidden state transitions do not necessarily emit observable events. This property of POM is used to model, as the hidden process, a common search behavior that users would read and skip search results, leaving no observable user actions to record in the search logs. The Markov nature of the model further lends support to cope with the facts that a single observed sequence can be probabilistically associated with many hidden sequences that have variable lengths, and the search results can be read in various temporal orders that are not necessarily reflected in the observed sequence of user actions. To tackle the implementation challenges accompanying the flexibility and analytic powers of POM, we introduce segmental Viterbi algorithm based on segmental decoding and Viterbi training to train the POM model parameters and apply them to uncover hidden processes from the search logs. To validate the model, the latent variables modeling the browsing patterns on the search result page are compared with the experimental data of the eye tracking stu-dies. The close agreements suggest that the search logs do contain rich information of user behaviors in browsing the search result page even though they are not directly observable, and that using POM to understand these sophisticated search behaviors is a promising approach.
Pskip: estimating relevance ranking quality from web search clickthrough data
Authors: Kuansan Wang, Toby Walker, Zijian Zheng
Venue: Conference KDD 2009
Year: 2009

In this article, we report our efforts in mining the information encoded as clickthrough data in the server logs to evaluate and monitor the relevance ranking quality of a commercial web search engine. We describe a metric called pSkip that aims to quantify the ranking quality by estimating the probability of users encountering non relevant results that cost them the efforts to read and skip. A search engine with a lower pSkip is regarded as having a better ranking quality. A key design goal of pSkip is to integrate the findings from two sets of user studies that utilize eye-tracking devices to track users' browsing patterns on the search result pages, and that use specially instrumented browsers to actively solicit users' explicit judgments on their search activities. We present the derivation of the maximum likelihood estimation of pSkip and demonstrate its efficacy in describing the user study data. The mathematical properties of pSkip are further analyzed and compared with several objective metrics as well as the cumulated gain method that uses subjective judgments. Experimental data show that pSkip can measure aspects of the search quality that these existing metrics are not designed or fail to address, such as identifying the real search intents expressed in the ambiguous queries. Although effective and superior in many ways, we also report a series of experiments that show pSkip may be influenced by system issues that are not directly related to relevance ranking, suggesting that measurements complementary to pSkip are still needed in order to form a holistic and accurate characterization of the ranking quality.
Dualminer: A dual-pruning algorithm for itemsets with constraints
Authors: Cristian Bucila, Johannes Gehrke, Daniel Kifer, Walker M. White
Venue: Conference KDD 2002
Year: 2002

Constraint-based mining of itemsets for questions such as "find all frequent itemsets where the total price is at least $50" has received much attention recently. Two classes of constraints, monotone and antimonotone, have been identified as very useful. There are algorithms that efficiently take advantage of either one of these two classes, but no previous algorithms can efficiently handle both types of constraints simultaneously. In this paper, we present the first algorithm (called DualMiner) that uses both monotone and antimonotone constraints to prune its search space. We complement a theoretical analysis and proof of correctness of DualMiner with an experimental study that shows the efficacy of DualMiner compared to previous work.
Correlated itemset mining in ROC space: A constraint programming approach
Authors: Siegfried Nijssen, Tias Guns, Luc De Raedt
Venue: Conference KDD 2009
Year: 2009

Correlated or discriminative pattern mining is concerned with finding the highest scoring patterns w.r.t. a correlation measure (such as information gain). By reinterpreting correlation measures in ROC space and formulating correlated itemset mining as a constraint programming problem, we obtain new theoretical insights with practical benefits. More specifically, we contribute 1) an improved bound for correlated itemset miners, 2) a novel iterative pruning algorithm to exploit the bound, and 3) an adaptation of this algorithm to mine all itemsets on the convex hull in ROC space. The algorithm does not depend on a minimal frequency threshold and is shown to outperform several alternative approaches by orders of magnitude, both in runtime and in memory requirements.
Implicit color segmentation features for pedestrian and object detection
Authors: Patrick Ott, Mark Everingham
Venue: Conference ICCV 2009
Year: 2009

We investigate the problem of pedestrian detection in still images. Sliding window classifiers, notably using the Histogram-of-Gradient (HOG) features proposed by Dalal and Triggs are the state-of-the-art for this task, and we base our method on this approach. We propose a novel feature extraction scheme which computes implicit `soft segmentations' of image regions into foreground/background. The method yields stronger object/background edges than gray-scale gradient alone, suppresses textural and shading variations, and captures local coherence of object appearance. The main contributions of our work are: (i) incorporation of segmentation cues into object detection; (ii) integration with classifier learning cf. a post-processing filter; (iii) high computational efficiency. We report results on the INRIA person detection dataset, achieving state-of-the-art results considerably exceeding those of the original HOG detector. Preliminary results for generic object detection on the PASCAL VOC2006 dataset also show substantial improvements in accuracy.
Generating hierarchical summaries for web searches
Authors: Dawn J. Lawrie, W. Bruce Croft
Venue: Conference SIGIR 2003
Year: 2003

Hierarchies provide a means of organizing, summarizing and accessing information. We describe a method for automatically generating hierarchies from small collections of text, and then apply this technique to summarizing the documents retrieved by a search engine.
Statistical and computational analysis of locality preserving projection
Authors: Xiaofei He 0001, Deng Cai 0001, Wanli Min
Venue: Conference ICML 2005
Year: 2005

Recently, several manifold learning algorithms have been proposed, such as ISOMAP (Tenenbaum et al., 2000), Locally Linear Embedding (Roweis & Saul, 2000), Laplacian Eigenmap (Belkin & Niyogi, 2001), Locality Preserving Projection (LPP) (He & Niyogi, 2003), etc. All of them aim at discovering the meaningful low dimensional structure of the data space. In this paper, we present a statistical analysis of the LPP algorithm. Different from Principal Component Analysis (PCA) which obtains a subspace spanned by the largest eigenvectors of the global covariance matrix, we show that LPP obtains a subspace spanned by the smallest eigenvectors of the local covariance matrix. We applied PCA and LPP to real world document clustering task. Experimental results show that the performance can be significantly improved in the subspace, and especially LPP works much better than PCA.
Learning Spatially Localized Parts-Based Representation
Authors: Stan Z. Li, Xinwen Hou, HongJiang Zhang, QianSheng Cheng
Venue: Conference CVPR 2001
Year: 2001

In this paper, we propose a novel method, called local non-negative matrix factorization (LNMF), for learning spatially localized, parts-based subspace representation of visual patterns. An objective function is defined to impose a localization constraint, in addition to the non-negativity constraint in the standard NMF. This gives a set of bases which not only allows a non-subtractive (part-based) representation of images but also manifests localized features. An algorithm is presented for the learning of such basic components. Experimental results are presented to compare LNMF with the NMF and PCA methods for face representation and recognition, which demonstrates advantages of LNMF.
MRF optimization via dual decomposition: Message-passing revisited
Authors: Nikos Komodakis, Nikos Paragios, Georgios Tziritas
Venue: Conference ICCV 2007
Year: 2007

A new message-passing scheme for MRF optimization is proposed in this paper. This scheme inherits better theoretical properties than all other state-of-the-art message passing methods and in practice performs equally well/outperforms them. It is based on the very powerful technique of Dual Decomposition [1] and leads to an elegant and general framework for understanding/designing message-passing algorithms that can provide new insights into existing techniques. Promising experimental results and comparisons with the state of the art demonstrate the extreme theoretical and practical potentials of our approach.