OpenRaiser/Intern-Atlas huggingface dataset:
Parsimonious Labeling
Venue: arXiv cs.CV 2015
Year: 2015

We propose a new family of discrete energy minimization problems, which we call parsimonious labeling. Specifically, our energy functional consists of unary potentials and high-order clique potentials. While the unary potentials are arbitrary, the clique potentials are proportional to the {\em diversity} of set of the unique labels assigned to the clique. Intuitively, our energy functional encourages the labeling to be parsimonious, that is, use as few labels as possible. This in turn allows us to capture useful cues for important computer vision applications such as stereo correspondence and image denoising. Furthermore, we propose an efficient graph-cuts based algorithm for the parsimonious labeling problem that provides strong theoretical guarantees on the quality of the solution. Our algorithm consists of three steps. First, we approximate a given diversity using a mixture of a novel hierarchical $P^n$ Potts model. Second, we use a divide-and-conquer approach for each mixture component, where each subproblem is solved using an effficient $α$-expansion algorithm. This provides us with a small number of putative labelings, one for each mixture component. Third, we choose the best putative labeling in terms of the energy value. Using both sythetic and standard real datasets, we show that our algorithm significantly outperforms other graph-cuts based approaches.
Combining Models of Approximation with Partial Learning
Venue: arXiv cs.LG 2015
Year: 2015

In Gold's framework of inductive inference, the model of partial learning requires the learner to output exactly one correct index for the target object and only the target object infinitely often. Since infinitely many of the learner's hypotheses may be incorrect, it is not obvious whether a partial learner can be modifed to "approximate" the target object. Fulk and Jain (Approximate inference and scientific method. Information and Computation 114(2):179--191, 1994) introduced a model of approximate learning of recursive functions. The present work extends their research and solves an open problem of Fulk and Jain by showing that there is a learner which approximates and partially identifies every recursive function by outputting a sequence of hypotheses which, in addition, are also almost all finite variants of the target function. The subsequent study is dedicated to the question how these findings generalise to the learning of r.e. languages from positive data. Here three variants of approximate learning will be introduced and investigated with respect to the question whether they can be combined with partial learning. Following the line of Fulk and Jain's research, further investigations provide conditions under which partial language learners can eventually output only finite variants of the target language. The combinabilities of other partial learning criteria will also be briefly studied.
Compressive Hyperspectral Imaging via Approximate Message Passing
Venue: arXiv cs.IT 2015
Year: 2015

We consider a compressive hyperspectral imaging reconstruction problem, where three-dimensional spatio-spectral information about a scene is sensed by a coded aperture snapshot spectral imager (CASSI). The CASSI imaging process can be modeled as suppressing three-dimensional coded and shifted voxels and projecting these onto a two-dimensional plane, such that the number of acquired measurements is greatly reduced. On the other hand, because the measurements are highly compressive, the reconstruction process becomes challenging. We previously proposed a compressive imaging reconstruction algorithm that is applied to two-dimensional images based on the approximate message passing (AMP) framework. AMP is an iterative algorithm that can be used in signal and image reconstruction by performing denoising at each iteration. We employed an adaptive Wiener filter as the image denoiser, and called our algorithm "AMP-Wiener." In this paper, we extend AMP-Wiener to three-dimensional hyperspectral image reconstruction, and call it "AMP-3D-Wiener." Applying the AMP framework to the CASSI system is challenging, because the matrix that models the CASSI system is highly sparse, and such a matrix is not suitable to AMP and makes it difficult for AMP to converge. Therefore, we modify the adaptive Wiener filter and employ a technique called damping to solve for the divergence issue of AMP. Our approach is applied in nature, and the numerical experiments show that AMP-3D-Wiener outperforms existing widely-used algorithms such as gradient projection for sparse reconstruction (GPSR) and two-step iterative shrinkage/thresholding (TwIST) given a similar amount of runtime. Moreover, in contrast to GPSR and TwIST, AMP-3D-Wiener need not tune any parameters, which simplifies the reconstruction process.
The New War Correspondents: the Rise of Civic Media Curation in Urban Warfare
Venue: arXiv cs.CY 2015
Year: 2015

