OpenRaiser/Intern-Atlas huggingface dataset:
Convolutional Neural Networks learn compact local image descriptors
Venue: arXiv cs.CV 2013
Year: 2013

A standard deep convolutional neural network paired with a suitable loss function learns compact local image descriptors that perform comparably to state-of-the art approaches.
Semi-Supervised Information-Maximization Clustering
Venue: arXiv cs.LG 2013
Year: 2013

Semi-supervised clustering aims to introduce prior knowledge in the decision process of a clustering algorithm. In this paper, we propose a novel semi-supervised clustering algorithm based on the information-maximization principle. The proposed method is an extension of a previous unsupervised information-maximization clustering algorithm based on squared-loss mutual information to effectively incorporate must-links and cannot-links. The proposed method is computationally efficient because the clustering solution can be obtained analytically via eigendecomposition. Furthermore, the proposed method allows systematic optimization of tuning parameters such as the kernel width, given the degree of belief in the must-links and cannot-links. The usefulness of the proposed method is demonstrated through experiments.
Cooperative Synchronization in Wireless Networks
Venue: arXiv cs.DC 2013
Year: 2013

Synchronization is a key functionality in wireless network, enabling a wide variety of services. We consider a Bayesian inference framework whereby network nodes can achieve phase and skew synchronization in a fully distributed way. In particular, under the assumption of Gaussian measurement noise, we derive two message passing methods (belief propagation and mean field), analyze their convergence behavior, and perform a qualitative and quantitative comparison with a number of competing algorithms. We also show that both methods can be applied in networks with and without master nodes. Our performance results are complemented by, and compared with, the relevant Bayesian Cramér-Rao bounds.
Uniqueness of Tensor Decompositions with Applications to Polynomial Identifiability
Venue: arXiv cs.DS 2013
Year: 2013

We give a robust version of the celebrated result of Kruskal on the uniqueness of tensor decompositions: we prove that given a tensor whose decomposition satisfies a robust form of Kruskal's rank condition, it is possible to approximately recover the decomposition if the tensor is known up to a sufficiently small (inverse polynomial) error. Kruskal's theorem has found many applications in proving the identifiability of parameters for various latent variable models and mixture models such as Hidden Markov models, topic models etc. Our robust version immediately implies identifiability using only polynomially many samples in many of these settings. This polynomial identifiability is an essential first step towards efficient learning algorithms for these models. Recently, algorithms based on tensor decompositions have been used to estimate the parameters of various hidden variable models efficiently in special cases as long as they satisfy certain "non-degeneracy" properties. Our methods give a way to go beyond this non-degeneracy barrier, and establish polynomial identifiability of the parameters under much milder conditions. Given the importance of Kruskal's theorem in the tensor literature, we expect that this robust version will have several applications beyond the settings we explore in this work.
On Convexity of Error Rates in Digital Communications
Venue: arXiv cs.IT 2013
Year: 2013

Convexity properties of error rates of a class of decoders, including the ML/min-distance one as a special case, are studied for arbitrary constellations, bit mapping and coding. Earlier results obtained for the AWGN channel are extended to a wide class of noise densities, including unimodal and spherically-invariant noise. Under these broad conditions, symbol and bit error rates are shown to be convex functions of the SNR in the high-SNR regime with an explicitly-determined threshold, which depends only on the constellation dimensionality and minimum distance, thus enabling an application of the powerful tools of convex optimization to such digital communication systems in a rigorous way. It is the decreasing nature of the noise power density around the decision region boundaries that insures the convexity of symbol error rates in the general case. The known high/low SNR bounds of the convexity/concavity regions are tightened and no further improvement is shown to be possible in general. The high SNR bound fits closely into the channel coding theorem: all codes, including capacity-achieving ones, whose decision regions include the hardened noise spheres (from the noise sphere hardening argument in the channel coding theorem) satisfies this high SNR requirement and thus has convex error rates in both SNR and noise power. We conjecture that all capacity-achieving codes have convex error rates. Convexity properties in signal amplitude and noise power are also investigated. Some applications of the results are discussed. In particular, it is shown that fading is convexity-preserving and is never good in low dimensions under spherically-invariant noise, which may also include any linear diversity combining.
Image Compression By Embedding Five Modulus Method Into JPEG
Venue: arXiv cs.CV 2013
Year: 2013

The standard JPEG format is almost the optimum format in image compression. The compression ratio in JPEG sometimes reaches 30:1. The compression ratio of JPEG could be increased by embedding the Five Modulus Method (FMM) into the JPEG algorithm. The novel algorithm gives twice the time as the standard JPEG algorithm or more. The novel algorithm was called FJPEG (Five-JPEG). The quality of the reconstructed image after compression is approximately approaches the JPEG. Standard test images have been used to support and implement the suggested idea in this paper and the error metrics have been computed and compared with JPEG.
Pricing Public Goods for Private Sale
Venue: arXiv cs.GT 2013
Year: 2013

