OpenRaiser/Intern-Atlas huggingface dataset:
Fault-Tolerant Distributed Optimization (Part IV): Constrained Optimization with Arbitrary Directed Networks
Venue: arXiv cs.DC 2015
Year: 2015

We study the problem of constrained distributed optimization in multi-agent networks when some of the computing agents may be faulty. In this problem, the system goal is to have all the non-faulty agents collectively minimize a global objective given by weighted average of local cost functions, each of which is initially known to a non-faulty agent only. In particular, we are interested in the scenario when the computing agents are connected by an arbitrary directed communication network, some of the agents may suffer from crash faults or Byzantine faults, and the estimate of each agent is restricted to lie in a common constraint set. This problem finds its applications in social computing and distributed large-scale machine learning. The fault-tolerant multi-agent optimization problem was first formulated by Su and Vaidya, and is solved when the local functions are defined over the whole real line, and the networks are fully-connected. In this report, we consider arbitrary directed communication networks and focus on the scenario where, local estimates at the non-faulty agents are constrained, and only local communication and minimal memory carried across iterations are allowed. In particular, we generalize our previous results on fully-connected networks and unconstrained optimization to arbitrary directed networks and constrained optimization. As a byproduct, we provide a matrix representation for iterative approximate crash consensus. The matrix representation allows us to characterize the convergence rate for crash iterative consensus.
Weighted Sum-Throughput Maximization for MIMO Broadcast Channel: Energy Harvesting Under System Imperfection
Venue: arXiv cs.IT 2015
Year: 2015

In this work, a MIMO broadcast channel under the energy harvesting (EH) constraint and the peak power constraint is investigated. The transmitter is equipped with a hybrid energy storage system consisting of a perfect super capacitor (SC) and an inefficient battery, where both elements have limited energy storage capacities. In addition, the effect of data processing circuit power consumption is also addressed. To be specific, two extreme cases are studied here, where the first assumes ideal/zero circuit power consumption and the second considers a positive constant circuit power consumption where the circuit is always operating at its highest power level. The performance of these two extreme cases hence serve as the upper bound and the lower bound of the system performance in practice, respectively. In this setting, the offline scheduling with ideal and maximum circuit power consumptions are investigated. The associated optimization problems are formulated and solved in terms of weighted throughput optimization. Further, we extend to a general circuit power consumption model. To complement this work, some intuitive online policies are presented for all cases. Interestingly, for the case with maximum circuit power consumption, a close-to-optimal online policy is presented and its performance is shown to be comparable to its offline counterpart in the numerical results.
Network comparison using directed graphlets
Venue: arXiv cs.SI 2015
Year: 2015

With recent advances in high-throughput cell biology the amount of cellular biological data has grown drastically. Such data is often modeled as graphs (also called networks) and studying them can lead to new insights into molecule-level organization. A possible way to understand their structure is by analysing the smaller components that constitute them, namely network motifs and graphlets. Graphlets are particularly well suited to compare networks and to assess their level of similarity but are almost always used as small undirected graphs of up to five nodes, thus limiting their applicability in directed networks. However, a large set of interesting biological networks such as metabolic, cell signaling or transcriptional regulatory networks are intrinsically directional, and using metrics that ignore edge direction may gravely hinder information extraction. The applicability of graphlets is extended to directed networks by considering the edge direction of the graphlets. We tested our approach on a set of directed biological networks and verified that they were correctly grouped by type using directed graphlets. However, enumerating all graphlets in a large network is a computationally demanding task. Our implementation addresses this concern by using a state-of-the-art data structure, the g-trie, which is able to greatly reduce the necessary computation. We compared our tool, gtrieScanner, to other state-of-the art methods and verified that it is the fastest general tool for graphlet counting.
A quantitative performance analysis for Stokes solvers at the extreme scale
Venue: arXiv cs.CE 2015
Year: 2015

