OpenRaiser/Intern-Atlas huggingface dataset:
The Self-Aware Matching Measure for Stereo
Authors: Philippos Mordohai
Venue: Conference ICCV 2009
Year: 2009

We revisit stereo matching functions, a topic that is considered well understood, from a different angle. Our goal is to discover a transformation that operates on the cost or similarity measures between pixels in binocular stereo. This transformation should produce a new matching curve that results in higher matching accuracy. The desired transformation must have no additional parameters over those of the original matching function and must result in a new matching function that can be used by existing local, global and semi-local stereo algorithms without having to modify the algorithms. We propose a transformation that meets these requirements, taking advantage of information derived from matching the input images against themselves. We analyze the behavior of this transformation, which we call Self-Aware Matching Measure (SAMM), on a diverse set of experiments on data with ground truth. Our results show that the SAMM improves the performance of dense and semi-dense stereo. Moreover, as opposed to the current state of the art, it does not require distinctiveness to match pixels reliably.
Directed Acyclic Graph Factorization Machines for CTR Prediction via Knowledge Distillation
Authors: Zhen Tian, Ting Bai, Zibin Zhang, Zhiyuan Xu, Kangyi Lin, Ji-Rong Wen, Wayne Xin Zhao
Venue: Conference WSDM 2023
Year: 2023

With the growth of high-dimensional sparse data in web-scale recommender systems, the computational cost to learn high-order feature interaction in CTR prediction task largely increases, which limits the use of high-order interaction models in real industrial applications. Some recent knowledge distillation based methods transfer knowledge from complex teacher models to shallow student models for accelerating the online model inference. However, they suffer from the degradation of model accuracy in knowledge distillation process. It is challenging to balance the efficiency and effectiveness of the shallow student models. To address this problem, we propose a Directed Acyclic Graph Factorization Machine (KD-DAGFM) to learn the high-order feature interactions from existing complex interaction models for CTR prediction via Knowledge Distillation. The proposed lightweight student model DAGFM can learn arbitrary explicit feature interactions from teacher networks, which achieves approximately lossless performance and is proved by a dynamic programming algorithm. Besides, an improved general model KD-DAGFM+ is shown to be effective in distilling both explicit and implicit feature interactions from any complex teacher model. Extensive experiments are conducted on four real-world datasets, including a large-scale industrial dataset from WeChat platform with billions of feature dimensions. KD-DAGFM achieves the best performance with less than 21.5% FLOPs of the state-of-the-art method on both online and offline experiments, showing the superiority of DAGFM to deal with the industrial scale data in CTR prediction task.
Constraint relaxation in approximate linear programs
Authors: Marek Petrik, Shlomo Zilberstein
Venue: Conference ICML 2009
Year: 2009

Approximate Linear Programming (ALP) is a reinforcement learning technique with nice theoretical properties, but it often performs poorly in practice. We identify some reasons for the poor quality of ALP solutions in problems where the approximation induces virtual loops. We then introduce two methods for improving solution quality. One method rolls out selected constraints of the ALP, guided by the dual information. The second method is a relaxation of the ALP, based on external penalty methods. The latter method is applicable in domains in which rolling out constraints is impractical. Both approaches show promising empirical results for simple benchmark problems as well as for a realistic blood inventory management problem.
Boosting with structural sparsity
Authors: John C. Duchi, Yoram Singer
Venue: Conference ICML 2009
Year: 2009

We derive generalizations of AdaBoost and related gradient-based coordinate descent methods that incorporate sparsity-promoting penalties for the norm of the predictor that is being learned. The end result is a family of coordinate descent algorithms that integrate forward feature induction and back-pruning through regularization and give an automatic stopping criterion for feature induction. We study penalties based on the l1, l2, and l∞ norms of the predictor and introduce mixed-norm penalties that build upon the initial penalties. The mixed-norm regularizers facilitate structural sparsity in parameter space, which is a useful property in multiclass prediction and other related tasks. We report empirical results that demonstrate the power of our approach in building accurate and structurally sparse models.
Gradient lasso for feature selection
Authors: Yongdai Kim, Jinseog Kim
Venue: Conference ICML 2004
Year: 2004

LASSO (Least Absolute Shrinkage and Selection Operator) is a useful tool to achieve the shrinkage and variable selection simultaneously. Since LASSO uses the L1 penalty, the optimization should rely on the quadratic program (QP) or general non-linear program which is known to be computational intensive. In this paper, we propose a gradient descent algorithm for LASSO. Even though the final result is slightly less accurate, the proposed algorithm is computationally simpler than QP or non-linear program, and so can be applied to large size problems. We provide the convergence rate of the algorithm, and illustrate it with simulated models as well as real data sets.
Empirical bayes screening for multi-item associations
Authors: William DuMouchel, Daryl Pregibon
Venue: Conference KDD 2001
Year: 2001