We consider the pricing problem faced by a seller who assigns a price to a good that confers its benefits not only to its buyers, but also to other individuals around them. For example, a snow-blower is potentially useful not only to the household that buys it, but also to others on the same street. Given that the seller is constrained to selling such a (locally) public good via individual private sales, how should he set his prices given the distribution of values held by the agents? We study this problem as a two-stage game. In the first stage, the seller chooses and announces a price for the product. In the second stage, the agents (each having a private value for the good) decide simultaneously whether or not they will buy the product. In the resulting game, which can exhibit a multiplicity of equilibria, agents must strategize about whether they will themselves purchase the good to receive its benefits. In the case of a fully public good (where all agents benefit whenever any agent purchases), we describe a pricing mechanism that is approximately revenue-optimal (up to a constant factor) when values are drawn from a regular distribution. We then study settings in which the good is only "locally" public: agents are arranged in a network and share benefits only with their neighbors. We describe a pricing method that approximately maximizes revenue, in the worst case over equilibria of agent behavior, for any $d$-regular network. Finally, we show that approximately optimal prices can be found for general networks in the special case that private values are drawn from a uniform distribution. We also discuss some barriers to extending these results to general networks and regular distributions.
Bubbles are rational
Venue: arXiv cs.GT 2013
Year: 2013

As we show using the notion of equilibrium in the theory of infinite sequential games, bubbles and escalations are rational for economic and environmental agents, who believe in an infinite world. This goes against a vision of a self regulating, wise and pacific economy in equilibrium. In other words, in this context, equilibrium is not a synonymous of stability. We attempt to draw from this statement methodological consequences and a new approach to economics. To the mindware of economic agents (a concept due to cognitive psychology) we propose to add coinduction to properly reason on infinite games. This way we refine the notion of rationality.
Clustering Unclustered Data: Unsupervised Binary Labeling of Two Datasets Having Different Class Balances
Venue: arXiv cs.LG 2013
Year: 2013

We consider the unsupervised learning problem of assigning labels to unlabeled data. A naive approach is to use clustering methods, but this works well only when data is properly clustered and each cluster corresponds to an underlying class. In this paper, we first show that this unsupervised labeling problem in balanced binary cases can be solved if two unlabeled datasets having different class balances are available. More specifically, estimation of the sign of the difference between probability densities of two unlabeled datasets gives the solution. We then introduce a new method to directly estimate the sign of the density difference without density estimation. Finally, we demonstrate the usefulness of the proposed method against several clustering methods on various toy problems and real-world datasets.
Convergence Analysis of Mixed Timescale Cross-Layer Stochastic Optimization
Venue: arXiv cs.SY 2013
Year: 2013

This paper considers a cross-layer optimization problem driven by multi-timescale stochastic exogenous processes in wireless communication networks. Due to the hierarchical information structure in a wireless network, a mixed timescale stochastic iterative algorithm is proposed to track the time-varying optimal solution of the cross-layer optimization problem, where the variables are partitioned into short-term controls updated in a faster timescale, and long-term controls updated in a slower timescale. We focus on establishing a convergence analysis framework for such multi-timescale algorithms, which is difficult due to the timescale separation of the algorithm and the time-varying nature of the exogenous processes. To cope with this challenge, we model the algorithm dynamics using stochastic differential equations (SDEs) and show that the study of the algorithm convergence is equivalent to the study of the stochastic stability of a virtual stochastic dynamic system (VSDS). Leveraging the techniques of Lyapunov stability, we derive a sufficient condition for the algorithm stability and a tracking error bound in terms of the parameters of the multi-timescale exogenous processes. Based on these results, an adaptive compensation algorithm is proposed to enhance the tracking performance. Finally, we illustrate the framework by an application example in wireless heterogeneous network.
An Optimal Algorithm for the Euclidean Bottleneck Full Steiner Tree Problem
Venue: arXiv cs.CG 2013
Year: 2013

Let $P$ and $S$ be two disjoint sets of $n$ and $m$ points in the plane, respectively. We consider the problem of computing a Steiner tree whose Steiner vertices belong to $S$, in which each point of $P$ is a leaf, and whose longest edge length is minimum. We present an algorithm that computes such a tree in $O((n+m)\log m)$ time, improving the previously best result by a logarithmic factor. We also prove a matching lower bound in the algebraic computation tree model.
MATAWS: A Multimodal Approach for Automatic WS Semantic Annotation
Venue: arXiv cs.SE 2013
Year: 2013

