OpenRaiser/Intern-Atlas huggingface dataset:
Multi-Hypothesis Compressed Video Sensing Technique
Venue: arXiv cs.MM 2014
Year: 2014

In this paper, we present a compressive sampling and Multi-Hypothesis (MH) reconstruction strategy for video sequences which has a rather simple encoder, while the decoding system is not that complex. We introduce a convex cost function that incorporates the MH technique with the sparsity constraint and the Tikhonov regularization. Consequently, we derive a new iterative algorithm based on these criteria. This algorithm surpasses its counterparts (Elasticnet and Tikhonov) in the recovery performance. Besides it is computationally much faster than the Elasticnet and comparable to the Tikhonov. Our extensive simulation results confirm these claims.
Nonclassical polynomials as a barrier to polynomial lower bounds
Venue: arXiv cs.CC 2014
Year: 2014

The problem of constructing explicit functions which cannot be approximated by low degree polynomials has been extensively studied in computational complexity, motivated by applications in circuit lower bounds, pseudo-randomness, constructions of Ramsey graphs and locally decodable codes. Still, most of the known lower bounds become trivial for polynomials of super-logarithmic degree. Here, we suggest a new barrier explaining this phenomenon. We show that many of the existing lower bound proof techniques extend to nonclassical polynomials, an extension of classical polynomials which arose in higher order Fourier analysis. Moreover, these techniques are tight for nonclassical polynomials of logarithmic degree.
A representation of robotic behaviors using component port arbitration
Venue: arXiv cs.RO 2014
Year: 2014

Developing applications considering reactiveness, scalability and re-usability has always been at the center of attention of robotic researchers. Behavior-based architectures have been proposed as a programming paradigm to develop robust and complex behaviors as integration of simpler modules whose activities are directly modulated by sensory feedback or input from other models. The design of behavior based systems, however, becomes increasingly difficult as the complexity of the application grows. This article proposes an approach for modeling and coordinating behaviors in distributed architectures based on port arbitration which clearly separates representation of the behaviors from the composition of the software components. Therefore, based on different behavioral descriptions, the same software components can be reused to implement different applications.
Functional Automata - Formal Languages for Computer Science Students
Venue: arXiv cs.FL 2014
Year: 2014

An introductory formal languages course exposes advanced undergraduate and early graduate students to automata theory, grammars, constructive proofs, computability, and decidability. Programming students find these topics to be challenging or, in many cases, overwhelming and on the fringe of Computer Science. The existence of this perception is not completely absurd since students are asked to design and prove correct machines and grammars without being able to experiment nor get immediate feedback, which is essential in a learning context. This article puts forth the thesis that the theory of computation ought to be taught using tools for actually building computations. It describes the implementation and the classroom use of a library, FSM, designed to provide students with the opportunity to experiment and test their designs using state machines, grammars, and regular expressions. Students are able to perform random testing before proceeding with a formal proof of correctness. That is, students can test their designs much like they do in a programming course. In addition, the library easily allows students to implement the algorithms they develop as part of the constructive proofs they write. Providing students with this ability ought to be a new trend in the formal languages classroom.
New Bounds for the Garden-Hose Model
Venue: arXiv cs.CC 2014
Year: 2014

We show new results about the garden-hose model. Our main results include improved lower bounds based on non-deterministic communication complexity (leading to the previously unknown $Θ(n)$ bounds for Inner Product mod 2 and Disjointness), as well as an $O(n\cdot \log^3 n)$ upper bound for the Distributed Majority function (previously conjectured to have quadratic complexity). We show an efficient simulation of formulae made of AND, OR, XOR gates in the garden-hose model, which implies that lower bounds on the garden-hose complexity $GH(f)$ of the order $Ω(n^{2+ε})$ will be hard to obtain for explicit functions. Furthermore we study a time-bounded variant of the model, in which even modest savings in time can lead to exponential lower bounds on the size of garden-hose protocols.
Discovering beautiful attributes for aesthetic image analysis
Venue: arXiv cs.CV 2014
Year: 2014

Aesthetic image analysis is the study and assessment of the aesthetic properties of images. Current computational approaches to aesthetic image analysis either provide accurate or interpretable results. To obtain both accuracy and interpretability by humans, we advocate the use of learned and nameable visual attributes as mid-level features. For this purpose, we propose to discover and learn the visual appearance of attributes automatically, using a recently introduced database, called AVA, which contains more than 250,000 images together with their aesthetic scores and textual comments given by photography enthusiasts. We provide a detailed analysis of these annotations as well as the context in which they were given. We then describe how these three key components of AVA - images, scores, and comments - can be effectively leveraged to learn visual attributes. Lastly, we show that these learned attributes can be successfully used in three applications: aesthetic quality prediction, image tagging and retrieval.
Network connectivity in non-convex domains with reflections
Venue: arXiv cs.NI 2014
Year: 2014

