OpenRaiser/Intern-Atlas huggingface dataset:
Color Image Enhancement Using the lrgb Coordinates in the Context of Support Fuzzification
Venue: arXiv cs.CV 2015
Year: 2015

Image enhancement is an important stage in the image-processing domain. The most known image enhancement method is the histogram equalization. This method is an automated one, and realizes a simultaneous modification for brightness and contrast in the case of monochrome images and for brightness, contrast, saturation and hue in the case of color images. Simple and efficient methods can be obtained if affine transforms within logarithmic models are used. A very important thing in the affine transform determination for color images is the coordinate system that is used for color space representation. Thus, the using of the RGB coordinates leads to a simultaneous modification of luminosity and saturation. In this paper using the lrgb perceptual coordinates one can define affine transforms, which allow a separated modification of luminosity l and saturation s (saturation being calculated with the component rgb in the chromatic plane). Better results can be obtained if partitions are defined on the image support and then the pixels are separately processed in each window belonging to the defined partition. Classical partitions frequently lead to the appearance of some discontinuities at the boundaries between these windows. In order to avoid all these drawbacks the classical partitions may be replaced by fuzzy partitions. Their elements will be fuzzy windows and in each of them there will be defined an affine transform induced by parameters using the fuzzy mean, fuzzy variance and fuzzy saturation computed for the pixels that belong to the analyzed window. The final image is obtained by summing up in a weight way the images of every fuzzy window.
Parallel Identity Testing for Skew Circuits with Big Powers and Applications
Venue: arXiv cs.CC 2015
Year: 2015

Powerful skew arithmetic circuits are introduced. These are skew arithmetic circuits with variables, where input gates can be labelled with powers $x^n$ for binary encoded numbers $n$. It is shown that polynomial identity testing for powerful skew arithmetic circuits belongs to $\mathsf{coRNC}^2$, which generalizes a corresponding result for (standard) skew circuits. Two applications of this result are presented: (i) Equivalence of higher-dimensional straight-line programs can be tested in $\mathsf{coRNC}^2$; this result is even new in the one-dimensional case, where the straight-line programs produce strings. (ii) The compressed word problem (or circuit evaluation problem) for certain wreath products of finitely generated abelian groups belongs to $\mathsf{coRNC}^2$.
Structural Properties of an Open Problem in Preemptive Scheduling
Venue: arXiv cs.DM 2015
Year: 2015

Structural properties of optimal preemptive schedules have been studied in a number of recent papers with a primary focus on two structural parameters: the minimum number of preemptions necessary, and a tight lower bound on `shifts', i.e., the sizes of intervals bounded by the times created by preemptions, job starts, or completions. So far only rough bounds for these parameters have been derived for specific problems. This paper sharpens the bounds on these structural parameters for a well-known open problem in the theory of preemptive scheduling: Instances consist of in-trees of $n$ unit-execution-time jobs with release dates, and the objective is to minimize the total completion time on two processors. This is among the current, tantalizing `threshold' problems of scheduling theory: Our literature survey reveals that any significant generalization leads to an NP-hard problem, but that any significant simplification leads to tractable problem. For the above problem, we show that the number of preemptions necessary for optimality need not exceed $2n-1$; that the number must be of order $Ω(\log n)$ for some instances; and that the minimum shift need not be less than $2^{-2n+1}$. These bounds are obtained by combinatorial analysis of optimal schedules rather than by the analysis of polytope corners for linear-program formulations, an approach to be found in earlier papers. The bounds immediately follow from a fundamental structural property called `normality', by which minimal shifts of a job are exponentially decreasing functions. In particular, the first interval between a preempted job's start and its preemption is a multiple of 1/2, the second such interval is a multiple of 1/4, and in general, the $i$-th preemption occurs at a multiple of $2^{-i}$. We expect the new structural properties to play a prominent role in finally settling a vexing, still-open question of complexity.
Inferring 3D Object Pose in RGB-D Images
Venue: arXiv cs.CV 2015
Year: 2015

The goal of this work is to replace objects in an RGB-D scene with corresponding 3D models from a library. We approach this problem by first detecting and segmenting object instances in the scene using the approach from Gupta et al. [13]. We use a convolutional neural network (CNN) to predict the pose of the object. This CNN is trained using pixel normals in images containing rendered synthetic objects. When tested on real data, it outperforms alternative algorithms trained on real data. We then use this coarse pose estimate along with the inferred pixel support to align a small number of prototypical models to the data, and place the model that fits the best into the scene. We observe a 48% relative improvement in performance at the task of 3D detection over the current state-of-the-art [33], while being an order of magnitude faster at the same time.
Physical Biomodeling: a new field enabled by 3-D printing in biomodeling
Venue: arXiv cs.OH 2015
Year: 2015

