OpenRaiser/Intern-Atlas huggingface dataset:
Bias Correction and Modified Profile Likelihood under the Wishart Complex Distribution
Venue: arXiv cs.CV 2014
Year: 2014

This paper proposes improved methods for the maximum likelihood (ML) estimation of the equivalent number of looks $L$. This parameter has a meaningful interpretation in the context of polarimetric synthetic aperture radar (PolSAR) images. Due to the presence of coherent illumination in their processing, PolSAR systems generate images which present a granular noise called speckle. As a potential solution for reducing such interference, the parameter $L$ controls the signal-noise ratio. Thus, the proposal of efficient estimation methodologies for $L$ has been sought. To that end, we consider firstly that a PolSAR image is well described by the scaled complex Wishart distribution. In recent years, Anfinsen et al. derived and analyzed estimation methods based on the ML and on trace statistical moments for obtaining the parameter $L$ of the unscaled version of such probability law. This paper generalizes that approach. We present the second-order bias expression proposed by Cox and Snell for the ML estimator of this parameter. Moreover, the formula of the profile likelihood modified by Barndorff-Nielsen in terms of $L$ is discussed. Such derivations yield two new ML estimators for the parameter $L$, which are compared to the estimators proposed by Anfinsen et al. The performance of these estimators is assessed by means of Monte Carlo experiments, adopting three statistical measures as comparison criterion: the mean square error, the bias, and the coefficient of variation. Equivalently to the simulation study, an application to actual PolSAR data concludes that the proposed estimators outperform all the others in homogeneous scenarios.
Causal Interfaces
Venue: arXiv cs.AI 2014
Year: 2014

The interaction of two binary variables, assumed to be empirical observations, has three degrees of freedom when expressed as a matrix of frequencies. Usually, the size of causal influence of one variable on the other is calculated as a single value, as increase in recovery rate for a medical treatment, for example. We examine what is lost in this simplification, and propose using two interface constants to represent positive and negative implications separately. Given certain assumptions about non-causal outcomes, the set of resulting epistemologies is a continuum. We derive a variety of particular measures and contrast them with the one-dimensional index.
CTBNCToolkit: Continuous Time Bayesian Network Classifier Toolkit
Venue: arXiv cs.AI 2014
Year: 2014

Continuous time Bayesian network classifiers are designed for temporal classification of multivariate streaming data when time duration of events matters and the class does not change over time. This paper introduces the CTBNCToolkit: an open source Java toolkit which provides a stand-alone application for temporal classification and a library for continuous time Bayesian network classifiers. CTBNCToolkit implements the inference algorithm, the parameter learning algorithm, and the structural learning algorithm for continuous time Bayesian network classifiers. The structural learning algorithm is based on scoring functions: the marginal log-likelihood score and the conditional log-likelihood score are provided. CTBNCToolkit provides also an implementation of the expectation maximization algorithm for clustering purpose. The paper introduces continuous time Bayesian network classifiers. How to use the CTBNToolkit from the command line is described in a specific section. Tutorial examples are included to facilitate users to understand how the toolkit must be used. A section dedicate to the Java library is proposed to help further code extensions.
Enumerating Maximal Bicliques from a Large Graph using MapReduce
Venue: arXiv cs.DC 2014
Year: 2014

We consider the enumeration of maximal bipartite cliques (bicliques) from a large graph, a task central to many practical data mining problems in social network analysis and bioinformatics. We present novel parallel algorithms for the MapReduce platform, and an experimental evaluation using Hadoop MapReduce. Our algorithm is based on clustering the input graph into smaller sized subgraphs, followed by processing different subgraphs in parallel. Our algorithm uses two ideas that enable it to scale to large graphs: (1) the redundancy in work between different subgraph explorations is minimized through a careful pruning of the search space, and (2) the load on different reducers is balanced through the use of an appropriate total order among the vertices. Our evaluation shows that the algorithm scales to large graphs with millions of edges and tens of mil- lions of maximal bicliques. To our knowledge, this is the first work on maximal biclique enumeration for graphs of this scale.
Opinion Mining In Hindi Language: A Survey
Venue: arXiv cs.IR 2014
Year: 2014

Opinions are very important in the life of human beings. These Opinions helped the humans to carry out the decisions. As the impact of the Web is increasing day by day, Web documents can be seen as a new source of opinion for human beings. Web contains a huge amount of information generated by the users through blogs, forum entries, and social networking websites and so on To analyze this large amount of information it is required to develop a method that automatically classifies the information available on the Web. This domain is called Sentiment Analysis and Opinion Mining. Opinion Mining or Sentiment Analysis is a natural language processing task that mine information from various text forms such as reviews, news, and blogs and classify them on the basis of their polarity as positive, negative or neutral. But, from the last few years, enormous increase has been seen in Hindi language on the Web. Research in opinion mining mostly carried out in English language but it is very important to perform the opinion mining in Hindi language also as large amount of information in Hindi is also available on the Web. This paper gives an overview of the work that has been done Hindi language.
Promoting cold-start items in recommender systems
Venue: arXiv cs.IR 2014
Year: 2014