Recent research has demonstrated the importance of boundary effects on the overall connection probability of wireless networks but has largely focused on convex deployment regions. We consider here a scenario of practical importance to wireless communications, in which one or more nodes are located outside the convex space where the remaining nodes reside. We call these `external nodes', and assume that they play some essential role in the macro network functionality e.g. a gateway to a dense self-contained mesh network cloud. Conventional approaches with the underlying assumption of only line-of-sight (LOS) or direct connections between nodes, fail to provide the correct analysis for such a network setup. To this end we present a novel analytical framework that accommodates for the non-convexity of the domain and explicitly considers the effects of non-LOS nodes through reflections from the domain boundaries. We obtain analytical expressions in 2D and 3D which are confirmed numerically for Rician channel fading statistics and discuss possible extensions and applications.
Restricting the h-index to a citation time window: A case study of a timed Hirsch index
Venue: arXiv cs.DL 2014
Year: 2014

The h-index has been shown to increase in many cases mostly because of citations to rather old publications. This inertia can be circumvented by restricting the evaluation to a citation time window. Here I report results of an empirical study analyzing the evolution of the thus defined timed h-index in dependence on the length of the citation time window.
Analysis of Optimal Recombination in Genetic Algorithm for a Scheduling Problem with Setups
Venue: arXiv cs.NE 2014
Year: 2014

In this paper, we perform an experimental study of optimal recombination operator for makespan minimization problem on single machine with sequence-dependent setup times ($1|s_{vu}|C_{\max}$). The computational experiment on benchmark problems from TSPLIB library indicates practical applicability of optimal recombination in crossover operator of genetic algorithm for $1|s_{vu}|C_{\max}$.
A Multi-criteria neutrosophic group decision making metod based TOPSIS for supplier selection
Venue: arXiv cs.AI 2014
Year: 2014

The process of multiple criteria decision making (MCDM) is of determining the best choice among all of the probable alternatives. The problem of supplier selection on which decision maker has usually vague and imprecise knowledge is a typical example of multi criteria group decision-making problem. The conventional crisp techniques has not much effective for solving MCDM problems because of imprecise or fuzziness nature of the linguistic assessments. To find the exact values for MCDM problems is both difficult and impossible in more cases in real world. So, it is more reasonable to consider the values of alternatives according to the criteria as single valued neutrosophic sets (SVNS). This paper deal with the technique for order preference by similarity to ideal solution (TOPSIS) approach and extend the TOPSIS method to MCDM problem with single valued neutrosophic information. The value of each alternative and the weight of each criterion are characterized by single valued neutrosophic numbers. Here, the importance of criteria and alternatives is identified by aggregating individual opinions of decision makers (DMs) via single valued neutrosophic weighted averaging (IFWA) operator. The proposed method is, easy use, precise and practical for solving MCDM problem with single valued neutrosophic data. Finally, to show the applicability of the developed method, a numerical experiment for supplier choice is given as an application of single valued neutrosophic TOPSIS method at end of this paper.
How many queries are needed to distinguish a truncated random permutation from a random function?
Venue: arXiv cs.CR 2014
Year: 2014

An oracle chooses a function $f$ from the set of $n$ bits strings to itself, which is either a randomly chosen permutation or a randomly chosen function. When queried by an $n$-bit string $w$, the oracle computes $f(w)$, truncates the $m$ last bits, and returns only the first $n-m$ bits of $f(w)$. How many queries does a querying adversary need to submit in order to distinguish the truncated permutation from the (truncated) function? In 1998, Hall et al. showed an algorithm for determining (with high probability) whether or not $f$ is a permutation, using $O(2^{\frac{m+n}{2}})$ queries. They also showed that if $m < n/7$, a smaller number of queries will not suffice. For $m > n/7$, their method gives a weaker bound. In this note, we first show how a modification of the approximation method used by Hall et al. can solve the problem completely. It extends the result to practically any $m$, showing that $Ω(2^{\frac{m+n}{2}})$ queries are needed to get a non-negligible distinguishing advantage. However, more surprisingly, a better bound for the distinguishing advantage can be obtained from a result of Stam published, in a different context, already in 1978. We also show that, at least in some cases, Stam's bound is tight.
Application of Topic Models to Judgments from Public Procurement Domain
Venue: arXiv cs.CL 2014
Year: 2014

In this work, automatic analysis of themes contained in a large corpora of judgments from public procurement domain is performed. The employed technique is unsupervised latent Dirichlet allocation (LDA). In addition, it is proposed, to use LDA in conjunction with recently developed method of unsupervised keyword extraction. Such an approach improves the interpretability of the automatically obtained topics and allows for better computational performance. The described analysis illustrates a potential of the method in detecting recurring themes and discovering temporal trends in lodged contract appeals. These results may be in future applied to improve information retrieval from repositories of legal texts or as auxiliary material for legal analyses carried out by human experts.
Testing MCMC code
Venue: arXiv cs.SE 2014
Year: 2014

Markov Chain Monte Carlo (MCMC) algorithms are a workhorse of probabilistic modeling and inference, but are difficult to debug, and are prone to silent failure if implemented naively. We outline several strategies for testing the correctness of MCMC algorithms. Specifically, we advocate writing code in a modular way, where conditional probability calculations are kept separate from the logic of the sampler. We discuss strategies for both unit testing and integration testing. As a running example, we show how a Python implementation of Gibbs sampling for a mixture of Gaussians model can be tested.
Refining the Semantics of Social Influence
Venue: arXiv cs.SI 2014
Year: 2014

With the proliferation of network data, researchers are increasingly focusing on questions investigating phenomena occurring on networks. This often includes analysis of peer-effects, i.e., how the connections of an individual affect that individual's behavior. This type of influence is not limited to direct connections of an individual (such as friends), but also to individuals that are connected through longer paths (for example, friends of friends, or friends of friends of friends). In this work, we identify an ambiguity in the definition of what constitutes the extended neighborhood of an individual. This ambiguity gives rise to different semantics and supports different types of underlying phenomena. We present experimental results, both on synthetic and real networks, that quantify differences among the sets of extended neighbors under different semantics. Finally, we provide experimental evidence that demonstrates how the use of different semantics affects model selection.
The switch Markov chain for sampling irregular graphs
Venue: arXiv cs.DS 2014
Year: 2014

The problem of efficiently sampling from a set of(undirected) graphs with a given degree sequence has many applications. One approach to this problem uses a simple Markov chain, which we call the switch chain, to perform the sampling. The switch chain is known to be rapidly mixing for regular degree sequences. We prove that the switch chain is rapidly mixing for any degree sequence with minimum degree at least 1 and with maximum degree $d_{\max}$ which satisfies $3\leq d_{\max}\leq \frac{1}{4}\, \sqrt{M}$, where $M$ is the sum of the degrees. The mixing time bound obtained is only an order of $n$ larger than that established in the regular case, where $n$ is the number of vertices.
Reduction and Fixed Points of Boolean Networks and Linear Network Coding Solvability
Venue: arXiv cs.IT 2014
Year: 2014

Linear network coding transmits data through networks by letting the intermediate nodes combine the messages they receive and forward the combinations towards their destinations. The solvability problem asks whether the demands of all the destinations can be simultaneously satisfied by using linear network coding. The guessing number approach converts this problem to determining the number of fixed points of coding functions $f:A^n\to A^n$ over a finite alphabet $A$ (usually referred to as Boolean networks if $A = \{0,1\}$) with a given interaction graph, that describes which local functions depend on which variables. In this paper, we generalise the so-called reduction of coding functions in order to eliminate variables. We then determine the maximum number of fixed points of a fully reduced coding function, whose interaction graph has a loop on every vertex. Since the reduction preserves the number of fixed points, we then apply these ideas and results to obtain four main results on the linear network coding solvability problem. First, we prove that non-decreasing coding functions cannot solve any more instances than routing already does. Second, we show that triangle-free undirected graphs are linearly solvable if and only if they are solvable by routing. This is the first classification result for the linear network coding solvability problem. Third, we exhibit a new class of non-linearly solvable graphs. Fourth, we determine large classes of strictly linearly solvable graphs.
Word Network Topic Model: A Simple but General Solution for Short and Imbalanced Texts
Venue: arXiv cs.CL 2014
Year: 2014

The short text has been the prevalent format for information of Internet in recent decades, especially with the development of online social media, whose millions of users generate a vast number of short messages everyday. Although sophisticated signals delivered by the short text make it a promising source for topic modeling, its extreme sparsity and imbalance brings unprecedented challenges to conventional topic models like LDA and its variants. Aiming at presenting a simple but general solution for topic modeling in short texts, we present a word co-occurrence network based model named WNTM to tackle the sparsity and imbalance simultaneously. Different from previous approaches, WNTM models the distribution over topics for each word instead of learning topics for each document, which successfully enhance the semantic density of data space without importing too much time or space complexity. Meanwhile, the rich contextual information preserved in the word-word space also guarantees its sensitivity in identifying rare topics with convincing quality. Furthermore, employing the same Gibbs sampling with LDA makes WNTM easily to be extended to various application scenarios. Extensive validations on both short and normal texts testify the outperformance of WNTM as compared to baseline methods. And finally we also demonstrate its potential in precisely discovering newly emerging topics or unexpected events in Weibo at pretty early stages.
Full-reference image quality assessment by combining global and local distortion measures
Venue: arXiv cs.CV 2014
Year: 2014

Full-reference image quality assessment (FR-IQA) techniques compare a reference and a distorted/test image and predict the perceptual quality of the test image in terms of a scalar value representing an objective score. The evaluation of FR-IQA techniques is carried out by comparing the objective scores from the techniques with the subjective scores (obtained from human observers) provided in the image databases used for the IQA. Hence, we reasonably assume that the goal of a human observer is to rate the distortion present in the test image. The goal oriented tasks are processed by the human visual system (HVS) through top-down processing which actively searches for local distortions driven by the goal. Therefore local distortion measures in an image are important for the top-down processing. At the same time, bottom-up processing also takes place signifying spontaneous visual functions in the HVS. To account for this, global perceptual features can be used. Therefore, we hypothesize that the resulting objective score for an image can be derived from the combination of local and global distortion measures calculated from the reference and test images. We calculate the local distortion by measuring the local correlation differences from the gradient and contrast information. For global distortion, dissimilarity of the saliency maps computed from a bottom-up model of saliency is used. The motivation behind the proposed approach has been thoroughly discussed, accompanied by an intuitive analysis. Finally, experiments are conducted in six benchmark databases suggesting the effectiveness of the proposed approach that achieves competitive performance with the state-of-the-art methods providing an improvement in the overall performance.
Towards a constructive multilayer perceptron for regression task using non-parametric clustering. A case study of Photo-Z redshift reconstruction
Venue: arXiv cs.NE 2014
Year: 2014

The choice of architecture of artificial neuron network (ANN) is still a challenging task that users face every time. It greatly affects the accuracy of the built network. In fact there is no optimal method that is applicable to various implementations at the same time. In this paper we propose a method to construct ANN based on clustering, that resolves the problems of random and ad hoc approaches for multilayer ANN architecture. Our method can be applied to regression problems. Experimental results obtained with different datasets, reveals the efficiency of our method.
From Co- Toward Multi-Simulation of Smart Grids based on HLA and FMI Standards
Venue: arXiv cs.NI 2014
Year: 2014

In this article, a multi-simulation model is proposed to measure the performance of all Smart Grid perspectives as defined in the IEEE P2030 standard. As a preliminary implementation, a novel information technology (IT) and communication multi-simulator is developed following an High Level Architecture (HLA). To illustrate the usefulness of such a multi-simulator, a case study of a distribution network operation application is presented using real-world topology configurations with realistic communication traffic based on IEC 61850. The multi-simulator allows to quantify, in terms of communication delay and system reliability, the impacts of aggregating all traffic on a low-capacity wireless link based on Digital Mobile Radio (DMR) when a Long Term Evolution (LTE) network failure occurs. The case study illustrates that such a multi-simulator can be used to experiment new smart grid mechanisms and verify their impacts on all smart grid perspectives in an automated manner. Even more importantly, multi-simulation can prevent problems before modifying/upgrading a smart grid and thus potentially reduce utility costs.
On the Complexity of Nash Equilibria in Anonymous Games
Venue: arXiv cs.GT 2014
Year: 2014

We show that the problem of finding an ε-approximate Nash equilibrium in an anonymous game with seven pure strategies is complete in PPAD, when the approximation parameter ε is exponentially small in the number of players.
Towards Open World Recognition
Venue: arXiv cs.CV 2014
Year: 2014

With the of advent rich classification models and high computational power visual recognition systems have found many operational applications. Recognition in the real world poses multiple challenges that are not apparent in controlled lab environments. The datasets are dynamic and novel categories must be continuously detected and then added. At prediction time, a trained system has to deal with myriad unseen categories. Operational systems require minimum down time, even to learn. To handle these operational issues, we present the problem of Open World recognition and formally define it. We prove that thresholding sums of monotonically decreasing functions of distances in linearly transformed feature space can balance "open space risk" and empirical risk. Our theory extends existing algorithms for open world recognition. We present a protocol for evaluation of open world recognition systems. We present the Nearest Non-Outlier (NNO) algorithm which evolves model efficiently, adding object categories incrementally while detecting outliers and managing open space risk. We perform experiments on the ImageNet dataset with 1.2M+ images to validate the effectiveness of our method on large scale visual recognition tasks. NNO consistently yields superior results on open world recognition.