OpenRaiser/Intern-Atlas huggingface dataset:
Automated local regression discontinuity design discovery
Authors: William Herlands, Edward McFowland III, Andrew Gordon Wilson, Daniel B. Neill
Venue: Conference KDD 2018
Year: 2018

Inferring causal relationships in observational data is crucial for understanding scientific and social processes. We develop the first statistical machine learning approach for automatically discovering regression discontinuity designs (RDDs), a quasi-experimental setup often used in econometrics. Our method identifies interpretable, localized RDDs in arbitrary dimensional data and can seamlessly compute treatment effects without expert supervision. By applying the technique to a variety of synthetic and real datasets, we demonstrate robust performance under adverse conditions including unobserved variables, substantial noise, and model
Intrinsic mean shift for clustering on stiefel and grassmann manifolds
Authors: Hasan Ertan Çetingül, René Vidal
Venue: Conference CVPR 2009
Year: 2009

The mean shift algorithm, which is a nonparametric density estimator for detecting the modes of a distribution on a Euclidean space, was recently extended to operate on analytic manifolds. The extension is extrinsic in the sense that the inherent optimization is performed on the tangent spaces of these manifolds. This approach specifically requires the use of the exponential map at each iteration. This paper presents an alternative mean shift formulation, which performs the iterative optimization “on” the manifold of interest and intrinsically locates the modes via consecutive evaluations of a mapping. In particular, these evaluations constitute a modified gradient ascent scheme that avoids the computation of the exponential maps for Stiefel and Grassmann manifolds. The performance of our algorithm is evaluated by conducting extensive comparative studies on synthetic data as well as experiments on object categorization and segmentation of multiple motions.
Sparse mixed linear regression with guarantees: Taming an intractable problem with invex relaxation
Authors: Adarsh Barik, Jean Honorio
Venue: Conference ICML 2022
Year: 2022

In this paper, we study the problem of sparse mixed linear regression on an unlabeled dataset that is generated from linear measurements from two different regression parameter vectors. Since the data is unlabeled, our task is not only to figure out a good approximation of the regression parameter vectors but also to label the dataset correctly. In its original form, this problem is NP-hard. The most popular algorithms to solve this problem (such as Expectation-Maximization) have a tendency to stuck at local minima. We provide a novel invex relaxation for this intractable problem which leads to a solution with provable theoretical guarantees. This relaxation enables exact recovery of data labels. Furthermore, we recover a close approximation of the regression parameter vectors which match the true parameter vectors in support and sign. Our formulation uses a carefully constructed primal dual witnesses framework for the invex problem. Furthermore, we show that the sample complexity of our method is only logarithmic in terms of the dimension of the regression parameter vectors.
On the hidden biases of policy mirror ascent in continuous action spaces
Authors: Amrit Singh Bedi, Souradip Chakraborty, Anjaly Parayil, Brian M. Sadler, Pratap Tokekar, Alec Koppel
Venue: Conference ICML 2022
Year: 2022

We focus on parameterized policy search for reinforcement learning over continuous action spaces. Typically, one assumes the score function associated with a policy is bounded, which fails to hold even for Gaussian policies. To properly address this issue, one must introduce an exploration tolerance parameter to quantify the region in which it is bounded. Doing so incurs a persistent bias that appears in the attenuation rate of the expected policy gradient norm, which is inversely proportional to the radius of the action space. To mitigate this hidden bias, heavy-tailed policy parameterizations may be used, which exhibit a bounded score function, but doing so can cause instability in algorithmic updates. To address these issues, in this work, we study the convergence of policy gradient algorithms under heavy-tailed parameterizations, which we propose to stabilize with a combination of mirror ascent-type updates and gradient tracking. Our main theoretical contribution is the establishment that this scheme converges with constant step and batch sizes, whereas prior works require these parameters to respectively shrink to null or grow to infinity. Experimentally, this scheme under a heavy-tailed policy parameterization yields improved reward accumulation across a variety of settings as compared with standard benchmarks.
Combining powerful local and global statistics for texture description
Authors: Yong Xu 0007, Si-Bin Huang, Hui Ji 0002, Cornelia Fermüller
Venue: Conference CVPR 2009
Year: 2009