This article presents a systematic quantitative performance analysis for large finite element computations on extreme scale computing systems. Three parallel iterative solvers for the Stokes system, discretized by low order tetrahedral elements, are compared with respect to their numerical efficiency and their scalability running on up to $786\,432$ parallel threads. A genuine multigrid method for the saddle point system using an Uzawa-type smoother provides the best overall performance with respect to memory consumption and time-to-solution. The largest system solved on a Blue Gene/Q system has more than ten trillion ($1.1 \cdot 10 ^{13}$) unknowns and requires about 13 minutes compute time. Despite the matrix free and highly optimized implementation, the memory requirement for the solution vector and the auxiliary vectors is about 200 TByte. Brandt's notion of "textbook multigrid efficiency" is employed to study the algorithmic performance of iterative solvers. A recent extension of this paradigm to "parallel textbook multigrid efficiency" makes it possible to assess also the efficiency of parallel iterative solvers for a given hardware architecture in absolute terms. The efficiency of the method is demonstrated for simulating incompressible fluid flow in a pipe filled with spherical obstacles.
Learning Optimized Or's of And's
Venue: arXiv cs.AI 2015
Year: 2015

Or's of And's (OA) models are comprised of a small number of disjunctions of conjunctions, also called disjunctive normal form. An example of an OA model is as follows: If ($x_1 = $ `blue' AND $x_2=$ `middle') OR ($x_1 = $ `yellow'), then predict $Y=1$, else predict $Y=0$. Or's of And's models have the advantage of being interpretable to human experts, since they are a set of conditions that concisely capture the characteristics of a specific subset of data. We present two optimization-based machine learning frameworks for constructing OA models, Optimized OA (OOA) and its faster version, Optimized OA with Approximations (OOAx). We prove theoretical bounds on the properties of patterns in an OA model. We build OA models as a diagnostic screening tool for obstructive sleep apnea, that achieves high accuracy with a substantial gain in interpretability over other methods.
Deep Kernel Learning
Venue: arXiv cs.LG 2015
Year: 2015

We introduce scalable deep kernels, which combine the structural properties of deep learning architectures with the non-parametric flexibility of kernel methods. Specifically, we transform the inputs of a spectral mixture base kernel with a deep architecture, using local kernel interpolation, inducing points, and structure exploiting (Kronecker and Toeplitz) algebra for a scalable kernel representation. These closed-form kernels can be used as drop-in replacements for standard kernels, with benefits in expressive power and scalability. We jointly learn the properties of these kernels through the marginal likelihood of a Gaussian process. Inference and learning cost $O(n)$ for $n$ training points, and predictions cost $O(1)$ per test point. On a large and diverse collection of applications, including a dataset with 2 million examples, we show improved performance over scalable Gaussian processes with flexible kernel learning models, and stand-alone deep architectures.
Some Lower Bound Results for Set-Multilinear Arithmetic Computations
Venue: arXiv cs.CC 2015
Year: 2015

In this paper, we study the structure of set-multilinear arithmetic circuits and set-multilinear branching programs with the aim of showing lower bound results. We define some natural restrictions of these models for which we are able to show lower bound results. Some of our results extend existing lower bounds, while others are new and raise open questions. More specifically, our main results are the following: (1) We observe that set-multilinear arithmetic circuits can be transformed into shallow set-multilinear circuits efficiently, similar to depth reduction results of [VSBR83,RY08] for more general commutative circuits. As a consequence, we note that polynomial size set-multilinear circuits have quasi-polynomial size set-multilinear branching programs. We show that \emph{narrow} set-multilinear ABPs (with a restricted number of set types) computing the Permanent polynomial $\mathrm{PER}_n$ require $2^{n^{Ω(1)}}$ size. A similar result for general set-multilinear ABPs appears difficult as it would imply that the Permanent requires superpolynomial size set-multilinear circuits. It would also imply that the noncommutative Permanent requires superpolynomial size noncommutative arithmetic circuits. (2) Indeed, we also show that set-multilinear branching programs are exponentially more powerful than \emph{interval} multilinear circuits (where the index sets for each gate is restricted to be an interval w.r.t.\ some ordering), assuming the sum-of-squares conjecture. This further underlines the power of set-multilinear branching programs. (3) Finally, we consider set-multilinear circuits with restrictions on the number of proof trees of monomials computed by it, and prove exponential lower bounds results. This raises some new lower bound questions.
Performance Analysis of Multiclass Support Vector Machine Classification for Diagnosis of Coronary Heart Diseases
Venue: arXiv cs.LG 2015
Year: 2015