In this paper we examine the information sharing practices of people living in cities amid armed conflict. We describe the volume and frequency of microblogging activity on Twitter from four cities afflicted by the Mexican Drug War, showing how citizens use social media to alert one another and to comment on the violence that plagues their communities. We then investigate the emergence of civic media "curators," individuals who act as "war correspondents" by aggregating and disseminating information to large numbers of people on social media. We conclude by outlining the implications of our observations for the design of civic media systems in wartime.
Two-dimensional Burst Error Correcting Code using Finite Field Fourier Transforms
Venue: arXiv cs.IT 2015
Year: 2015

We construct two-dimensional codes for correcting burst errors using the finite field Fourier transform. The encoding procedure is performed in the transformed domain using the conjugacy property of the finite field Fourier transform. The decoding procedure is also done in the transformed domain. Our code is capable of correcting multiple non-overlapping occurrence of different error patterns from a finite set of predefined error patterns. The code construction is useful for encoding data in two dimensions for application in data storage and bar codes
Welfare Maximization with Deferred Acceptance Auctions in Reallocation Problems
Venue: arXiv cs.GT 2015
Year: 2015

We design approximate weakly group strategy-proof mechanisms for resource reallocation problems using Milgrom and Segal's deferred acceptance auction framework: the radio spectrum and network bandwidth reallocation problems in the procurement auction setting and the cost minimization problem with set cover constraints in the selling auction setting. Our deferred acceptance auctions are derived from simple greedy algorithms for the underlying optimization problems and guarantee approximately optimal social welfare (cost) of the agents retaining their rights (contracts). In the reallocation problems, we design procurement auctions to purchase agents' broadcast/access rights to free up some of the resources such that the unpurchased rights can still be exercised with respect to the remaining resources. In the cost minimization problem, we design a selling auction to sell early termination rights to agents with existing contracts such that some minimal constraints are still satisfied with remaining contracts. In these problems, while the "allocated" agents transact, exchanging rights and payments, the objective and feasibility constraints are on the "rejected" agents.
A Simple Algorithm for Maximum Margin Classification, Revisited
Venue: arXiv cs.LG 2015
Year: 2015

In this note, we revisit the algorithm of Har-Peled et. al. [HRZ07] for computing a linear maximum margin classifier. Our presentation is self contained, and the algorithm itself is slightly simpler than the original algorithm. The algorithm itself is a simple Perceptron like iterative algorithm. For more details and background, the reader is referred to the original paper.
Beyond Semantic Image Segmentation : Exploring Efficient Inference in Video
Venue: arXiv cs.CV 2015
Year: 2015

We explore the efficiency of the CRF inference module beyond image level semantic segmentation. The key idea is to combine the best of two worlds of semantic co-labeling and exploiting more expressive models. Similar to [Alvarez14] our formulation enables us perform inference over ten thousand images within seconds. On the other hand, it can handle higher-order clique potentials similar to [vineet2014] in terms of region-level label consistency and context in terms of co-occurrences. We follow the mean-field updates for higher order potentials similar to [vineet2014] and extend the spatial smoothness and appearance kernels [DenseCRF13] to address video data inspired by [Alvarez14]; thus making the system amenable to perform video semantic segmentation most effectively.
Analysis of Handover Failures in Heterogeneous Networks with Fading
Venue: arXiv cs.NI 2015
Year: 2015

