OpenRaiser/Intern-Atlas huggingface dataset:
Surrogate Regret Bounds for Bipartite Ranking via Strongly Proper Losses
Venue: arXiv cs.LG 2012
Year: 2012

The problem of bipartite ranking, where instances are labeled positive or negative and the goal is to learn a scoring function that minimizes the probability of mis-ranking a pair of positive and negative instances (or equivalently, that maximizes the area under the ROC curve), has been widely studied in recent years. A dominant theoretical and algorithmic framework for the problem has been to reduce bipartite ranking to pairwise classification; in particular, it is well known that the bipartite ranking regret can be formulated as a pairwise classification regret, which in turn can be upper bounded using usual regret bounds for classification problems. Recently, Kotlowski et al. (2011) showed regret bounds for bipartite ranking in terms of the regret associated with balanced versions of the standard (non-pairwise) logistic and exponential losses. In this paper, we show that such (non-pairwise) surrogate regret bounds for bipartite ranking can be obtained in terms of a broad class of proper (composite) losses that we term as strongly proper. Our proof technique is much simpler than that of Kotlowski et al. (2011), and relies on properties of proper (composite) losses as elucidated recently by Reid and Williamson (2010, 2011) and others. Our result yields explicit surrogate bounds (with no hidden balancing terms) in terms of a variety of strongly proper losses, including for example logistic, exponential, squared and squared hinge losses as special cases. We also obtain tighter surrogate bounds under certain low-noise conditions via a recent result of Clemencon and Robbiano (2011).
More Effective Crossover Operators for the All-Pairs Shortest Path Problem
Venue: arXiv cs.NE 2012
Year: 2012

The all-pairs shortest path problem is the first non-artificial problem for which it was shown that adding crossover can significantly speed up a mutation-only evolutionary algorithm. Recently, the analysis of this algorithm was refined and it was shown to have an expected optimization time (w.r.t. the number of fitness evaluations) of $Θ(n^{3.25}(\log n)^{0.25})$. In contrast to this simple algorithm, evolutionary algorithms used in practice usually employ refined recombination strategies in order to avoid the creation of infeasible offspring. We study extensions of the basic algorithm by two such concepts which are central in recombination, namely \emph{repair mechanisms} and \emph{parent selection}. We show that repairing infeasible offspring leads to an improved expected optimization time of $\mathord{O}(n^{3.2}(\log n)^{0.2})$. As a second part of our study we prove that choosing parents that guarantee feasible offspring results in an even better optimization time of $\mathord{O}(n^{3}\log n)$. Both results show that already simple adjustments of the recombination operator can asymptotically improve the runtime of evolutionary algorithms.
Universal Witnesses for State Complexity of Basic Operations Combined with Reversal
Venue: arXiv cs.FL 2012
Year: 2012

We study the state complexity of boolean operations, concatenation and star with one or two of the argument languages reversed. We derive tight upper bounds for the symmetric differences and differences of such languages. We prove that the previously discovered bounds for union, intersection, concatenation and star of such languages can all be met by the recently introduced universal witnesses and their variants.
Improving neural networks by preventing co-adaptation of feature detectors
Venue: arXiv cs.NE 2012
Year: 2012

When a large feedforward neural network is trained on a small training set, it typically performs poorly on held-out test data. This "overfitting" is greatly reduced by randomly omitting half of the feature detectors on each training case. This prevents complex co-adaptations in which a feature detector is only helpful in the context of several other specific feature detectors. Instead, each neuron learns to detect a feature that is generally helpful for producing the correct answer given the combinatorially large variety of internal contexts in which it must operate. Random "dropout" gives big improvements on many benchmark tasks and sets new records for speech and object recognition.
Meme as Building Block for Evolutionary Optimization of Problem Instances
Venue: arXiv cs.NE 2012
Year: 2012