As one of major challenges, cold-start problem plagues nearly all recommender systems. In particular, new items will be overlooked, impeding the development of new products online. Given limited resources, how to utilize the knowledge of recommender systems and design efficient marketing strategy for new items is extremely important. In this paper, we convert this ticklish issue into a clear mathematical problem based on a bipartite network representation. Under the most widely used algorithm in real e-commerce recommender systems, so-called the item-based collaborative filtering, we show that to simply push new items to active users is not a good strategy. To our surprise, experiments on real recommender systems indicate that to connect new items with some less active users will statistically yield better performance, namely these new items will have more chance to appear in other users' recommendation lists. Further analysis suggests that the disassortative nature of recommender systems contributes to such observation. In a word, getting in-depth understanding on recommender systems could pave the way for the owners to popularize their cold-start products with low costs.
Bipartite Graph based Construction of Compressed Sensing Matrices
Venue: arXiv cs.IT 2014
Year: 2014

This paper proposes an efficient method to construct the bipartite graph with as many edges as possible while without introducing the shortest cycles of length equal to 4. The binary matrix associated with the bipartite graph described above presents comparable and even better phase transitions than Gaussian random matrices.
Functional dependencies with null markers
Venue: arXiv cs.DB 2014
Year: 2014

Functional dependencies are an integral part of database design. However, they are only defined when we exclude null markers. Yet we commonly use null markers in practice. To bridge this gap between theory and practice, researchers have proposed definitions of functional dependencies over relations with null markers. Though sound, these definitions lack some qualities that we find desirable. For example, some fail to satisfy Armstrong's axioms---while these axioms are part of the foundation of common database methodologies. We propose a set of properties that any extension of functional dependencies over relations with null markers should possess. We then propose two new extensions having these properties. These extensions attempt to allow null markers where they make sense to practitioners. They both support Armstrong's axioms and provide realizable null markers: at any time, some or all of the null markers can be replaced by actual values without causing an anomaly. Our proposals may improve database designs.
Dynamic and Multi-functional Labeling Schemes
Venue: arXiv cs.DS 2014
Year: 2014