A texture descriptor is proposed, which combines local highly discriminative features with the global statistics of fractal geometry to achieve high descriptive power, but also invariance to geometric and illumination transformations. As local measurements SIFT features are estimated densely at multiple window sizes and discretized. On each of the discretized measurements the fractal dimension is computed to obtain the so-called multifractal spectrum, which is invariant to geometric transformations and illumination changes. Finally to achieve robustness to scale changes, a multi-scale representation of the multifractal spectrum is developed using a framelet system, that is, a redundant tight wavelet frame system. Experiments on classification demonstrate that the descriptor outperforms existing methods on the UIUC as well as the UMD high-resolution dataset.
Semi-supervised random forests
Authors: Christian Leistner, Amir Saffari, Jakob Santner, Horst Bischof
Venue: Conference ICCV 2009
Year: 2009

Random Forests (RFs) have become commonplace in many computer vision applications. Their popularity is mainly driven by their high computational efficiency during both training and evaluation while still being able to achieve state-of-the-art accuracy. This work extends the usage of Random Forests to Semi-Supervised Learning (SSL) problems. We show that traditional decision trees are optimizing multi-class margin maximizing loss functions. From this intuition, we develop a novel multi-class margin definition for the unlabeled data, and an iterative deterministic annealing-style training algorithm maximizing both the multi-class margin of labeled and unlabeled samples. In particular, this allows us to use the predicted labels of the unlabeled data as additional optimization variables. Furthermore, we propose a control mechanism based on the out-of-bag error, which prevents the algorithm from degradation if the unlabeled data is not useful for the task. Our experiments demonstrate state-of-the-art semi-supervised learning performance in typical machine learning problems and constant improvement using unlabeled data for the Caltech-101 object categorization task.
Proximal regularization for online and batch learning
Authors: Chuong B. Do, Quoc V. Le, Chuan-Sheng Foo
Venue: Conference ICML 2009
Year: 2009

Many learning algorithms rely on the curvature (in particular, strong convexity) of regularized objective functions to provide good theoretical performance guarantees. In practice, the choice of regularization penalty that gives the best testing set performance may result in objective functions with little or even no curvature. In these cases, algorithms designed specifically for regularized objectives often either fail completely or require some modification that involves a substantial compromise in performance.
The Open Meeting: A Web-Based System for Conferencing and Collaboration
Authors: Roger Hurwitz, John C. Mallery
Venue: Conference WWW 1995
Year: 1995

An asynchronous collaboration system was developed for Vice President AL Gore's Open Meeting on the National Performance Review. The system supported a large online meeting with over 4000 participants and successfully achieved all its design goals. A theory for managing wide-area collaboration guided the implementation as it extended an earlier system developed to publish electronic documents. It provided users access over SMTP and HTTP to hypertext synthesized from an object database and structured with knowledge representation techniques, including a light-weight semantics based on argument connectives. The users participated in policy planning as they discussed, evaluated, and critiqued recommendations by linking their comments to points in the evolving policy hypertext. These policy conversations were structured according to a link grammar that constrained the types of comments which could be attached in specific discourse contexts. Persistent actions enforced constraints on man-machine tasks, such as moderation workflow. Timely delivery of newly moderated comments kept the conversation gain at a level comparable to tightly-focused mailing lists threading out from specific points in the hypertext. After reviewing the architecture and performance of the system in this Open Meeting, the paper closes with discussion of lessons learned and suggestions for future research.
Animat vision: Active vision in artificial animals
Authors: Demetri Terzopoulos, Tamer F. Rabie
Venue: Conference ICCV 1995
Year: 1995