Automatic diagnosis of coronary heart disease helps the doctor to support in decision making a diagnosis. Coronary heart disease have some types or levels. Referring to the UCI Repository dataset, it divided into 4 types or levels that are labeled numbers 1-4 (low, medium, high and serious). The diagnosis models can be analyzed with multiclass classification approach. One of multiclass classification approach used, one of which is a support vector machine (SVM). The SVM use due to strong performance of SVM in binary classification. This research study multiclass performance classification support vector machine to diagnose the type or level of coronary heart disease. Coronary heart disease patient data taken from the UCI Repository. Stages in this study is preprocessing, which consist of, to normalizing the data, divide the data into data training and testing. The next stage of multiclass classification and performance analysis. This study uses multiclass SVM algorithm, namely: Binary Tree Support Vector Machine (BTSVM), One-Against-One (OAO), One-Against-All (OAA), Decision Direct Acyclic Graph (DDAG) and Exhaustive Output Error Correction Code (ECOC). Performance parameter used is recall, precision, F-measure and Overall accuracy.
On a class of $(δ+αu^2)$-constacyclic codes over $\mathbb{F}_{q}[u]/\langle u^4\rangle$
Venue: arXiv cs.IT 2015
Year: 2015

Let $\mathbb{F}_{q}$ be a finite field of cardinality $q$, $R=\mathbb{F}_{q}[u]/\langle u^4\rangle=\mathbb{F}_{q}+u\mathbb{F}_{q}+u^2\mathbb{F}_{q}+u^3\mathbb{F}_{q}$ $(u^4=0)$ which is a finite chain ring, and $n$ be a positive integer satisfying ${\rm gcd}(q,n)=1$. For any $δ,α\in \mathbb{F}_{q}^{\times}$, an explicit representation for all distinct $(δ+αu^2)$-constacyclic codes over $R$ of length $n$ is given, and the dual code for each of these codes is determined. For the case of $q=2^m$ and $δ=1$, all self-dual $(1+αu^2)$-constacyclic codes over $R$ of odd length $n$ are provided.
There are infinitely many bent functions for which the dual is not bent
Venue: arXiv cs.IT 2015
Year: 2015

Bent functions can be classified into regular bent functions, weakly regular but not regular bent functions, and non-weakly regular bent functions. Regular and weakly regular bent functions always appear in pairs since their duals are also bent functions. In general this does not apply to non-weaky regular bent functions. However, the first known construction of non-weakly regular bent functions by Ceşmelioğlu et {\it al.}, 2012, yields bent functions for which the dual is also bent. In this paper the first construction of non-weakly regular bent functions for which the dual is not bent is presented. We call such functions non-dual-bent functions. Until now, only sporadic examples found via computer search were known. We then show that with the direct sum of bent functions and with the construction by Ceşmelioğlu et {\it al.} one can obtain infinitely many non-dual-bent functions once one example of a non-dual-bent function is known.
The Cosmic Microwave Background Radiation Power Spectrum as a Random Bit Generator for Symmetric and Asymmetric-Key Cryptography
Venue: arXiv cs.CR 2015
Year: 2015

In this note, the Cosmic Microwave Background (CMB) Radiation is shown to be capable of functioning as a Random Bit Generator, and constitutes an effectively infinite supply of truly random one-time pad values of arbitrary length. It is further argued that the CMB power spectrum potentially conforms to the FIPS 140-2 standard. Additionally, its applicability to the generation of a (n x n) random key matrix for a Vernam cipher is established.
Modeling the Interplay Between Individual Behavior and Network Distributions
Venue: arXiv cs.SI 2015
Year: 2015