This paper considers the framework of the so-called &quot;market basket problem&quot;, in which a database of transactions is mined for the occurrence of unusually frequent item sets. In our case, &quot;unusually frequent&quot; involves estimates of the frequency of each item set divided by a baseline frequency computed as if items occurred independently. The focus is on obtaining reliable estimates of this measure of interestingness for all item sets, even item sets with relatively low frequencies. For example, in a medical database of patient histories, unusual item sets including the item &quot;patient death&quot; (or other serious adverse event) might hopefully be flagged with as few as 5 or 10 occurrences of the item set, it being unacceptable to require that item sets occur in as many as 0.1% of millions of patient reports before the data mining algorithm detects a signal. Similar considerations apply in fraud detection applications. Thus we abandon the requirement that interesting item sets must contain a re...
N-gram over context
Authors: Noriaki Kawamae
Venue: Conference WWW 2016
Year: 2016

Our proposal, $N$-gram over Context (NOC), is a nonparametric topic model that aims to help our understanding of a given corpus, and be applied to many text mining applications. Like other topic models, NOC represents each document as a mixture of topics and generates each word from one topic. Unlike these models, NOC focuses on both a topic structure as an internal linguistic structure, and N-gram as an external linguistic structure. To improve the quality of topic specific N-grams, NOC reveals a tree of topics that captures the semantic relationship between topics from a given corpus as context, and forms $N$-gram by offering power-law distributions for word frequencies on this topic tree. To gain both these linguistic structures efficiently, NOC learns them from a given corpus in a unified manner. By accessing this entire tree at the word level in the generative process of each document, NOC enables each document to maintain a thematic coherence and form $N$-grams over context. We develop a parallelizable inference algorithm, D-NOC, to support large data sets. Experiments on review articles/papers/tweet show that NOC is useful as a generative model to discover both the topic structure and the corresponding N-grams, and well complements human experts and domain specific knowledge. D-NOC can process large data sets while preserving full generative model performance, by the help of an open-source distributed machine learning framework.
Classifying trending topics: a typology of conversation triggers on twitter
Authors: Arkaitz Zubiaga, Damiano Spina, Víctor Fresno, Raquel Martínez-Unanue
Venue: Conference CIKM 2011
Year: 2011

Twitter summarizes the great deal of messages posted by users in the form of trending topics that reflect the top conversations being discussed at a given moment. These trending topics tend to be connected to current affairs. Different happenings can give rise to the emergence of these trending topics. For instance, a sports event broadcasted on TV, or a viral meme introduced by a community of users. Detecting the type of origin can facilitate information filtering, enhance real-time data processing, and improve user experience. In this paper, we introduce a typology to categorize the triggers that leverage trending topics: news, current events, memes, and commemoratives. We define a set of straightforward language-independent features that rely on the social spread of the trends to discriminate among those types of trending topics. Our method provides an efficient way to immediately and accurately categorize trending topics without need of external data, outperforming a content-based approach.
Gradient boosting for kernelized output spaces
Authors: Pierre Geurts, Louis Wehenkel, Florence d&apos, Alché-Buc
Venue: Conference ICML 2007
Year: 2007

A general framework is proposed for gradient boosting in supervised learning problems where the loss function is defined using a kernel over the output space. It extends boosting in a principled way to complex output spaces (images, text, graphs etc.) and can be applied to a general class of base learners working in kernelized output spaces. Empirical results are provided on three problems: a regression problem, an image completion task and a graph prediction problem. In these experiments, the framework is combined with tree-based base learners, which have interesting algorithmic properties. The results show that gradient boosting significantly improves these base learners and provides competitive results with other tree-based ensemble methods based on randomization.
Topic models with power-law using pitman-yor process
Authors: Issei Sato, Hiroshi Nakagawa
Venue: Conference KDD 2010
Year: 2010

One important approach for knowledge discovery and data mining is to estimate unobserved variables because latent variables can indicate hidden specific properties of observed data. The latent factor model assumes that each item in a record has a latent factor; the co-occurrence of items can then be modeled by latent factors. In document modeling, a record indicates a document represented as a "bag of words," meaning that the order of words is ignored, an item indicates a word and a latent factor indicates a topic. Latent Dirichlet allocation (LDA) is a widely used Bayesian topic model applying the Dirichlet distribution over the latent topic distribution of a document having multiple topics. LDA assumes that latent topics, i.e., discrete latent variables, are distributed according to a multinomial distribution whose parameters are generated from the Dirichlet distribution. LDA also models a word distribution by using a multinomial distribution whose parameters follows the Dirichlet distribution. This Dirichlet-multinomial setting, however, cannot capture the power-law phenomenon of a word distribution, which is known as Zipf's law in linguistics. We therefore propose a novel topic model using the Pitman-Yor(PY) process, called the PY topic model. The PY topic model captures two properties of a document; a power-law word distribution and the presence of multiple topics. In an experiment using real data, this model outperformed LDA in document modeling in terms of perplexity.
An efficient subgraph GNN with provable substructure counting power
Authors: Zuoyu Yan, Junru Zhou, Liangcai Gao, Zhi Tang 0001, Muhan Zhang
Venue: Conference KDD 2024
Year: 2024