Accurate physical modeling with 3D-printing techniques could lead to new approaches to study structure and dynamics of biological systems complementing computational methods. Computational biology has become an important part of research over the last couple of decades. Now 3D printing technology opens the door for a new field, Physical Biomodeling, at the intersection of experimental data, computational biology and physical modeling for study of biological systems, such as protein folding at nano-scale. Here I explore this new domain of precision physical modeling and correlate it with existing visualization and computational systems and future possibilities. Dynamic physical models can be designed to-scale that can serve as research tools in future along with existing biocomputational tools and databases, adding a third angle to tackle unsolved scientific problems.
Computational Curiosity (A Book Draft)
Venue: arXiv cs.AI 2015
Year: 2015

This book discusses computational curiosity, from the psychology of curiosity to the computational models of curiosity, and then showcases several interesting applications of computational curiosity. A brief overview of the book is given as follows. Chapter 1 discusses the underpinnings of curiosity in human beings, including the major categories of curiosity, curiosity-related emotions and behaviors, and the benefits of curiosity. Chapter 2 reviews the arousal theories of curiosity in psychology and summarizes a general two-step process model for computational curiosity. Base on the perspective of the two-step process model, Chapter 3 reviews and analyzes some of the traditional computational models of curiosity. Chapter 4 introduces a novel generic computational model of curiosity, which is developed based on the arousal theories of curiosity. After the discussion of computational models of curiosity, we outline the important applications where computational curiosity may bring significant impacts in Chapter 5. Chapter 6 discusses the application of the generic computational model of curiosity in a machine learning framework. Chapter 7 discusses the application of the generic computational model of curiosity in a recommender system. In Chapter 8 and Chapter 9, the generic computational model of curiosity is studied in two types of pedagogical agents. In Chapter 8, a curious peer learner is studied. It is a non-player character that aims to provide a believable virtual learning environment for users. In Chapter 9, a curious learning companion is studied. It aims to enhance users' learning experience through providing meaningful interactions with them. Chapter 10 discusses open questions in the research field of computation curiosity.
Advances in Artificial Intelligence: Are you sure, we are on the right track?
Venue: arXiv cs.AI 2015
Year: 2015

Over the past decade, AI has made a remarkable progress. It is agreed that this is due to the recently revived Deep Learning technology. Deep Learning enables to process large amounts of data using simplified neuron networks that simulate the way in which the brain works. However, there is a different point of view, which posits that the brain is processing information, not data. This unresolved duality hampered AI progress for years. In this paper, I propose a notion of Integrated information that hopefully will resolve the problem. I consider integrated information as a coupling between two separate entities - physical information (that implies data processing) and semantic information (that provides physical information interpretation). In this regard, intelligence becomes a product of information processing. Extending further this line of thinking, it can be said that information processing does not require more a human brain for its implementation. Indeed, bacteria and amoebas exhibit intelligent behavior without any sign of a brain. That dramatically removes the need for AI systems to emulate the human brain complexity! The paper tries to explore this shift in AI systems design philosophy.
Impact of network size on the performance of incremental LMS adaptive networks
Venue: arXiv cs.IT 2015
Year: 2015

In this paper we study the impact of network size on the performance of incremental least mean square (ILMS) adaptive networks. Specifically, we consider two ILMS networks with different number of nodes and compare their performance in two different cases including (i) ideal links and (ii) noisy links. We show that when the links between nodes are ideal, increasing the network size improves the steady-state error. On the other hand, in the presence of noisy links, we see different behavior and the ILMS adaptive network with more nodes necessarily has not better steady-state performance. Simulation results are also provided to illustrate the discussions.
Proper Complex Gaussian Processes for Regression
Venue: arXiv cs.LG 2015
Year: 2015

Complex-valued signals are used in the modeling of many systems in engineering and science, hence being of fundamental interest. Often, random complex-valued signals are considered to be proper. A proper complex random variable or process is uncorrelated with its complex conjugate. This assumption is a good model of the underlying physics in many problems, and simplifies the computations. While linear processing and neural networks have been widely studied for these signals, the development of complex-valued nonlinear kernel approaches remains an open problem. In this paper we propose Gaussian processes for regression as a framework to develop 1) a solution for proper complex-valued kernel regression and 2) the design of the reproducing kernel for complex-valued inputs, using the convolutional approach for cross-covariances. In this design we pay attention to preserve, in the complex domain, the measure of similarity between near inputs. The hyperparameters of the kernel are learned maximizing the marginal likelihood using Wirtinger derivatives. Besides, the approach is connected to the multiple output learning scenario. In the experiments included, we first solve a proper complex Gaussian process where the cross-covariance does not cancel, a challenging scenario when dealing with proper complex signals. Then we successfully use these novel results to solve some problems previously proposed in the literature as benchmarks, reporting a remarkable improvement in the estimation error.
Progressive Transactional Memory in Time and Space
Venue: arXiv cs.DC 2015
Year: 2015