A significantly under-explored area of evolutionary optimization in the literature is the study of optimization methodologies that can evolve along with the problems solved. Particularly, present evolutionary optimization approaches generally start their search from scratch or the ground-zero state of knowledge, independent of how similar the given new problem of interest is to those optimized previously. There has thus been the apparent lack of automated knowledge transfers and reuse across problems. Taking the cue, this paper introduces a novel Memetic Computational Paradigm for search, one that models after how human solves problems, and embarks on a study towards intelligent evolutionary optimization of problems through the transfers of structured knowledge in the form of memes learned from previous problem-solving experiences, to enhance future evolutionary searches. In particular, the proposed memetic search paradigm is composed of four culture-inspired operators, namely, Meme Learning, Meme Selection, Meme Variation and Meme Imitation. The learning operator mines for memes in the form of latent structures derived from past experiences of problem-solving. The selection operator identifies the fit memes that replicate and transmit across problems, while the variation operator introduces innovations into the memes. The imitation operator, on the other hand, defines how fit memes assimilate into the search process of newly encountered problems, thus gearing towards efficient and effective evolutionary optimization. Finally, comprehensive studies on two widely studied challenging well established NP-hard routing problem domains, particularly, the capacitated vehicle routing (CVR) and capacitated arc routing (CAR), confirm the high efficacy of the proposed memetic computational search paradigm for intelligent evolutionary optimization of problems.
Speckle Reduction using Stochastic Distances
Venue: arXiv cs.IT 2012
Year: 2012

This paper presents a new approach for filter design based on stochastic distances and tests between distributions. A window is defined around each pixel, samples are compared and only those which pass a goodness-of-fit test are used to compute the filtered value. The technique is applied to intensity Synthetic Aperture Radar (SAR) data, using the Gamma model with varying number of looks allowing, thus, changes in heterogeneity. Modified Nagao-Matsuyama windows are used to define the samples. The proposal is compared with the Lee's filter which is considered a standard, using a protocol based on simulation. Among the criteria used to quantify the quality of filters, we employ the equivalent number of looks (related to the signal-to-noise ratio), line contrast, and edge preservation. Moreover, we also assessed the filters by the Universal Image Quality Index and the Pearson's correlation between edges.
Survey on Improved Scheduling in Hadoop MapReduce in Cloud Environments
Venue: arXiv cs.DC 2012
Year: 2012

Cloud Computing is emerging as a new computational paradigm shift. Hadoop-MapReduce has become a powerful Computation Model for processing large data on distributed commodity hardware clusters such as Clouds. In all Hadoop implementations, the default FIFO scheduler is available where jobs are scheduled in FIFO order with support for other priority based schedulers also. In this paper we study various scheduler improvements possible with Hadoop and also provided some guidelines on how to improve the scheduling in Hadoop in Cloud Environments.
Theory and Techniques for Synthesizing a Family of Graph Algorithms
Venue: arXiv cs.SE 2012
Year: 2012

Although Breadth-First Search (BFS) has several advantages over Depth-First Search (DFS) its prohibitive space requirements have meant that algorithm designers often pass it over in favor of DFS. To address this shortcoming, we introduce a theory of Efficient BFS (EBFS) along with a simple recursive program schema for carrying out the search. The theory is based on dominance relations, a long standing technique from the field of search algorithms. We show how the theory can be used to systematically derive solutions to two graph algorithms, namely the Single Source Shortest Path problem and the Minimum Spanning Tree problem. The solutions are found by making small systematic changes to the derivation, revealing the connections between the two problems which are often obscured in textbook presentations of them.
A New Security Mechanism for Vehicular Communication Networks
Venue: arXiv cs.CR 2012
Year: 2012

Vehicular communication networks is a promising and emerging technology to facilitat road safety, Safety of life, traffic management, and infotainment dissemination for drivers and passengers. One of the ultimate goals in the design of such networking is to resist various malicious abuses and security attacks. In this research new security mechanisms are proposed to achieve secure certificate revocation, which is considered among the most challenging design objective in vehicular ad hoc networks.
On the Fundamental Relationship Determining the Capacity of Static and Mobile Wireless Networks
Venue: arXiv cs.NI 2012
Year: 2012