We propose and demonstrate a new paradigm for active vision research that draws upon recent advances in the fields of artificial life and computer graphics. A software alternative to the prevailing hardware vision mindset, animat vision prescribes artificial animals, or animats, situated in physics-based virtual worlds as autonomous virtual robots possessing active perception systems. To be operative in its world, an animat must autonomously control its eyes and muscle-actuated body, applying computer vision algorithms to continuously analyze the retinal image streams acquired by its eyes in order to locomote purposefully through its world. We describe an initial animat vision implementation within lifelike artificial fishes inhabiting a physics-based, virtual marine world. Emulating the appearance, motion, and behavior of real fishes in their natural habitats, these animats are capable of spatially nonuniform retinal imaging, foveation, retinal image stabilization, color object recognition, and perceptually-guided navigation. These capabilities allow them to pursue moving targets such as fellow artificial fishes. Animat vision offers a fertile approach to the development, implementation, and evaluation of computational theories that profess sensorimotor competence for animal or robotic situated agents.< <ETX xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">></ETX>
Finding authorities and hubs from link structures on the world wide web
Authors: Allan Borodin, Gareth O. Roberts, Jeffrey S. Rosenthal, Panayiotis Tsaparas
Venue: Conference WWW 2001
Year: 2001

Recently, ther have been a number of algorH#-9 prC osed for analyzing hyperDCC link str5#TDso as todeterCDthe best &quot;authorODHUM for a given topic or quer . While such analysis is usually combined with content analysis, ther is a sense in which some algorUO-9 ar deemed to be&quot;mor balanced&quot; andother &quot;mor focused&quot;. WeunderDe a compar --C e study of hyperDTD link analysisalgor-CDCO Guided by some experD#C tal quer5CD we prD ose somefor-C crC5O r for evaluating and comparTlink analysisalgor-CUH5 Keywords link analysis, websear hing, hubs, author-9TD5 SALSA, KleinberMU algor9T#5 thrCHHE-9 Bayesian 1.
Approximate tree matching and shape similarity
Authors: Tyng-Luh Liu, Davi Geiger
Venue: Conference ICCV 1999
Year: 1999

We present a framework for 2D shape contour (silhouette) comparison that can account for stretchings, occlusions and region information. Topological changes due to the original 3D scenarios and articulations are also addressed. To compare the degree of similarity between any two shapes, our approach is to represent each shape contour with a free tree structure derived from a shape axis (SA) model, which we have recently proposed. We then use a tree matching scheme to find the best approximate match and the matching cost. To deal with articulations, stretchings and occlusions, three local tree matching operations, merge, cut, and merge-and-cut, are introduced to yield optimally approximate matches, which can accommodate not only one-to-one but many-to-many mappings. The optimization process gives guaranteed globally optimal match efficiently. Experimental results on a variety of shape contours are provided.
Turning CARTwheels: An Alternating Algorithm for Mining Redescriptions
Authors: Naren Ramakrishnan, Deept Kumar, Bud Mishra, Malcolm Potts, Richard F. Helm
Venue: Conference KDD 2004
Year: 2004

We present an unusual algorithm involving classification trees---CARTwheels---where two trees are grown in opposite directions so that they are joined at their leaves. This approach finds application in a new data mining task we formulate, called redescription mining. A redescription is a shift-of-vocabulary, or a different way of communicating information about a given subset of data; the goal of redescription mining is to find subsets of data that afford multiple descriptions. We highlight the importance of this problem in domains such as bioinformatics, which exhibit an underlying richness and diversity of data descriptors (e.g., genes can be studied in a variety of ways). CARTwheels exploits the duality between class partitions and path partitions in an induced classification tree to model and mine redescriptions. It helps integrate multiple forms of characterizing datasets, situates the knowledge gained from one dataset in the context of others, and harnesses high-level abstractions for uncovering cryptic and subtle features of data. Algorithm design decisions, implementation details, and experimental results are presented.
Mixed-initiative, multi-source information assistants
Authors: Craig A. Knoblock, Steven Minton, José Luis Ambite, Maria Muslea, Jean Oh, Martin Frank
Venue: Conference WWW 2001
Year: 2001