We investigate the enhancement of graph neural networks' (GNNs) representation power through their ability in substructure counting. Recent advances have seen the adoption of subgraph GNNs, which partition an input graph into numerous subgraphs, subsequently applying GNNs to each to augment the graph's overall representation. Despite their ability to identify various substructures, subgraph GNNs are hindered by significant computational and memory costs. In this paper, we tackle a critical question: Is it possible for GNNs to count substructures both \textbf{efficiently} and \textbf{provably}? Our approach begins with a theoretical demonstration that the distance to rooted nodes in subgraphs is key to boosting the counting power of subgraph GNNs. To avoid the need for repetitively applying GNN across all subgraphs, we introduce precomputed structural embeddings that encapsulate this crucial distance information. Experiments validate that our proposed model retains the counting power of subgraph GNNs while achieving significantly faster performance.
DL-learner structured machine learning on semantic web data
Authors: Lorenz Bühmann, Jens Lehmann, Patrick Westphal, Simon Bin
Venue: Conference WWW 2018
Year: 2018

The following paper is an extended summary of the journal paper "DL-Learner A framework for inductive learning on the Semantic Web". In this system paper, we describe the DL-Learner framework. It is beneficial in various data and schema analytic tasks with applications in different standard machine learning scenarios, e.g. life sciences, as well as Semantic Web specific applications such as ontology learning and enrichment. Since its creation in 2007, it has become the main OWL and RDF-based software framework for supervised structured machine learning and includes several algorithm implementations, usage examples and has applications building on top of the framework.
Interpolation-based Q-learning
Authors: Csaba Szepesvári, William D. Smart
Venue: Conference ICML 2004
Year: 2004

We consider a variant of Q-learning in continuous state spaces under the total expected discounted cost criterion combined with local function approximation methods. Provided that the function approximator satisfies certain interpolation properties, the resulting algorithm is shown to converge with probability one. The limit function is shown to satisfy a fixed point equation of the Bellman type, where the fixed point operator depends on the stationary distribution of the exploration policy and the function approximation method. The basic algorithm is extended in several ways. In particular, a variant of the algorithm is obtained that is shown to converge in probability to the optimal Q function. Preliminary computer simulations are presented that confirm the validity of the approach.
Distribution Kernels Based on Moments of Counts
Authors: Corinna Cortes, Mehryar Mohri
Venue: Conference ICML 2004
Year: 2004

Many applications in text and speech processing require the analysis of distributions of variable-length sequences. We recently introduced a general kernel framework, rational kernels, to extend kernel methods to the analysis of such variable-length sequences or more generally weighted automata. These kernels are efficient to compute and have been successfully used in applications such as spoken-dialog classification using Support Vector Machines.However, the rational kernels previously introduced do not fully encompass distributions over alternate sequences. Prior similarity measures between two weighted automata are based only on the expected counts of co-occurring subsequences and ignore similarities (or dissimilarities) in higher order moments of the distributions of these counts.In this paper, we introduce a new family of rational kernels, moment kernels, that precisely exploit this additional information. These kernels are distribution kernels based on moments of counts of strings. We describe efficient algorithms to compute moment kernels and apply them to several difficult spoken-dialog classification tasks. Our experiments show that using the second moment of the counts of n-gram sequences consistently improves the classification accuracy in these tasks.
Webpage understanding: an integrated approach
Authors: Jun Zhu, Bo Zhang, Zaiqing Nie, Ji-Rong Wen, Hsiao-Wuen Hon
Venue: Conference KDD 2007
Year: 2007

Recent work has shown the effectiveness of leveraging layout and tag-tree structure for segmenting webpages and labeling HTML elements. However, how to effectively segment and label the text contents inside HTML elements is still an open problem. Since many text contents on a webpage are often text fragments and not strictly grammatical, traditional natural language processing techniques, that typically expect grammatical sentences, are no longer directly applicable. In this paper, we examine how to use layout and tag-tree structure in a principled way to help understand text contents on webpages. We propose to segment and label the page structure and the text content of a webpage in a joint discriminative probabilistic model. In this model, semantic labels of page structure can be leveraged to help text content understanding, and semantic labels ofthe text phrases can be used in page structure understanding tasks such as data record detection. Thus, integration of both page structure and text content understanding leads to an integrated solution of webpage understanding. Experimental results on research homepage extraction show the feasibility and promise of our approach.
On the relationship between description logic and predicate logic
Authors: Alexander Borgida
Venue: Conference CIKM 1994
Year: 1994