Studying the capacity of wireless multi-hop networks is an important problem and extensive research has been done in the area. In this letter, we sift through various capacity-impacting parameters and show that the capacity of both static and mobile networks is fundamentally determined by the average number of simultaneous transmissions, the link capacity and the average number of transmissions required to deliver a packet to its destination. We then use this result to explain and help to better understand existing results on the capacities of static networks, mobile networks and hybrid networks and the multicast capacity.
A Comprehensive Model to achieve Service Reusability for Multi level stakeholders using Non-Functional attributes of Service Oriented Architecture
Venue: arXiv cs.SE 2012
Year: 2012

SOA is a prominent paradigm for accomplishing reuse of services. Service reusability is one dominant factor which has a greater influence on achieving quality in SOA systems. There exists sufficient research in this area and researchers have contributed many works towards achieving quality in SOA systems but much emphasis was not provided on service reusability [1] [2] [3]. Few authors have addressed reusability factor with limited non-functional attributes. Our study focuses on identifying the non-functional attributes which have major or greater influence towards obtaining reusability in SOA systems. The objective of this study goes into the next level, to categorize the non-functional attributes on multi stakeholder's perspective i.e. Service Consumer, Service Provider and Service Developer which paves the way to build a comprehensive quality model for achieving Service Reusability
Higher-Order Partial Least Squares (HOPLS): A Generalized Multi-Linear Regression Method
Venue: arXiv cs.AI 2012
Year: 2012

A new generalized multilinear regression model, termed the Higher-Order Partial Least Squares (HOPLS), is introduced with the aim to predict a tensor (multiway array) $\tensor{Y}$ from a tensor $\tensor{X}$ through projecting the data onto the latent space and performing regression on the corresponding latent variables. HOPLS differs substantially from other regression models in that it explains the data by a sum of orthogonal Tucker tensors, while the number of orthogonal loadings serves as a parameter to control model complexity and prevent overfitting. The low dimensional latent space is optimized sequentially via a deflation operation, yielding the best joint subspace approximation for both $\tensor{X}$ and $\tensor{Y}$. Instead of decomposing $\tensor{X}$ and $\tensor{Y}$ individually, higher order singular value decomposition on a newly defined generalized cross-covariance tensor is employed to optimize the orthogonal loadings. A systematic comparison on both synthetic data and real-world decoding of 3D movement trajectories from electrocorticogram (ECoG) signals demonstrate the advantages of HOPLS over the existing methods in terms of better predictive ability, suitability to handle small sample sizes, and robustness to noise.
Of Starships and Klingons: Bayesian Logic for the 23rd Century
Venue: arXiv cs.AI 2012
Year: 2012

Intelligent systems in an open world must reason about many interacting entities related to each other in diverse ways and having uncertain features and relationships. Traditional probabilistic languages lack the expressive power to handle relational domains. Classical first-order logic is sufficiently expressive, but lacks a coherent plausible reasoning capability. Recent years have seen the emergence of a variety of approaches to integrating first-order logic, probability, and machine learning. This paper presents Multi-entity Bayesian networks (MEBN), a formal system that integrates First Order Logic (FOL) with Bayesian probability theory. MEBN extends ordinary Bayesian networks to allow representation of graphical models with repeated sub-structures, and can express a probability distribution over models of any consistent, finitely axiomatizable first-order theory. We present the logic using an example inspired by the Paramount Series StarTrek.
Unsupervised spectral learning
Venue: arXiv cs.LG 2012
Year: 2012