While the information resources on the Web are vast, the sources are often hard to find, painful to use, and difficult to integrate. We have developed the Heracles framework for building Web-based information assistants. This framework provides the infrastructure to rapidly construct new applications that extract information from multiple Web sources and interactively integrate the data using a dynamic, hierarchical constraint network. This paper describes the core technologies that comprise the framework, including information extraction, hierarchical template representation, and constraint propagation. In addition, we present an application of this framework, the Travel Assistant, which is an interactive travel planning system. We also briefly describe our experience using the same framework to build a second application, the WorldInfo Assistant, which extracts and integrates geographic-related data about countries thorughout the world. We believe these types of information assistants provide a significant step forward in fully exploiting the information available on the Internet.
Carpenter: Finding Closed Patterns in Long Biological Datasets
Authors: Feng Pan, Gao Cong, Anthony K. H. Tung, Jiong Yang, Mohammed Javeed Zaki
Venue: Conference KDD 2003
Year: 2003

The growth of bioinformatics has resulted in datasets with new characteristics. These datasets typically contain a large number of columns and a small number of rows. For example, many gene expression datasets may contain 10,000-100,000 columns but only 100-1000 rows.Such datasets pose a great challenge for existing (closed) frequent pattern discovery algorithms, since they have an exponential dependence on the average row length. In this paper, we describe a new algorithm called CARPENTER that is specially designed to handle datasets having a large number of attributes and relatively small number of rows. Several experiments on real bioinformatics datasets show that CARPENTER is orders of magnitude better than previous closed pattern mining algorithms like CLOSET and CHARM.
CLOSET+: searching for the best strategies for mining frequent closed itemsets
Authors: Jianyong Wang, Jiawei Han, Jian Pei
Venue: Conference KDD 2003
Year: 2003

Mining frequent closed itemsets provides complete and non-redundant results for frequent pattern analysis. Extensive studies have proposed various strategies for efficient frequent closed itemset mining, such as depth-first search vs. breadthfirst search, vertical formats vs. horizontal formats, tree-structure vs. other data structures, top-down vs. bottom-up traversal, pseudo projection vs. physical projection of conditional database, etc. It is the right time to ask "what are the pros and cons of the strategies?" and "what and how can we pick and integrate the best strategies to achieve higher performance in general cases?"In this study, we answer the above questions by a systematic study of the search strategies and develop a winning algorithm CLOSET+. CLOSET+ integrates the advantages of the previously proposed effective strategies as well as some ones newly developed here. A thorough performance study on synthetic and real data sets has shown the advantages of the strategies and the improvement of CLOSET+ over existing mining algorithms, including CLOSET, CHARM and OP, in terms of runtime, memory usage and scalability.
Lookahead-based algorithms for anytime induction of decision trees
Authors: Saher Esmeir, Shaul Markovitch
Venue: Conference ICML 2004
Year: 2004

The majority of the existing algorithms for learning decision trees are greedy---a tree is induced top-down, making locally optimal decisions at each node. In most cases, however, the constructed tree is not globally optimal. Furthermore, the greedy algorithms require a fixed amount of time and are not able to generate a better tree if additional time is available. To overcome this problem, we present two lookahead-based algorithms for anytime induction of decision trees, thus allowing tradeoff between tree quality and learning time. The first one is depth-k lookahead, where a larger time allocation permits larger k. The second algorithm uses a novel strategy for evaluating candidate splits; a stochastic version of ID3 is repeatedly invoked to estimate the size of the tree in which each split results, and the one that minimizes the expected size is preferred. Experimental results indicate that for several hard concepts, our proposed approach exhibits good anytime behavior and yields significantly better decision trees when more time is available.
Sequential skewing: an improved skewing algorithm
Authors: Soumya Ray, David Page
Venue: Conference ICML 2004
Year: 2004