The handover process is one of the most critical functions in a cellular network, and is in charge of maintaining seamless connectivity of user equipments (UEs) across multiple cells. It is usually based on signal measurements from the neighboring base stations (BSs), and it is adversely affected by the time and frequency selectivity of the radio propagation channel. In this paper, we introduce a new model for analyzing handover performance in heterogeneous networks (HetNets) as a function of vehicular user velocity, cell size, and mobility management parameters. In order to investigate the impact of shadowing and fading on handover performance, we extract relevant statistics obtained from a 3rd Generation Partnership Project (3GPP)-compliant HetNet simulator, and subsequently, we integrate these statistics into our analytical model to analyze handover failure probability under fluctuating channel conditions. Computer simulations validate the analytical findings, which show that fading can significantly degrade the handover performance in HetNets with vehicular users.
Languages for Mobile Agents
Venue: arXiv cs.PL 2015
Year: 2015

Mobile agents represent a new model for network computing. Many different languages have been used to implement mobile agents. The characteristics that make a language useful for writing mobile agents are: (1) their support of agent migration, (2) their support for agent-to-agent communication, (3) how they allow agents to interact with local resources, (4) security mechanisms, (5) execution efficiency, (6) language implementation across multiple platforms, and (7) the language's ease of programming of the tasks mobile agents perform.
Allocation de ressources dans un r{é}seau de radio cognitive en utilisant JADE
Venue: arXiv cs.NI 2015
Year: 2015

In this work, we are interested in the negotiation between several PU and several SU in a cognitive radio context by using multi-agent systems. So, we have implemented PU coalitions (CPU) and SU coalitions (CSU). We also used the multi-criteria decision (TOPSIS algorithm) to best meet the needs of SU.Management by coalitions and the aggregation technique that we have used in this context significantly reduce the number of messages exchanged in the network. Processing negotiations simultaneously by several CSU minimizes response time side SU.
The Web for Under-Powered Mobile Devices: Lessons learned from Google Glass
Venue: arXiv cs.HC 2015
Year: 2015

This paper examines some of the potential challenges associated with enabling a seamless web experience on underpowered mobile devices such as Google Glass from the perspective of web content providers, device, and the network. We conducted experiments to study the impact of webpage complexity, individual web components and different application layer protocols while accessing webpages on the performance of Glass browser, by measuring webpage load time, temperature variation and power consumption and compare it to a smartphone. Our findings suggest that (a) performance of Glass compared to a smartphone in terms of power consumption and webpage load time deteriorates with increasing webpage complexity (b) execution time for popular JavaScript benchmarks is about 3-8 times higher on Glass compared to a smartphone, (c) WebP is more energy efficient image format than JPEG and PNG, and (d) seven out of 50 websites studied are optimized for content delivery to Glass.
Path-Fault-Tolerant Approximate Shortest-Path Trees
Venue: arXiv cs.DS 2015
Year: 2015

Let $G=(V,E)$ be an $n$-nodes non-negatively real-weighted undirected graph. In this paper we show how to enrich a {\em single-source shortest-path tree} (SPT) of $G$ with a \emph{sparse} set of \emph{auxiliary} edges selected from $E$, in order to create a structure which tolerates effectively a \emph{path failure} in the SPT. This consists of a simultaneous fault of a set $F$ of at most $f$ adjacent edges along a shortest path emanating from the source, and it is recognized as one of the most frequent disruption in an SPT. We show that, for any integer parameter $k \geq 1$, it is possible to provide a very sparse (i.e., of size $O(kn\cdot f^{1+1/k})$) auxiliary structure that carefully approximates (i.e., within a stretch factor of $(2k-1)(2|F|+1)$) the true shortest paths from the source during the lifetime of the failure. Moreover, we show that our construction can be further refined to get a stretch factor of $3$ and a size of $O(n \log n)$ for the special case $f=2$, and that it can be converted into a very efficient \emph{approximate-distance sensitivity oracle}, that allows to quickly (even in optimal time, if $k=1$) reconstruct the shortest paths (w.r.t. our structure) from the source after a path failure, thus permitting to perform promptly the needed rerouting operations. Our structure compares favorably with previous known solutions, as we discuss in the paper, and moreover it is also very effective in practice, as we assess through a large set of experiments.
Learning Tractable Probabilistic Models for Fault Localization
Venue: arXiv cs.SE 2015
Year: 2015