Description languages form the basis of several object-centered knowledge base management systems developed in recent years, including ones in industrial use. Originally used for conceptual modeling (to define views), DLs are seeing increased use as query languages for retrieving information. This paper, aimed at a general audience that includes database researchers, considers the relationship between the expressive power of DLs and that of query languages based on Predicate Calculus.
A mixed-state condensation tracker with automatic model-switching
Authors: Michael Isard, Andrew Blake 0001
Venue: Conference ICCV 1998
Year: 1998

There is considerable interest in the computer vision community in representing and modelling motion. Motion models are used as predictors to increase the robustness and accuracy of visual trackers, and as classifiers for gesture recognition. This paper presents a significant development of random sampling methods to allow automatic switching between multiple motion models as a natural extension of the tracking process. The Bayesian mixed-state framework is described in its generality, and the example of a bouncing ball is used to demonstrate that a mixed-state model can significantly improve tracking performance in heavy clutter. The relevance of the approach to the problem of gesture recognition is then investigated using a tracker which is able to follow the natural drawing action of a hand holding a pen, and switches state according to the hand's motion.
Vision-based hand modeling and tracking for virtual teleconferencing and telecollaboration
Authors: James J. Kuch, Thomas S. Huang
Venue: Conference ICCV 1995
Year: 1995

The authors present a hand model that simultaneously satisfies both the synthesis and analysis requirements of model based compression. The model can be fitted to any person's hand and can be done using a single camera. Once the model is fitted to a real human hand, it is then used in several tracking scenarios in order to verify its effectiveness. With successful tracking achieved, the model is ready to be incorporated into a virtual environment or model based compression scheme such as sign language communication over telephone lines or virtual teleconferences over computer networks at very low bit rates and at very high image quality.< <ETX xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">></ETX>
Capturing articulated human hand motion: A divide-and-conquer approach
Authors: Ying Wu 0001, Thomas S. Huang
Venue: Conference ICCV 1999
Year: 1999

The use of the human hand as a natural interface device serves as a motivating force for research in the modeling, analysis and capture of the motion of an articulated hand. Model-based hand motion capture can be formulated as a large nonlinear programming problem, but this approach is plagued by local minima. An alternative way is to use analysis-by-synthesis by searching a huge space, but the results are rough and the computation expensive. In this paper, articulated hand motion is decoupled, a new two-step iterative model-based algorithm is proposed to capture articulated human hand motion, and a proof of convergence of this iterative algorithm is also given. In our proposed work, the decoupled global hand motion and local finger motion are parameterized by the 3D hand pose and the state of the hand respectively. Hand pose determination is formulated as a least-median-of-squares (LMS) problem rather than the nonrobust least-squares (LS) problem, so that 3D hand pose can be reliably calculated even if there are outliers. Local finger motion is formulated as an inverse kinematics problem. A genetic algorithm-based method is proposed to find a sub-optimal solution of the inverse kinematics effectively. Our algorithm and the LS-based algorithm are compared in several experiments. Both algorithms converge when local finger motion between consecutive frames is small. When large finger motion is present, the LS-based method fails, but our algorithm can still estimate the global and local finger motion well.
BL-WoLF: A framework for loss-bounded learnability in zero-sum games
Authors: Vincent Conitzer, Tuomas Sandholm
Venue: Conference ICML 2003
Year: 2003

We present BL-WoLF, a framework for learnability in repeated zero-sum games where the cost of learning is measured by the losses the learning agent accrues (rather than the number of rounds). The game is adversarially chosen from some family that the learner knows. The opponent knows the game and the learner's learning strategy. The learner tries to either not accrue losses, or to quickly learn about the game so as to avoid future losses (this is consistent with the Win or Learn Fast (WoLF) principle; BL stands for ``bounded loss''). Our framework allows for both probabilistic and approximate learning. The resultant notion of {\em BL-WoLF}-learnability can be applied to any class of games, and allows us to measure the inherent disadvantage to a player that does not know which game in the class it is in. We present {\em guaranteed BL-WoLF-learnability} results for families of games with deterministic payoffs and families of games with stochastic payoffs. We demonstrate that these families are {\em guaranteed approximately BL-WoLF-learnable} with lower cost. We then demonstrate families of games (both stochastic and deterministic) that are not guaranteed BL-WoLF-learnable. We show that those families, nevertheless, are {\em BL-WoLF-learnable}. To prove these results, we use a key lemma which we derive.