It is well-known that many networks follow a power-law degree distribution; however, the factors that influence the formation of their distributions are still unclear. How can one model the connection between individual actions and network distributions? How can one explain the formation of group phenomena and their evolutionary patterns? In this paper, we propose a unified framework, M3D, to model human dynamics in social networks from three perspectives: macro, meso, and micro. At the micro-level, we seek to capture the way in which an individual user decides whether to perform an action. At the meso-level, we study how group behavior develops and evolves over time, based on individual actions. At the macro-level, we try to understand how network distributions such as power-law (or heavy-tailed phenomena) can be explained by group behavior. We provide theoretical analysis for the proposed framework, and discuss the connection of our framework with existing work. The framework offers a new, flexible way to explain the interplay between individual user actions and network distributions, and can benefit many applications. To model heavy-tailed distributions from partially observed individual actions and to predict the formation of group behaviors, we apply M3D to three different genres of networks: Tencent Weibo, Citation, and Flickr. We also use information-burst prediction as a particular application to quantitatively evaluate the predictive power of the proposed framework. Our results on the Weibo indicate that M3D's prediction performance exceeds that of several alternative methods by up to 30\%.
S-PowerGraph: Streaming Graph Partitioning for Natural Graphs by Vertex-Cut
Venue: arXiv cs.SI 2015
Year: 2015

One standard solution for analyzing large natural graphs is to adopt distributed computation on clusters. In distributed computation, graph partitioning (GP) methods assign the vertices or edges of a graph to different machines in a balanced way so that some distributed algorithms can be adapted for. Most of traditional GP methods are offline, which means that the whole graph has been observed before partitioning. However, the offline methods often incur high computation cost. Hence, streaming graph partitioning (SGP) methods, which can partition graphs in an online way, have recently attracted great attention in distributed computation. There exist two typical GP strategies: edge-cut and vertex-cut. Most SGP methods adopt edge-cut, but few vertex-cut methods have been proposed for SGP. However, the vertex-cut strategy would be a better choice than the edge-cut strategy because the degree of a natural graph in general follows a highly skewed power-law distribution. Thus, we propose a novel method, called S-PowerGraph, for SGP of natural graphs by vertex-cut. Our S-PowerGraph method is simple but effective. Experiments on several large natural graphs and synthetic graphs show that our S-PowerGraph can outperform the state-of-the-art baselines.
The Turing Test for Telepresence
Venue: arXiv cs.HC 2015
Year: 2015

The quality of high-end videoconferencing systems has improved significantly over the last few years enabling a class of applications known as "telepresence" wherein the users engaged in a communication session experience a feeling of mutual presence in a shared virtual space. Telepresence systems have reached a maturity level that seriously challenges the old familiar truism that a face-to-face meeting is always better than a technology-mediated alternative. To explore the state of the art in telepresence technology and outline future opportunities, this paper proposes an optimality condition, expressed as a "Turing Test," whereby the subjective experience of using a telepresence system is compared to the corresponding face-to-face situation. The requirements and challenges of designing a system passing such a Turing Test for telepresence are analyzed with respect to the limits of human perception, and the feasibility of achieving this goal with currently available or near future technology is discussed.
Toward Biochemical Probabilistic Computation
Venue: arXiv cs.ET 2015
Year: 2015

Living organisms survive and multiply even though they have uncertain and incomplete information about their environment and imperfect models to predict the consequences of their actions. Bayesian models have been proposed to face this challenge. Indeed, Bayesian inference is a way to do optimal reasoning when only uncertain and incomplete information is available. Various perceptive, sensory-motor, and cognitive functions have been successfully modeled this way. However, the biological mechanisms allowing animals and humans to represent and to compute probability distributions are not known. It has been proposed that neurons and assemblies of neurons could be the appropriate scale to search for clues to probabilistic reasoning. In contrast, in this paper, we propose that interacting populations of macromolecules and diffusible messengers can perform probabilistic computation. This suggests that probabilistic reasoning, based on cellular signaling pathways, is a fundamental skill of living organisms available to the simplest unicellular organisms as well as the most complex brains.
A Novel Adaptation Method for HTTP Streaming of VBR Videos over Mobile Networks
Venue: arXiv cs.MM 2015
Year: 2015