We investigate labeling schemes supporting adjacency, ancestry, sibling, and connectivity queries in forests. In the course of more than 20 years, the existence of $\log n + O(\log \log)$ labeling schemes supporting each of these functions was proven, with the most recent being ancestry [Fraigniaud and Korman, STOC '10]. Several multi-functional labeling schemes also enjoy lower or upper bounds of $\log n + Ω(\log \log n)$ or $\log n + O(\log \log n)$ respectively. Notably an upper bound of $\log n + 5\log \log n$ for adjacency+siblings and a lower bound of $\log n + \log \log n$ for each of the functions siblings, ancestry, and connectivity [Alstrup et al., SODA '03]. We improve the constants hidden in the $O$-notation. In particular we show a $\log n + 2\log \log n$ lower bound for connectivity+ancestry and connectivity+siblings, as well as an upper bound of $\log n + 3\log \log n + O(\log \log \log n)$ for connectivity+adjacency+siblings by altering existing methods. In the context of dynamic labeling schemes it is known that ancestry requires $Ω(n)$ bits [Cohen, et al. PODS '02]. In contrast, we show upper and lower bounds on the label size for adjacency, siblings, and connectivity of $2\log n$ bits, and $3 \log n$ to support all three functions. There exist efficient adjacency labeling schemes for planar, bounded treewidth, bounded arboricity and interval graphs. In a dynamic setting, we show a lower bound of $Ω(n)$ for each of those families.
Multiresolution analysis on compact Riemannian manifolds
Venue: arXiv cs.IT 2014
Year: 2014

In the chapter "Multiresolution Analysis on Compact Riemannian Manifolds" Isaac Pesenson describes multiscale analysis, sampling, interpolation and approximation of functions defined on manifolds. His main achievements are: construction on manifolds of bandlimited and space-localized frames which have Parseval property and construction of variational splines on manifolds. Such frames and splines enable multiscale analysis on arbitrary compact manifolds, and they already found a number of important applications (statistics, CMB, crystallography) related to such manifolds as two-dimensional sphere and group of its rotations.
Influence of the learning method in the performance of feedforward neural networks when the activity of neurons is modified
Venue: arXiv cs.NE 2014
Year: 2014

A method that allows us to give a different treatment to any neuron inside feedforward neural networks is presented. The algorithm has been implemented with two very different learning methods: a standard Back-propagation (BP) procedure and an evolutionary algorithm. First, we have demonstrated that the EA training method converges faster and gives more accurate results than BP. Then we have made a full analysis of the effects of turning off different combinations of neurons after the training phase. We demonstrate that EA is much more robust than BP for all the cases under study. Even in the case when two hidden neurons are lost, EA training is still able to give good average results. This difference implies that we must be very careful when pruning or redundancy effects are being studied since the network performance when losing neurons strongly depends on the training method. Moreover, the influence of the individual inputs will also depend on the training algorithm. Since EA keeps a good classification performance when units are lost, this method could be a good way to simulate biological learning systems since they must be robust against deficient neuron performance. Although biological systems are much more complex than the simulations shown in this article, we propose that a smart training strategy such as the one shown here could be considered as a first protection against the losing of a certain number of neurons.
Discrimination on the Grassmann Manifold: Fundamental Limits of Subspace Classifiers
Venue: arXiv cs.IT 2014
Year: 2014

We present fundamental limits on the reliable classification of linear and affine subspaces from noisy, linear features. Drawing an analogy between discrimination among subspaces and communication over vector wireless channels, we propose two Shannon-inspired measures to characterize asymptotic classifier performance. First, we define the classification capacity, which characterizes necessary and sufficient conditions for the misclassification probability to vanish as the signal dimension, the number of features, and the number of subspaces to be discerned all approach infinity. Second, we define the diversity-discrimination tradeoff which, by analogy with the diversity-multiplexing tradeoff of fading vector channels, characterizes relationships between the number of discernible subspaces and the misclassification probability as the noise power approaches zero. We derive upper and lower bounds on these measures which are tight in many regimes. Numerical results, including a face recognition application, validate the results in practice.
A higher-order MRF based variational model for multiplicative noise reduction
Venue: arXiv cs.CV 2014
Year: 2014

The Fields of Experts (FoE) image prior model, a filter-based higher-order Markov Random Fields (MRF) model, has been shown to be effective for many image restoration problems. Motivated by the successes of FoE-based approaches, in this letter, we propose a novel variational model for multiplicative noise reduction based on the FoE image prior model. The resulted model corresponds to a non-convex minimization problem, which can be solved by a recently published non-convex optimization algorithm. Experimental results based on synthetic speckle noise and real synthetic aperture radar (SAR) images suggest that the performance of our proposed method is on par with the best published despeckling algorithm. Besides, our proposed model comes along with an additional advantage, that the inference is extremely efficient. {Our GPU based implementation takes less than 1s to produce state-of-the-art despeckling performance.}
$L_p$-Testers for Bounded Derivative Properties on Product Distributions
Venue: arXiv cs.DS 2014
Year: 2014

We consider the problem of $L_p$-testing of class of bounded derivative properties over hypergrid domain with points distributed according to some product distribution. This class includes monotonicity, the Lipschitz property, $(α,β)$-generalized Lipschitz and many more properties. Previous results for $L_p$ testing on $[n]^d$ for this class were known for monotonicity and $c$-Lipschitz properties over uniformly distributed domains. \medskip Our results imply testers that give the same upper bound for arbitrary product distributions as the hitherto known testers, which use uniformly randomly chosen samples from $[n]^d$, for monotonicity and Lipschitz testing. Also, our testers are \emph{optimal} for a large class of bounded derivative properties, that includes $(α, β)$-generalized Lipschitz property, over uniform distributions. Infact, each edge in $[n]^d$ is allowed to have it's own left and right Lipschitz constants. The time complexity is \emph{same} for arbitrary product distributions.
Vertex Cover Gets Faster and Harder on Low Degree Graphs
Venue: arXiv cs.DS 2014
Year: 2014

The problem of finding an optimal vertex cover in a graph is a classic NP-complete problem, and is a special case of the hitting set question. On the other hand, the hitting set problem, when asked in the context of induced geometric objects, often turns out to be exactly the vertex cover problem on restricted classes of graphs. In this work we explore a particular instance of such a phenomenon. We consider the problem of hitting all axis-parallel slabs induced by a point set P, and show that it is equivalent to the problem of finding a vertex cover on a graph whose edge set is the union of two Hamiltonian Paths. We show the latter problem to be NP-complete, and we also give an algorithm to find a vertex cover of size at most k, on graphs of maximum degree four, whose running time is 1.2637^k n^O(1).
Fast Algorithms for Constructing Maximum Entropy Summary Trees
Venue: arXiv cs.DS 2014
Year: 2014

Karloff? and Shirley recently proposed summary trees as a new way to visualize large rooted trees (Eurovis 2013) and gave algorithms for generating a maximum-entropy k-node summary tree of an input n-node rooted tree. However, the algorithm generating optimal summary trees was only pseudo-polynomial (and worked only for integral weights); the authors left open existence of a olynomial-time algorithm. In addition, the authors provided an additive approximation algorithm and a greedy heuristic, both working on real weights. This paper shows how to construct maximum entropy k-node summary trees in time O(k^2 n + n log n) for real weights (indeed, as small as the time bound for the greedy heuristic given previously); how to speed up the approximation algorithm so that it runs in time O(n + (k^4/eps?) log(k/eps?)), and how to speed up the greedy algorithm so as to run in time O(kn + n log n). Altogether, these results make summary trees a much more practical tool than before.
The Likelihood Encoder for Lossy Source Compression
Venue: arXiv cs.IT 2014
Year: 2014

In this work, a likelihood encoder is studied in the context of lossy source compression. The analysis of the likelihood encoder is based on a soft-covering lemma. It is demonstrated that the use of a likelihood encoder together with the soft-covering lemma gives alternative achievability proofs for classical source coding problems. The case of the rate-distortion function with side information at the decoder (i.e. the Wyner-Ziv problem) is carefully examined and an application of the likelihood encoder to the multi-terminal source coding inner bound (i.e. the Berger-Tung region) is outlined.
From Quantity to Quality: Massive Molecular Dynamics Simulation of Nanostructures under Plastic Deformation in Desktop and Service Grid Distributed Computing Infrastructure
Venue: arXiv cs.CE 2014
Year: 2014

The distributed computing infrastructure (DCI) on the basis of BOINC and EDGeS-bridge technologies for high-performance distributed computing is used for porting the sequential molecular dynamics (MD) application to its parallel version for DCI with Desktop Grids (DGs) and Service Grids (SGs). The actual metrics of the working DG-SG DCI were measured, and the normal distribution of host performances, and signs of log-normal distributions of other characteristics (CPUs, RAM, and HDD per host) were found. The practical feasibility and high efficiency of the MD simulations on the basis of DG-SG DCI were demonstrated during the experiment with the massive MD simulations for the large quantity of aluminum nanocrystals ($\sim10^2$-$10^3$). Statistical analysis (Kolmogorov-Smirnov test, moment analysis, and bootstrapping analysis) of the defect density distribution over the ensemble of nanocrystals had shown that change of plastic deformation mode is followed by the qualitative change of defect density distribution type over ensemble of nanocrystals. Some limitations (fluctuating performance, unpredictable availability of resources, etc.) of the typical DG-SG DCI were outlined, and some advantages (high efficiency, high speedup, and low cost) were demonstrated. Deploying on DG DCI allows to get new scientific $\it{quality}$ from the simulated $\it{quantity}$ of numerous configurations by harnessing sufficient computational power to undertake MD simulations in a wider range of physical parameters (configurations) in a much shorter timeframe.
Find my mug: Efficient object search with a mobile robot using semantic segmentation
Venue: arXiv cs.CV 2014
Year: 2014

In this paper, we propose an efficient semantic segmentation framework for indoor scenes, tailored to the application on a mobile robot. Semantic segmentation can help robots to gain a reasonable understanding of their environment, but to reach this goal, the algorithms not only need to be accurate, but also fast and robust. Therefore, we developed an optimized 3D point cloud processing framework based on a Randomized Decision Forest, achieving competitive results at sufficiently high frame rates. We evaluate the capabilities of our method on the popular NYU depth dataset and our own data and demonstrate its feasibility by deploying it on a mobile service robot, for which we could optimize an object search procedure using our results.
Capture-Avoiding and Hygienic Program Transformations (incl. Proofs)
Venue: arXiv cs.PL 2014
Year: 2014

Program transformations in terms of abstract syntax trees compromise referential integrity by introducing variable capture. Variable capture occurs when in the generated program a variable declaration accidentally shadows the intended target of a variable reference. Existing transformation systems either do not guarantee the avoidance of variable capture or impair the implementation of transformations. We present an algorithm called name-fix that automatically eliminates variable capture from a generated program by systematically renaming variables. name-fix is guided by a graph representation of the binding structure of a program, and requires name-resolution algorithms for the source language and the target language of a transformation. name-fix is generic and works for arbitrary transformations in any transformation system that supports origin tracking for names. We verify the correctness of name-fix and identify an interesting class of transformations for which name-fix provides hygiene. We demonstrate the applicability of name-fix for implementing capture-avoiding substitution, inlining, lambda lifting, and compilers for two domain-specific languages.