This paper extends previous work on the Skewing algorithm, a promising approach that allows greedy decision tree induction algorithms to handle problematic functions such as parity functions with a lower run-time penalty than Lookahead. A deficiency of the previously proposed algorithm is its inability to scale up to high dimensional problems. In this paper, we describe a modified algorithm that scales better with increasing numbers of variables. We present experiments with randomly generated Boolean functions that evaluate the algorithm's response to increasing dimensions. We also evaluate the algorithm on a challenging real world biomedical problem, that of SH3 domain binding. Our results indicate that our algorithm almost always outperforms an information gain-based decision tree learner.
Estimating required recall for successful knowledge acquisition from the Web
Authors: Wolfgang Gatterbauer
Venue: Conference WWW 2006
Year: 2006

Information on the Web is not only abundant but also redundant. This redundancy of information has an important consequence on the relation between the recall of an information gathering system and its capacity to harvest the core information of a certain domain of knowledge. This paper provides a new idea for estimating the necessary Web coverage of a knowledge acquisition system in order to achieve a certain desired coverage of the contained core information.
Visually guided bottom-up table detection and segmentation in web documents
Authors: Bernhard Krüpl, Marcus Herzog
Venue: Conference WWW 2006
Year: 2006

In the AllRight project, we are developing an algorithm for unsupervised table detection and segmentation that uses the visual rendition of a Web page rather than the HTML code. Our algorithm works bottom-up by grouping word bounding boxes into larger groups and uses a set of heuristics. It has already been implemented and a preliminary evaluation on about 6000 Web documents has been carried out.
Using visual cues for extraction of tabular data from arbitrary html documents
Authors: Bernhard Krüpl, Marcus Herzog, Wolfgang Gatterbauer
Venue: Conference WWW 2005
Year: 2005

We describe a method to extract tabular data from web pages. Rather than just analyzing the DOM tree, we also exploit visual cues in the rendered version of the document to extract data from tables which are not explicitly marked with an HTML table element. To detect tables, we rely on a variant of the well-known X-Y cut algorithm as used in the OCR community. We implemented the system by directly accessing Mozilla's box model that contains the positional data for all HTML elements of a given web page.
A machine learning based approach for table detection on the web
Authors: Yalin Wang, Jianying Hu
Venue: Conference WWW 2002
Year: 2002

Table is a commonly used presentation scheme, especially for describing relational information. However, table understanding remains an open problem. In this paper, we consider the problem of table detection in web documents. Its potential applications include web mining, knowledge management, and web content summarization and delivery to narrow-bandwidth devices. We describe a machine learning based approach to classify each given table entity as either genuine or non-genuine. Various features reflecting the layout as well as content characteristics of tables are studied.In order to facilitate the training and evaluation of our table classifier, we designed a novel web document table ground truthing protocol and used it to build a large table ground truth database. The database consists of 1,393 HTML files collected from hundreds of different web sites and contains 11,477 leaf TABLE elements, out of which 1,740 are genuine tables. Experiments were conducted using the cross validation method and an F-measure of 95.89% was achieved.
A new family of online algorithms for category ranking
Authors: Koby Crammer, Yoram Singer
Venue: Conference SIGIR 2002
Year: 2002

We describe a new family of topic-ranking algorithms for multi-labeled documents. The motivation for the algorithms stems from recent advances in online learning algorithms. The algorithms we present are simple to implement and are time and memory efficient. We evaluate the algorithms on the Reuters-21578 corpus and the new corpus released by Reuters in 2000. On both corpora the algorithms we present outperform adaptations to topic-ranking of Rocchio's algorithm and the Perceptron algorithm. We also outline the formal analysis of the algorithm in the mistake bound model. To our knowledge, this work is the first to report performance results with the entire new Reuters corpus.
A MFoM Learning Approach to Robust Multiclass Multi-Label Text Categorization
Authors: Sheng Gao, Wen Wu, Chin-Hui Lee 0001, Tat-Seng Chua
Venue: Conference ICML 2004
Year: 2004

Proceedings, Twenty-First International Conference on Machine Learning, ICML 2004