In spectral clustering and spectral image segmentation, the data is partioned starting from a given matrix of pairwise similarities S. the matrix S is constructed by hand, or learned on a separate training set. In this paper we show how to achieve spectral clustering in unsupervised mode. Our algorithm starts with a set of observed pairwise features, which are possible components of an unknown, parametric similarity function. This function is learned iteratively, at the same time as the clustering of the data. The algorithm shows promosing results on synthetic and real data.
Local Utility Elicitation in GAI Models
Venue: arXiv cs.GT 2012
Year: 2012

Structured utility models are essential for the effective representation and elicitation of complex multiattribute utility functions. Generalized additive independence (GAI) models provide an attractive structural model of user preferences, offering a balanced tradeoff between simplicity and applicability. While representation and inference with such models is reasonably well understood, elicitation of the parameters of such models has been studied less from a practical perspective. We propose a procedure to elicit GAI model parameters using only "local" utility queries rather than "global" queries over full outcomes. Our local queries take full advantage of GAI structure and provide a sound framework for extending the elicitation procedure to settings where the uncertainty over utility parameters is represented probabilistically. We describe experiments using a myopic value-of-information approach to elicitation in a large GAI model.
Belief Updating and Learning in Semi-Qualitative Probabilistic Networks
Venue: arXiv cs.AI 2012
Year: 2012

This paper explores semi-qualitative probabilistic networks (SQPNs) that combine numeric and qualitative information. We first show that exact inferences with SQPNs are NPPP-Complete. We then show that existing qualitative relations in SQPNs (plus probabilistic logic and imprecise assessments) can be dealt effectively through multilinear programming. We then discuss learning: we consider a maximum likelihood method that generates point estimates given a SQPN and empirical data, and we describe a Bayesian-minded method that employs the Imprecise Dirichlet Model to generate set-valued estimates.
Counterfactual Reasoning in Linear Structural Equation Models
Venue: arXiv cs.AI 2012
Year: 2012

Consider the case where causal relations among variables can be described as a Gaussian linear structural equation model. This paper deals with the problem of clarifying how the variance of a response variable would have changed if a treatment variable were assigned to some value (counterfactually), given that a set of variables is observed (actually). In order to achieve this aim, we reformulate the formulas of the counterfactual distribution proposed by Balke and Pearl (1995) through both the total effects and a covariance matrix of observed variables. We further extend the framework of Balke and Pearl (1995) from point observations to interval observations, and from an unconditional plan to a conditional plan. The results of this paper enable us to clarify the properties of counterfactual distribution and establish an optimal plan.
Modeling Transportation Routines using Hybrid Dynamic Mixed Networks
Venue: arXiv cs.AI 2012
Year: 2012

This paper describes a general framework called Hybrid Dynamic Mixed Networks (HDMNs) which are Hybrid Dynamic Bayesian Networks that allow representation of discrete deterministic information in the form of constraints. We propose approximate inference algorithms that integrate and adjust well known algorithmic principles such as Generalized Belief Propagation, Rao-Blackwellised Particle Filtering and Constraint Propagation to address the complexity of modeling and reasoning in HDMNs. We use this framework to model a person's travel activity over time and to predict destination and routes given the current location. We present a preliminary empirical evaluation demonstrating the effectiveness of our modeling framework and algorithms using several variants of the activity model.
Learning Bayesian Network Parameters with Prior Knowledge about Context-Specific Qualitative Influences
Venue: arXiv cs.AI 2012
Year: 2012

We present a method for learning the parameters of a Bayesian network with prior knowledge about the signs of influences between variables. Our method accommodates not just the standard signs, but provides for context-specific signs as well. We show how the various signs translate into order constraints on the network parameters and how isotonic regression can be used to compute order-constrained estimates from the available data. Our experimental results show that taking prior knowledge about the signs of influences into account leads to an improved fit of the true distribution, especially when only a small sample of data is available. Moreover, the computed estimates are guaranteed to be consistent with the specified signs, thereby resulting in a network that is more likely to be accepted by experts in its domain of application.
Asynchronous Dynamic Bayesian Networks
Venue: arXiv cs.AI 2012
Year: 2012