Many recent works aim at developing methods and tools for the processing of semantic Web services. In order to be properly tested, these tools must be applied to an appropriate benchmark, taking the form of a collection of semantic WS descriptions. However, all of the existing publicly available collections are limited by their size or their realism (use of randomly generated or resampled descriptions). Larger and realistic syntactic (WSDL) collections exist, but their semantic annotation requires a certain level of automation, due to the number of operations to be processed. In this article, we propose a fully automatic method to semantically annotate such large WS collections. Our approach is multimodal, in the sense it takes advantage of the latent semantics present not only in the parameter names, but also in the type names and structures. Concept-to-word association is performed by using Sigma, a mapping of WordNet to the SUMO ontology. After having described in details our annotation method, we apply it to the larger collection of real-world syntactic WS descriptions we could find, and assess its efficiency.
Automated generation of web server fingerprints
Venue: arXiv cs.CR 2013
Year: 2013

In this paper, we demonstrate that it is possible to automatically generate fingerprints for various web server types using multifactor Bayesian inference on randomly selected servers on the Internet, without building an a priori catalog of server features or behaviors. This makes it possible to conclusively study web server distribution without relying on reported (and variable) version strings. We gather data by sending a collection of specialized requests to 110,000 live web servers. Using only the server response codes, we then train an algorithm to successfully predict server types independently of the server version string. In the process, we note several distinguishing features of current web infrastructure.
The role of twitter in the life cycle of a scientific publication
Venue: arXiv cs.DL 2013
Year: 2013

Twitter is a micro-blogging social media platform for short messages that can have a long-term impact on how scientists create and publish ideas. We investigate the usefulness of twitter in the development and distribution of scientific knowledge. At the start of the life cycle of a scientific publication, twitter provides a large virtual department of colleagues that can help to rapidly generate, share and refine new ideas. As ideas become manuscripts, twitter can be used as an informal arena for the pre-review of works in progress. Finally, tweeting published findings can communicate research to a broad audience of other researchers, decision makers, journalists and the general public that can amplify the scientific and social impact of publications. However, there are limitations, largely surrounding issues of intellectual property and ownership, inclusiveness and misrepresentations of science sound bites. Nevertheless, we believe twitter is a useful social media tool that can provide a valuable contribution to scientific publishing in the 21st century.
On Topological Structure of Web Services Networks for Composition
Venue: arXiv cs.SE 2013
Year: 2013

In order to deal efficiently with the exponential growth of the Web services landscape in composition life cycle activities, it is necessary to have a clear view of its main features. As for many situations where there is a lot of interacting entities, the complex networks paradigm is an appropriate approach to analyze the interactions between the multitudes of Web services. In this paper, we present and investigate the main interactions between semantic Web services models from the complex network perspective. Results show that both parameter and operation networks exhibit the main characteristics of typical real-world complex networks such as the small-world property and an inhomogeneous degree distribution. These results yield valuable insight in order to develop composition search algorithms, to deal with security threat in the composition process and on the phenomena which characterize its evolution.
Probe and Adapt: Rate Adaptation for HTTP Video Streaming At Scale
Venue: arXiv cs.NI 2013
Year: 2013

Today, the technology for video streaming over the Internet is converging towards a paradigm named HTTP-based adaptive streaming (HAS). HAS comes with two unique flavors. First, by riding on top of HTTP/TCP, it leverages the network-friendly TCP to achieve firewall/NATS traversal and bandwidth sharing. Second, by pre-encoding and storing the video in a number of discrete bitrate levels, it introduces video bitrate adaptivity in a scalable way that the video encoding is excluded from the closed-loop adaptation. A conventional wisdom is that the TCP throughput observed by a HAS client indicates the available network bandwidth, thus can be used as a reliable reference for the video bitrate selection. We argue that this no longer holds true when HAS becomes a substantial fraction of the Internet traffic. We show that when multiple HAS clients compete at a network bottleneck, the presence of competing clients and the discrete nature of the video bitrates would together create confusion for a client to correctly perceive its fair-share bandwidth. Through analysis and real experiments, we demonstrate that this fundamental limitation would lead to, for example, video rate oscillation that negatively impacts the video watching experiences. We therefore argue that it is necessary to implement at the application layer a "probe-and-adapt" mechanism for HAS video rate adaptation, which is akin but orthogonal to the transport-layer network rate adaptation achieved by TCP. We present PANDA -- a client-side rate adaptation algorithm for HAS -- as an embodiment of this idea. Our testbed results show that compared to conventional algorithms, PANDA is able to reduce the instability of video rate by 60%, at a given risk of buffer underrun.
On Guarded Transformation In The Modal Mu-Calculus
Venue: arXiv cs.LO 2013
Year: 2013