Recently, HTTP streaming has become very popular for delivering video over the Internet. For adaptivity, a provider should generate multiple versions of a video as well as the related metadata. Various adaptation methods have been proposed to support a streaming client in coping with strong bandwidth variations. However, most of existing methods target at constant bitrate (CBR) videos only. In this paper, we present a new method for quality adaptation in on-demand streaming of variable bitrate (VBR) videos. To cope with strong variations of VBR bitrate, we use a local average bitrate as the representative bitrate of a version. A buffer-based algorithm is then proposed to conservatively adapt video quality. Through experiments, we show that our method can provide quality stability as well as buffer stability even under very strong variations of bandwidth and video bitrates.
ReOpt: an Algorithm with a Quality Guaranty for Solving the Static Relocation Problem
Venue: arXiv cs.DS 2015
Year: 2015

In a carsharing system, a fleet of cars is distributed at stations in an urban area, customers can take and return cars at any time and station. For operating such a system in a satisfactory way, the stations have to keep a good ratio between the numbers of free places and cars in each station. This leads to the problem of relocating cars between stations, which can be modeled within the framework of a metric task system. In this paper, we focus on the Static Relocation Problem, where the system has to be set into a certain state, outgoing from the current state. We present a combinatorial approach and provide approximation factors for several different situations.
Neighbourhood NILM: A Big-data Approach to Household Energy Disaggregation
Venue: arXiv cs.LG 2015
Year: 2015

In this paper, we investigate whether "big-data" is more valuable than "precise" data for the problem of energy disaggregation: the process of breaking down aggregate energy usage on a per-appliance basis. Existing techniques for disaggregation rely on energy metering at a resolution of 1 minute or higher, but most power meters today only provide a reading once per month, and at most once every 15 minutes. In this paper, we propose a new technique called Neighbourhood NILM that leverages data from 'neighbouring' homes to disaggregate energy given only a single energy reading per month. The key intuition behind our approach is that 'similar' homes have 'similar' energy consumption on a per-appliance basis. Neighbourhood NILM matches every home with a set of 'neighbours' that have direct submetering infrastructure, i.e. power meters on individual circuits or loads. Many such homes already exist. Then, it estimates the appliance-level energy consumption of the target home to be the average of its K neighbours. We evaluate this approach using 25 homes and results show that our approach gives comparable or better disaggregation in comparison to state-of-the-art accuracy reported in the literature that depend on manual model training, high frequency power metering, or both. Results show that Neighbourhood NILM can achieve 83% and 79% accuracy disaggregating fridge and heating/cooling loads, compared to 74% and 73% for a technique called FHMM. Furthermore, it achieves up to 64% accuracy on washing machine, dryer, dishwasher, and lighting loads, which is higher than previously reported results. Many existing techniques are not able to disaggregate these loads at all. These results indicate a potentially substantial advantage to installing submetering infrastructure in a select few homes rather than installing new high-frequency smart metering infrastructure in all homes.
Efficient Construction of Local Parametric Reduced Order Models Using Machine Learning Techniques
Venue: arXiv cs.LG 2015
Year: 2015

Reduced order models are computationally inexpensive approximations that capture the important dynamical characteristics of large, high-fidelity computer models of physical systems. This paper applies machine learning techniques to improve the design of parametric reduced order models. Specifically, machine learning is used to develop feasible regions in the parameter space where the admissible target accuracy is achieved with a predefined reduced order basis, to construct parametric maps, to chose the best two already existing bases for a new parameter configuration from accuracy point of view and to pre-select the optimal dimension of the reduced basis such as to meet the desired accuracy. By combining available information using bases concatenation and interpolation as well as high-fidelity solutions interpolation we are able to build accurate reduced order models associated with new parameter settings. Promising numerical results with a viscous Burgers model illustrate the potential of machine learning approaches to help design better reduced order models.