Transactional memory (TM) allows concurrent processes to organize sequences of operations on shared \emph{data items} into atomic transactions. A transaction may commit, in which case it appears to have executed sequentially or it may \emph{abort}, in which case no data item is updated. The TM programming paradigm emerged as an alternative to conventional fine-grained locking techniques, offering ease of programming and compositionality. Though typically themselves implemented using locks, TMs hide the inherent issues of lock-based synchronization behind a nice transactional programming interface. In this paper, we explore inherent time and space complexity of lock-based TMs, with a focus of the most popular class of \emph{progressive} lock-based TMs. We derive that a progressive TM might enforce a read-only transaction to perform a quadratic (in the number of the data items it reads) number of steps and access a linear number of distinct memory locations, closing the question of inherent cost of \emph{read validation} in TMs. We then show that the total number of \emph{remote memory references} (RMRs) that take place in an execution of a progressive TM in which $n$ concurrent processes perform transactions on a single data item might reach $Ω(n \log n)$, which appears to be the first RMR complexity lower bound for transactional memory.
Point sets with many non-crossing matchings
Venue: arXiv cs.CG 2015
Year: 2015

The maximum number of non-crossing straight-line perfect matchings that a set of $n$ points in the plane can have is known to be $O(10.0438^n)$ and $Ω^*(3^n)$. The lower bound, due to García, Noy, and Tejel (2000) is attained by the double chain, which has $Θ(3^n n^{O(1)})$ such matchings. We reprove this bound in a simplified way that uses the novel notion of down-free matching, and apply this approach on several other constructions. As a result, we improve the lower bound. First we show that double zigzag chain with $n$ points has $Θ^*(λ^n)$ such matchings with $λ\approx 3.0532$. Next we analyze further generalizations of double zigzag chains - double $r$-chains. The best choice of parameters leads to a construction with $Θ^*(ν^n)$ matchings, with $ν\approx 3.0930$. The derivation of this bound requires an analysis of a coupled dynamic-programming recursion between two infinite vectors.
Semi-supervised Segmentation Fusion of Multi-spectral and Aerial Images
Venue: arXiv cs.CV 2015
Year: 2015

A Semi-supervised Segmentation Fusion algorithm is proposed using consensus and distributed learning. The aim of Unsupervised Segmentation Fusion (USF) is to achieve a consensus among different segmentation outputs obtained from different segmentation algorithms by computing an approximate solution to the NP problem with less computational complexity. Semi-supervision is incorporated in USF using a new algorithm called Semi-supervised Segmentation Fusion (SSSF). In SSSF, side information about the co-occurrence of pixels in the same or different segments is formulated as the constraints of a convex optimization problem. The results of the experiments employed on artificial and real-world benchmark multi-spectral and aerial images show that the proposed algorithms perform better than the individual state-of-the art segmentation algorithms.
On Sex, Evolution, and the Multiplicative Weights Update Algorithm
Venue: arXiv cs.LG 2015
Year: 2015

We consider a recent innovative theory by Chastain et al. on the role of sex in evolution [PNAS'14]. In short, the theory suggests that the evolutionary process of gene recombination implements the celebrated multiplicative weights updates algorithm (MWUA). They prove that the population dynamics induced by sexual reproduction can be precisely modeled by genes that use MWUA as their learning strategy in a particular coordination game. The result holds in the environments of \emph{weak selection}, under the assumption that the population frequencies remain a product distribution. We revisit the theory, eliminating both the requirement of weak selection and any assumption on the distribution of the population. Removing the assumption of product distributions is crucial, since as we show, this assumption is inconsistent with the population dynamics. We show that the marginal allele distributions induced by the population dynamics precisely match the marginals induced by a multiplicative weights update algorithm in this general setting, thereby affirming and substantially generalizing these earlier results. We further revise the implications for convergence and utility or fitness guarantees in coordination games. In contrast to the claim of Chastain et al.[PNAS'14], we conclude that the sexual evolutionary dynamics does not entail any property of the population distribution, beyond those already implied by convergence.
Tensor Spectral Clustering for Partitioning Higher-order Network Structures
Venue: arXiv cs.SI 2015
Year: 2015