In recent years, several probabilistic techniques have been applied to various debugging problems. However, most existing probabilistic debugging systems use relatively simple statistical models, and fail to generalize across multiple programs. In this work, we propose Tractable Fault Localization Models (TFLMs) that can be learned from data, and probabilistically infer the location of the bug. While most previous statistical debugging methods generalize over many executions of a single program, TFLMs are trained on a corpus of previously seen buggy programs, and learn to identify recurring patterns of bugs. Widely-used fault localization techniques such as TARANTULA evaluate the suspiciousness of each line in isolation; in contrast, a TFLM defines a joint probability distribution over buggy indicator variables for each line. Joint distributions with rich dependency structure are often computationally intractable; TFLMs avoid this by exploiting recent developments in tractable probabilistic models (specifically, Relational SPNs). Further, TFLMs can incorporate additional sources of information, including coverage-based features such as TARANTULA. We evaluate the fault localization performance of TFLMs that include TARANTULA scores as features in the probabilistic model. Our study shows that the learned TFLMs isolate bugs more effectively than previous statistical methods or using TARANTULA directly.
Typing Regular Path Query Languages for Data Graphs
Venue: arXiv cs.DB 2015
Year: 2015

Regular path query languages for data graphs are essentially \emph{untyped}. The lack of type information greatly limits the optimization opportunities for query engines and makes application development more complex. In this paper we discuss a simple, yet expressive, schema language for edge-labelled data graphs. This schema language is, then, used to define a query type inference approach with good precision properties.
DART-MPI: An MPI-based Implementation of a PGAS Runtime System
Venue: arXiv cs.DC 2015
Year: 2015

A Partitioned Global Address Space (PGAS) approach treats a distributed system as if the memory were shared on a global level. Given such a global view on memory, the user may program applications very much like shared memory systems. This greatly simplifies the tasks of developing parallel applications, because no explicit communication has to be specified in the program for data exchange between different computing nodes. In this paper we present DART, a runtime environment, which implements the PGAS paradigm on large-scale high-performance computing clusters. A specific feature of our implementation is the use of one-sided communication of the Message Passing Interface (MPI) version 3 (i.e. MPI-3) as the underlying communication substrate. We evaluated the performance of the implementation with several low-level kernels in order to determine overheads and limitations in comparison to the underlying MPI-3.
Energy-saving Resource Allocation by Exploiting the Context Information
Venue: arXiv cs.IT 2015
Year: 2015

Improving energy efficiency of wireless systems by exploiting the context information has received attention recently as the smart phone market keeps expanding. In this paper, we devise energy-saving resource allocation policy for multiple base stations serving non-real-time traffic by exploiting three levels of context information, where the background traffic is assumed to occupy partial resources. Based on the solution from a total energy minimization problem with perfect future information,a context-aware BS sleeping, scheduling and power allocation policy is proposed by estimating the required future information with three levels of context information. Simulation results show that our policy provides significant gains over those without exploiting any context information. Moreover, it is seen that different levels of context information play different roles in saving energy and reducing outage in transmission.
Clustering Network Layers With the Strata Multilayer Stochastic Block Model
Venue: arXiv cs.SI 2015
Year: 2015

Multilayer networks are a useful data structure for simultaneously capturing multiple types of relationships between a set of nodes. In such networks, each relational definition gives rise to a layer. While each layer provides its own set of information, community structure across layers can be collectively utilized to discover and quantify underlying relational patterns between nodes. To concisely extract information from a multilayer network, we propose to identify and combine sets of layers with meaningful similarities in community structure. In this paper, we describe the "strata multilayer stochastic block model'' (sMLSBM), a probabilistic model for multilayer community structure. The central extension of the model is that there exist groups of layers, called "strata'', which are defined such that all layers in a given stratum have community structure described by a common stochastic block model (SBM). That is, layers in a stratum exhibit similar node-to-community assignments and SBM probability parameters. Fitting the sMLSBM to a multilayer network provides a joint clustering that yields node-to-community and layer-to-stratum assignments, which cooperatively aid one another during inference. We describe an algorithm for separating layers into their appropriate strata and an inference technique for estimating the SBM parameters for each stratum. We demonstrate our method using synthetic networks and a multilayer network inferred from data collected in the Human Microbiome Project.
Hindi to English Transfer Based Machine Translation System
Venue: arXiv cs.CL 2015
Year: 2015