Systems such as sensor networks and teams of autonomous robots consist of multiple autonomous entities that interact with each other in a distributed, asynchronous manner. These entities need to keep track of the state of the system as it evolves. Asynchronous systems lead to special challenges for monitoring, as nodes must update their beliefs independently of each other and no central coordination is possible. Furthermore, the state of the system continues to change as beliefs are being updated. Previous approaches to developing distributed asynchronous probabilistic reasoning systems have used static models. We present an approach using dynamic models, that take into account the way the system changes state over time. Our approach, which is based on belief propagation, is fully distributed and asynchronous, and allows the world to keep on changing as messages are being sent around. Experimental results show that our approach compares favorably to the factored frontier algorithm.
Robotic Mapping with Polygonal Random Fields
Venue: arXiv cs.RO 2012
Year: 2012

Two types of probabilistic maps are popular in the mobile robotics literature: occupancy grids and geometric maps. Occupancy grids have the advantages of simplicity and speed, but they represent only a restricted class of maps and they make incorrect independence assumptions. On the other hand, current geometric approaches, which characterize the environment by features such as line segments, can represent complex environments compactly. However, they do not reason explicitly about occupancy, a necessity for motion planning; and, they lack a complete probability model over environmental structures. In this paper we present a probabilistic mapping technique based on polygonal random fields (PRF), which combines the advantages of both approaches. Our approach explicitly represents occupancy using a geometric representation, and it is based upon a consistent probability distribution over environments which avoids the incorrect independence assumptions made by occupancy grids. We show how sampling techniques for PRFs can be applied to localized laser and sonar data, and we demonstrate significant improvements in mapping performance over occupancy grids.
Description Logics with Fuzzy Concrete Domains
Venue: arXiv cs.AI 2012
Year: 2012

We present a fuzzy version of description logics with concrete domains. Main features are: (i) concept constructors are based on t-norm, t-conorm, negation and implication; (ii) concrete domains are fuzzy sets; (iii) fuzzy modifiers are allowed; and (iv) the reasoning algorithm is based on a mixture of completion rules and bounded mixed integer programming.
Bayes' Bluff: Opponent Modelling in Poker
Venue: arXiv cs.GT 2012
Year: 2012

Poker is a challenging problem for artificial intelligence, with non-deterministic dynamics, partial observability, and the added difficulty of unknown adversaries. Modelling all of the uncertainties in this domain is not an easy task. In this paper we present a Bayesian probabilistic model for a broad class of poker games, separating the uncertainty in the game dynamics from the uncertainty of the opponent's strategy. We then describe approaches to two key subproblems: (i) inferring a posterior over opponent strategies given a prior distribution and observations of their play, and (ii) playing an appropriate response to that distribution. We demonstrate the overall approach on a reduced version of poker using Dirichlet priors and then on the full game of Texas hold'em using a more informed prior. We demonstrate methods for playing effective responses to the opponent, based on the posterior.
Mining Associated Text and Images with Dual-Wing Harmoniums
Venue: arXiv cs.LG 2012
Year: 2012

We propose a multi-wing harmonium model for mining multimedia data that extends and improves on earlier models based on two-layer random fields, which capture bidirectional dependencies between hidden topic aspects and observed inputs. This model can be viewed as an undirected counterpart of the two-layer directed models such as LDA for similar tasks, but bears significant difference in inference/learning cost tradeoffs, latent topic representations, and topic mixing mechanisms. In particular, our model facilitates efficient inference and robust topic mixing, and potentially provides high flexibilities in modeling the latent topic spaces. A contrastive divergence and a variational algorithm are derived for learning. We specialized our model to a dual-wing harmonium for captioned images, incorporating a multivariate Poisson for word-counts and a multivariate Gaussian for color histogram. We present empirical results on the applications of this model to classification, retrieval and image annotation on news video collections, and we report an extensive comparison with various extant models.