Spectral graph theory-based methods represent an important class of tools for studying the structure of networks. Spectral methods are based on a first-order Markov chain derived from a random walk on the graph and thus they cannot take advantage of important higher-order network substructures such as triangles, cycles, and feed-forward loops. Here we propose a Tensor Spectral Clustering (TSC) algorithm that allows for modeling higher-order network structures in a graph partitioning framework. Our TSC algorithm allows the user to specify which higher-order network structures (cycles, feed-forward loops, etc.) should be preserved by the network clustering. Higher-order network structures of interest are represented using a tensor, which we then partition by developing a multilinear spectral method. Our framework can be applied to discovering layered flows in networks as well as graph anomaly detection, which we illustrate on synthetic networks. In directed networks, a higher-order structure of particular interest is the directed 3-cycle, which captures feedback loops in networks. We demonstrate that our TSC algorithm produces large partitions that cut fewer directed 3-cycles than standard spectral clustering algorithms.
Models, Statistics, and Rates of Binary Correlated Sources
Venue: arXiv cs.IT 2015
Year: 2015

This paper discusses and analyzes various models of binary correlated sources, which may be relevant in several distributed communication scenarios. These models are statistically characterized in terms of joint Probability Mass Function (PMF) and covariance. Closed-form expressions for the joint entropy of the sources are also presented. The asymptotic entropy rate for very large number of sources is shown to converge to a common limit for all the considered models. This fact generalizes recent results on the information-theoretic performance limit of communication schemes which exploit the correlation among sources at the receiver.
Using multiple-criteria methods to evaluate community partitions
Venue: arXiv cs.SI 2015
Year: 2015

Community detection is one of the most studied problems on complex networks. Although hundreds of methods have been proposed so far, there is still no universally accepted formal definition of what is a good community. As a consequence, the problem of the evaluation and the comparison of the quality of the solutions produced by these algorithms is still an open question, despite constant progress on the topic. In this article, we investigate how using a multi-criteria evaluation can solve some of the existing problems of community evaluation, in particular the question of multiple equally-relevant solutions of different granularity. After exploring several approaches, we introduce a new quality function, called MDensity, and propose a method that can be related both to a widely used community detection metric, the Modularity, and to the Precision/Recall approach, ubiquitous in information retrieval.
Dependability Tests Selection Based on the Concept of Layered Networks
Venue: arXiv cs.DC 2015
Year: 2015

Nowadays, the consequences of failure and downtime of distributed systems have become more and more severe. As an obvious solution, these systems incorporate protection mechanisms to tolerate faults that could cause systems failures and system dependability must be validated to ensure that protection mechanisms have been implemented correctly and the system will provide the desired level of reliable service. This paper presents a systematic approach for identifying (1) characteristic sets of critical system elements for dependability testing (single points of failure and recovery groups) based on the concept of layered networks; and (2) the most important combinations of components from each recovery group based on a combinatorial technique. Based on these combinations, we determine a set of test templates to be performed to demonstrate system dependability.
Measuring Accuracy of Automated Parsing and Categorization Tools and Processes in Digital Investigations
Venue: arXiv cs.CY 2015
Year: 2015

This work presents a method for the measurement of the accuracy of evidential artifact extraction and categorization tasks in digital forensic investigations. Instead of focusing on the measurement of accuracy and errors in the functions of digital forensic tools, this work proposes the application of information retrieval measurement techniques that allow the incorporation of errors introduced by tools and analysis processes. This method uses a `gold standard' that is the collection of evidential objects determined by a digital investigator from suspect data with an unknown ground truth. This work proposes that the accuracy of tools and investigation processes can be evaluated compared to the derived gold standard using common precision and recall values. Two example case studies are presented showing the measurement of the accuracy of automated analysis tools as compared to an in-depth analysis by an expert. It is shown that such measurement can allow investigators to determine changes in accuracy of their processes over time, and determine if such a change is caused by their tools or knowledge.
Measuring Creativity of Wikipedia Editors
Venue: arXiv cs.SI 2015
Year: 2015

Our paper explores contribution patterns of creativity and collaboration of Wikipedia editors as manifestations of social dynamics between the editors. We find support for existence of four socially constructed personas among the editors and difference in distribution of personas in articles of different qualities.
Extended Formulation for CSP that is Compact for Instances of Bounded Treewidth
Venue: arXiv cs.CC 2015
Year: 2015

In this paper we provide an extended formulation for the class of constraint satisfaction problems and prove that its size is polynomial for instances whose constraint graph has bounded treewidth. This implies new upper bounds on extension complexity of several important NP-hard problems on graphs of bounded treewidth.