In large societies like India there is a huge demand to convert one human language into another. Lots of work has been done in this area. Many transfer based MTS have developed for English to other languages, as MANTRA CDAC Pune, MATRA CDAC Pune, SHAKTI IISc Bangalore and IIIT Hyderabad. Still there is a little work done for Hindi to other languages. Currently we are working on it. In this paper we focus on designing a system, that translate the document from Hindi to English by using transfer based approach. This system takes an input text check its structure through parsing. Reordering rules are used to generate the text in target language. It is better than Corpus Based MTS because Corpus Based MTS require large amount of word aligned data for translation that is not available for many languages while Transfer Based MTS requires only knowledge of both the languages(source language and target language) to make transfer rules. We get correct translation for simple assertive sentences and almost correct for complex and compound sentences.
Lower Bounds by Birkhoff Interpolation
Venue: arXiv cs.CC 2015
Year: 2015

In this paper we give lower bounds for the representation of real univariate polynomials as sums of powers of degree 1 polynomials. We present two families of polynomials of degree d such that the number of powers that are required in such a representation must be at least of order d. This is clearly optimal up to a constant factor. Previous lower bounds for this problem were only of order $Ω$($\sqrt$ d), and were obtained from arguments based on Wronskian determinants and "shifted derivatives." We obtain this improvement thanks to a new lower bound method based on Birkhoff interpolation (also known as "lacunary polynomial interpolation").
DCTNet : A Simple Learning-free Approach for Face Recognition
Venue: arXiv cs.CV 2015
Year: 2015

PCANet was proposed as a lightweight deep learning network that mainly leverages Principal Component Analysis (PCA) to learn multistage filter banks followed by binarization and block-wise histograming. PCANet was shown worked surprisingly well in various image classification tasks. However, PCANet is data-dependence hence inflexible. In this paper, we proposed a data-independence network, dubbed DCTNet for face recognition in which we adopt Discrete Cosine Transform (DCT) as filter banks in place of PCA. This is motivated by the fact that 2D DCT basis is indeed a good approximation for high ranked eigenvectors of PCA. Both 2D DCT and PCA resemble a kind of modulated sine-wave patterns, which can be perceived as a bandpass filter bank. DCTNet is free from learning as 2D DCT bases can be computed in advance. Besides that, we also proposed an effective method to regulate the block-wise histogram feature vector of DCTNet for robustness. It is shown to provide surprising performance boost when the probe image is considerably different in appearance from the gallery image. We evaluate the performance of DCTNet extensively on a number of benchmark face databases and being able to achieve on par with or often better accuracy performance than PCANet.
Emulating short-term synaptic dynamics with memristive devices
Venue: arXiv cs.ET 2015
Year: 2015

Neuromorphic architectures offer great promise for achieving computation capacities beyond conventional Von Neumann machines. The essential elements for achieving this vision are highly scalable synaptic mimics that do not undermine biological fidelity. Here we demonstrate that single solid-state TiO2 memristors can exhibit non-associative plasticity phenomena observed in biological synapses, supported by their metastable memory state transition properties. We show that, contrary to conventional uses of solid-state memory, the existence of rate-limiting volatility is a key feature for capturing short-term synaptic dynamics. We also show how the temporal dynamics of our prototypes can be exploited to implement spatio-temporal computation, demonstrating the memristors full potential for building biophysically realistic neural processing systems.