Guarded normal form requires occurrences of fixpoint variables in a μ-calculus-formula to occur under the scope of a modal operator. The literature contains guarded transformations that effectively bring a μ-calculus-formula into guarded normal form. We show that the known guarded transformations can cause an exponential blowup in formula size, contrary to existing claims of polynomial behaviour. We also show that any polynomial guarded transformation for μ-calculus-formulas in the more relaxed vectorial form gives rise to a polynomial solution algorithm for parity games, the existence of which is an open problem. We also investigate transformations between the μ-calculus, vectorial form and hierarchical equation systems, which are an alternative syntax for alternating parity tree automata.
An Asymptotically Efficient Backlog Estimate for Dynamic Frame Aloha
Venue: arXiv cs.IT 2013
Year: 2013

In this paper we investigate backlog estimation procedures for Dynamic Frame Aloha (DFA) in Radio Frequency Identification (RFID) environment. In particular, we address the tag identification efficiency with any tag number $N$, including $N\rightarrow\infty$. Although in the latter case efficiency $e^{-1}$ is possible, none of the solution proposed in the literature has been shown to reach such value. We analyze Schoute's backlog estimate, which is very attractive for its simplicity, and formally show that its asymptotic efficiency is 0.311. Leveraging the analysis, we propose the Asymptotic Efficient backlog Estimate (AE$^2$) an improvement of the Schoute's backlog estimate, whose efficiency reaches $e^{-1}$ asymptotically. We further show that AE$^2$ can be optimized in order to present an efficiency very close to $e^{-1}$ for practically any value of the population size. We also evaluate the loss of efficiency when the frame size is constrained to be a power of two, as required by RFID standards for DFA, and theoretically show that the asymptotic efficiency becomes 0.356.
A Comment on Budach's Mouse-in-an-Octant Problem
Venue: arXiv cs.FL 2013
Year: 2013

Budach's Mouse-in-an-Octant Problem (attributed to Lothar Budach in a 1980 article by van Emde Boas and Karpinski) concerns the behaviour of a very simple finite-state machine ("the mouse") moving on the integer two-dimensional grid. Its decidability is apparently still open. This note sketches a proof that an extended version of the problem (a super-mouse) is undecidable.
On Comparison between Evolutionary Programming Network-based Learning and Novel Evolution Strategy Algorithm-based Learning
Venue: arXiv cs.NE 2013
Year: 2013

This paper presents two different evolutionary systems - Evolutionary Programming Network (EPNet) and Novel Evolutions Strategy (NES) Algorithm. EPNet does both training and architecture evolution simultaneously, whereas NES does a fixed network and only trains the network. Five mutation operators proposed in EPNet to reflect the emphasis on evolving ANNs behaviors. Close behavioral links between parents and their offspring are maintained by various mutations, such as partial training and node splitting. On the other hand, NES uses two new genetic operators - subpopulation-based max-mean arithmetical crossover and time-variant mutation. The above-mentioned two algorithms have been tested on a number of benchmark problems, such as the medical diagnosis problems (breast cancer, diabetes, and heart disease). The results and the comparison between them are also presented in this paper.
Endow a service-oriented architecture by a decisional aspect
Venue: arXiv cs.SE 2013
Year: 2013

Service oriented architecture is more and more used in the companies, The importance of the service orientation and its advantages with the information system of the company, confront us to a new challenge. It is primarily to ensure the decision aspect of the information system of company by adopting Services Orientated Architecture like support architecture. This engineering must ensure on the one hand the flexibility of the information system and on the oth-er hand, avoids the redevelopment of the system by the decisions request. In the actual position, several obstacles force the installation of the SOA within the company. It is basically a question of the lack of method to be implemented to define the services architecture within the information system of the company which takes account the decisional aspect. Moreover, there's no existing works which treat this challenge. On the basis of these notes, we are interested, in this paper, on the develop-ment of a three-dimensional new architecture for the integration of the deci-sional aspect in SOA architectures, so that they are used perfectly. The proposal takes support, mainly, on the use of a coupling MAS-SOA. To demonstrate the application of our proposition, we use two study cases: project management and Evapo-transpiration.
Efficient Estimation of the number of neighbours in Probabilistic K Nearest Neighbour Classification
Venue: arXiv cs.LG 2013
Year: 2013

Probabilistic k-nearest neighbour (PKNN) classification has been introduced to improve the performance of original k-nearest neighbour (KNN) classification algorithm by explicitly modelling uncertainty in the classification of each feature vector. However, an issue common to both KNN and PKNN is to select the optimal number of neighbours, $k$. The contribution of this paper is to incorporate the uncertainty in $k$ into the decision making, and in so doing use Bayesian model averaging to provide improved classification. Indeed the problem of assessing the uncertainty in $k$ can be viewed as one of statistical model selection which is one of the most important technical issues in the statistics and machine learning domain. In this paper, a new functional approximation algorithm is proposed to reconstruct the density of the model (order) without relying on time consuming Monte Carlo simulations. In addition, this algorithm avoids cross validation by adopting Bayesian framework. The performance of this algorithm yielded very good performance on several real experimental datasets.