OpenRaiser/Intern-Atlas huggingface dataset:
Sequential Probability Assignment with Binary Alphabets and Large Classes of Experts
Venue: arXiv cs.IT 2015
Year: 2015

We analyze the problem of sequential probability assignment for binary outcomes with side information and logarithmic loss, where regret---or, redundancy---is measured with respect to a (possibly infinite) class of experts. We provide upper and lower bounds for minimax regret in terms of sequential complexities of the class. These complexities were recently shown to give matching (up to logarithmic factors) upper and lower bounds for sequential prediction with general convex Lipschitz loss functions (Rakhlin and Sridharan, 2015). To deal with unbounded gradients of the logarithmic loss, we present a new analysis that employs a sequential chaining technique with a Bernstein-type bound. The introduced complexities are intrinsic to the problem of sequential probability assignment, as illustrated by our lower bound. We also consider an example of a large class of experts parametrized by vectors in a high-dimensional Euclidean ball (or a Hilbert ball). The typical discretization approach fails, while our techniques give a non-trivial bound. For this problem we also present an algorithm based on regularization with a self-concordant barrier. This algorithm is of an independent interest, as it requires a bound on the function values rather than gradients.
Finding Connected Dense $k$-Subgraphs
Venue: arXiv cs.DM 2015
Year: 2015

Given a connected graph $G$ on $n$ vertices and a positive integer $k\le n$, a subgraph of $G$ on $k$ vertices is called a $k$-subgraph in $G$. We design combinatorial approximation algorithms for finding a connected $k$-subgraph in $G$ such that its density is at least a factor $Ω(\max\{n^{-2/5},k^2/n^2\})$ of the density of the densest $k$-subgraph in $G$ (which is not necessarily connected). These particularly provide the first non-trivial approximations for the densest connected $k$-subgraph problem on general graphs.
Hardness of Virtual Network Embedding with Replica Selection
Venue: arXiv cs.DC 2015
Year: 2015

Efficient embedding virtual clusters in physical network is a challenging problem. In this paper we consider a scenario where physical network has a structure of a balanced tree. This assumption is justified by many real- world implementations of datacenters. We consider an extension to virtual cluster embedding by introducing replication among data chunks. In many real-world applications, data is stored in distributed and redundant way. This assumption introduces additional hardness in deciding what replica to process. By reduction from classical NP-complete problem of Boolean Satisfia- bility, we show limits of optimality of embedding. Our result holds even in trees of edge height bounded by three. Also, we show that limiting repli- cation factor to two replicas per chunk type does not make the problem simpler.
Resilience for Exascale Enabled Multigrid Methods
Venue: arXiv cs.CE 2015
Year: 2015

With the increasing number of components and further miniaturization the mean time between faults in supercomputers will decrease. System level fault tolerance techniques are expensive and cost energy, since they are often based on redundancy. Also classical check-point-restart techniques reach their limits when the time for storing the system state to backup memory becomes excessive. Therefore, algorithm-based fault tolerance mechanisms can become an attractive alternative. This article investigates the solution process for elliptic partial differential equations that are discretized by finite elements. Faults that occur in the parallel geometric multigrid solver are studied in various model scenarios. In a standard domain partitioning approach, the impact of a failure of a core or a node will affect one or several subdomains. Different strategies are developed to compensate the effect of such a failure algorithmically. The recovery is achieved by solving a local subproblem with Dirichlet boundary conditions using local multigrid cycling algorithms. Additionally, we propose a superman strategy where extra compute power is employed to minimize the time of the recovery process.
Convergence law for hyper-graphs with prescribed degree sequences
Venue: arXiv cs.LO 2015
Year: 2015

We view hyper-graphs as incidence graphs, i.e. bipartite graphs with a set of nodes representing vertices and a set of nodes representing hyper-edges, with two nodes being adjacent if the corresponding vertex belongs to the corresponding hyper-edge. It defines a random hyper-multigraph specified by two distributions, one for the degrees of the vertices, and one for the sizes of the hyper-edges. We develop the logical analysis of this framework and first prove a convergence law for first-order logic, then characterise the limit first-order theories defined by a wide class of degree distributions. Convergence laws of other models follow, and in particular for the classical Erdős-Rényi graphs and $k$-uniform hyper-graphs.
Analytical Model for IEEE 802.15.4 Multi-Hop Networks with Improved Handling of Acknowledgements and Retransmissions
Venue: arXiv cs.NI 2015
Year: 2015

The IEEE 802.15.4 standard allows for the deployment of cost-effective and energy-efficient multi-hop networks. This document features an in-depth presentation of an analytical model for assessing the performance of such networks. It considers a generic, static topology with Poisson distributed data-collection as well as data-dissemination traffic. The unslotted CSMA/CA MAC layer of IEEE 802.15.4 is closely modeled as well as an enhanced model of the neighborhood allows for consideration of collisions of packets including interferences with acknowledgements. The hidden node problem is taken into account as well as a formerly disregarded effect of repeated collisions of retransmissions. The model has been shown to be suitable to estimate the capacity of large-scale multi-hop networks.
Robust Transceiver Design for MISO Interference Channel with Energy Harvesting
Venue: arXiv cs.IT 2015
Year: 2015

In this paper, we consider multiuser multiple-input single-output (MISO) interference channel where the received signal is divided into two parts for information decoding and energy harvesting (EH), respectively. The transmit beamforming vectors and receive power splitting (PS) ratios are jointly designed in order to minimize the total transmission power subject to both signal-to-interference-plus-noise ratio (SINR) and EH constraints. Most joint beamforming and power splitting (JBPS) designs assume that perfect channel state information (CSI) is available; however CSI errors are inevitable in practice. To overcome this limitation, we study the robust JBPS design problem assuming a norm-bounded error (NBE) model for the CSI. Three different solution approaches are proposed for the robust JBPS problem, each one leading to a different computational algorithm. Firstly, an efficient semidefinite relaxation (SDR)-based approach is presented to solve the highly non-convex JBPS problem, where the latter can be formulated as a semidefinite programming (SDP) problem. A rank-one recovery method is provided to recover a robust feasible solution to the original problem. Secondly, based on second order cone programming (SOCP) relaxation, we propose a low complexity approach with the aid of a closed-form robust solution recovery method. Thirdly, a new iterative method is also provided which can achieve near-optimal performance when the SDR-based algorithm results in a higher-rank solution. We prove that this iterative algorithm monotonically converges to a Karush-Kuhn-Tucker (KKT) solution of the robust JBPS problem. Finally, simulation results are presented to validate the robustness and efficiency of the proposed algorithms.
Construction of rational expression from tree automata using a generalization of Arden's Lemma
Venue: arXiv cs.FL 2015
Year: 2015

Arden's Lemma is a classical result in language theory allowing the computation of a rational expression denoting the language recognized by a finite string automaton. In this paper we generalize this important lemma to the rational tree languages. Moreover, we propose also a construction of a rational tree expression which denotes the accepted tree language of a finite tree automaton.
Co-Regularized Deep Representations for Video Summarization
Venue: arXiv cs.CV 2015
Year: 2015

Compact keyframe-based video summaries are a popular way of generating viewership on video sharing platforms. Yet, creating relevant and compelling summaries for arbitrarily long videos with a small number of keyframes is a challenging task. We propose a comprehensive keyframe-based summarization framework combining deep convolutional neural networks and restricted Boltzmann machines. An original co-regularization scheme is used to discover meaningful subject-scene associations. The resulting multimodal representations are then used to select highly-relevant keyframes. A comprehensive user study is conducted comparing our proposed method to a variety of schemes, including the summarization currently in use by one of the most popular video sharing websites. The results show that our method consistently outperforms the baseline schemes for any given amount of keyframes both in terms of attractiveness and informativeness. The lead is even more significant for smaller summaries.
Electronic Medication Prescribing Support System for Diagnosing Tropical Diseases
Venue: arXiv cs.CY 2015
Year: 2015

This paper presents the development of an e-prescription system for diagnosing tropical diseases.Results after testing the developed system by medical experts indicated that the e-prescription systems is more efficient and less susceptible to common errors associated with the conventional handwritten medical prescription and can also go a long way to help to improve patients health outcome in the health industry especially in the tropics.
An Analytical Study of different Document Image Binarization Methods
Venue: arXiv cs.CV 2015
Year: 2015

Document image has been the area of research for a couple of decades because of its potential application in the area of text recognition, line recognition or any other shape recognition from the image. For most of these purposes binarization of image becomes mandatory as far as recognition is concerned. Throughout couple decades standard algorithms have already been developed for this purpose. Some of these algorithms are applicable to degraded image also. Our objective behind this work is to study the existing techniques, compare them in view of advantages and disadvantages and modify some of these algorithms to optimize time or performance.
Time-Free and Timer-Based Assumptions Can Be Combined to Solve Authenticated Byzantine Consensus
Venue: arXiv cs.DC 2015
Year: 2015

To circumvent the FLP impossibility result in a deterministic way several protocols have been proposed on top of an asynchronous distributed system enriched with additional assumptions. In the context of Byzantine failures for systems where at most t processes may exhibit a Byzantine behavior, two approaches have been investigated to solve the consensus problem.The first, relies on the addition of synchrony, called Timer-Based, but the second is based on the pattern of the messages that are exchanged, called Time-Free. This paper shows that both types of assumptions are not antagonist and can be combined to solve authenticated Byzantine consensus. This combined assumption considers a correct process pi, called 2t-BW, and a set X of 2t processes such that, eventually, for each query broadcasted by a correct process pj of X, pj receives a response from pi 2 X among the (n- t) first responses to that query or both links connecting pi and pj are timely. Based on this combination, a simple hybrid authenticated Byzantine consensus protocol,benefiting from the best of both worlds, is proposed. Whereas many hybrid protocols have been designed for the consensus problem in the crash model, this is, to our knowledge, the first hybrid deterministic solution to the Byzantine consensus problem.
Context-aware Computing in the Internet of Things: A Survey on Internet of Things From Industrial Market Perspective
Venue: arXiv cs.CY 2015
Year: 2015

The Internet of Things (IoT) is a dynamic global information network consisting of Internet-connected objects, such as RFIDs, sensors, and actuators, as well as other instruments and smart appliances that are becoming an integral component of the Internet. Over the last few years, we have seen a plethora of IoT solutions making their way into the industry marketplace. Context-aware communication and computing has played a critical role throughout the last few years of ubiquitous computing and is expected to play a significant role in the IoT paradigm as well. In this article, we examine a variety of popular and innovative IoT solutions in terms of context-aware technology perspectives. More importantly, we evaluate these IoT solutions using a framework that we built around well-known context-aware computing theories. This survey is intended to serve as a guideline and a conceptual framework for contextaware product development and research in the IoT paradigm. It also provides a systematic exploration of existing IoT products in the marketplace and highlights a number of potentially significant research directions and trends.
A Study on the Impact of Wind Generation on the Stability of Electromechanical Oscillations
Venue: arXiv cs.SY 2015
Year: 2015

Wind is becoming an increasingly significant source of energy in modern power generation. Amongst existing technologies, Variable Speed Wind Turbines (VSWT) equipped with Double Fed Induction Generators (DFIG) is widely deployed. Consequently, power systems are now experiencing newer power flow patterns and operating conditions. This paper investigates the impact of a DFIG based Wind Farm (WF) on the stability of electromechanical oscillations. This is achieved by performing modal analysis to evaluate the stability of a two-area power network when subjected to different wind penetration levels and different geographical installed locations. The approach via eigenvalues analysis involves the design of voltage and Supplementary Damping Controllers (SDCs) that contribute to network damping. The effect of Power System Stabilizer (PSS) is also examined for several network conditions. Simulations demonstrate a damping improvement up to 933% when the control systems are activated and the system operates with 25% wind integration.
Can "Hot Spots" in the Sciences Be Mapped Using the Dynamics of Aggregated Journal-Journal Citation Relations?
Venue: arXiv cs.DL 2015
Year: 2015

Using three years of the Journal Citation Reports (2011, 2012, and 2013), indicators of transitions in 2012 (between 2011 and 2013) are studied using methodologies based on entropy statistics. Changes can be indicated at the level of journals using the margin totals of entropy production along the row or column vectors, but also at the level of links among journals by importing the transition matrices into network analysis and visualization programs (and using community-finding algorithms). Seventy-four journals are flagged in terms of discontinuous changes in their citations; but 3,114 journals are involved in "hot" links. Most of these links are embedded in a main component; 78 clusters (containing 172 journals) are flagged as potential "hot spots" emerging at the network level. An additional finding is that PLoS ONE introduced a new communication dynamics into the database. The limitations of the methodology are elaborated using an example. The results of the study indicate where developments in the citation dynamics can be considered as significantly unexpected. This can be used as heuristic information; but what a "hot spot" in terms of the entropy statistics of aggregated citation relations means substantively can be expected to vary from case to case.
Feature Selection with Redundancy-complementariness Dispersion
Venue: arXiv cs.LG 2015
Year: 2015

Feature selection has attracted significant attention in data mining and machine learning in the past decades. Many existing feature selection methods eliminate redundancy by measuring pairwise inter-correlation of features, whereas the complementariness of features and higher inter-correlation among more than two features are ignored. In this study, a modification item concerning the complementariness of features is introduced in the evaluation criterion of features. Additionally, in order to identify the interference effect of already-selected False Positives (FPs), the redundancy-complementariness dispersion is also taken into account to adjust the measurement of pairwise inter-correlation of features. To illustrate the effectiveness of proposed method, classification experiments are applied with four frequently used classifiers on ten datasets. Classification results verify the superiority of proposed method compared with five representative feature selection methods.
Injury risk prediction for traffic accidents in Porto Alegre/RS, Brazil
Venue: arXiv cs.LG 2015
Year: 2015

This study describes the experimental application of Machine Learning techniques to build prediction models that can assess the injury risk associated with traffic accidents. This work uses an freely available data set of traffic accident records that took place in the city of Porto Alegre/RS (Brazil) during the year of 2013. This study also provides an analysis of the most important attributes of a traffic accident that could produce an outcome of injury to the people involved in the accident.
Survey on Awareness of Privacy Issues in Ubiquitous Environment
Venue: arXiv cs.CY 2015
Year: 2015

This study aims to determine privacy awareness among people in ubiquitous environment through a questionnaire based survey.
An Exploration of Cursor tracking Data
Venue: arXiv cs.HC 2015
Year: 2015

Cursor tracking data contains information about website visitors which may provide new ways to understand visitors and their needs. This paper presents an Amazon Mechanical Turk study where participants were tracked as they used modified variants of the Wikipedia and BBC News websites. Participants were asked to complete reading and information-finding tasks. The results showed that it was possible to differentiate between users reading content and users looking for information based on cursor data. The effects of website aesthetics, user interest and cursor hardware were also analysed which showed it was possible to identify hardware from cursor data, but no relationship between cursor data and engagement was found. The implications of these results, from the impact on web analytics to the design of experiments to assess user engagement, are discussed.
Complex Background Subtraction by Pursuing Dynamic Spatio-Temporal Models
Venue: arXiv cs.CV 2015
Year: 2015

Although it has been widely discussed in video surveillance, background subtraction is still an open problem in the context of complex scenarios, e.g., dynamic backgrounds, illumination variations, and indistinct foreground objects. To address these challenges, we propose an effective background subtraction method by learning and maintaining an array of dynamic texture models within the spatio-temporal representations. At any location of the scene, we extract a sequence of regular video bricks, i.e. video volumes spanning over both spatial and temporal domain. The background modeling is thus posed as pursuing subspaces within the video bricks while adapting the scene variations. For each sequence of video bricks, we pursue the subspace by employing the ARMA (Auto Regressive Moving Average) Model that jointly characterizes the appearance consistency and temporal coherence of the observations. During online processing, we incrementally update the subspaces to cope with disturbances from foreground objects and scene changes. In the experiments, we validate the proposed method in several complex scenarios, and show superior performances over other state-of-the-art approaches of background subtraction. The empirical studies of parameter setting and component analysis are presented as well.
A Web-based Interactive Visual Graph Analytics Platform
Venue: arXiv cs.SI 2015
Year: 2015

This paper proposes a web-based visual graph analytics platform for interactive graph mining, visualization, and real-time exploration of networks. GraphVis is fast, intuitive, and flexible, combining interactive visualizations with analytic techniques to reveal important patterns and insights for sense making, reasoning, and decision making. Networks can be visualized and explored within seconds by simply drag-and-dropping a graph file into the web browser. The structure, properties, and patterns of the network are computed automatically and can be instantly explored in real-time. At the heart of GraphVis lies a multi-level interactive network visualization and analytics engine that allows for real-time graph mining and exploration across multiple levels of granularity simultaneously. Both the graph analytic and visualization techniques (at each level of granularity) are dynamic and interactive, with immediate and continuous visual feedback upon every user interaction (e.g., change of a slider for filtering). Furthermore, nodes, edges, and subgraphs are easily inserted, deleted or exported via a number of novel techniques and tools that make it extremely easy and flexible for exploring, testing hypothesis, and understanding networks in real-time over the web. A number of interactive visual graph analytic techniques are also proposed including interactive role discovery methods, community detection, as well as a number of novel block models for generating graphs with community structure. Finally, we also highlight other key aspects including filtering, querying, ranking, manipulating, exporting, partitioning, as well as tools for dynamic network analysis and visualization, interactive graph generators, and a variety of multi-level network analysis, summarization, and statistical techniques.
On Restricting No-Junta Boolean Function and Degree Lower Bounds by Polynomial Method
Venue: arXiv cs.CC 2015
Year: 2015

Let $\mathcal{F}_{n}^*$ be the set of Boolean functions depending on all $n$ variables. We prove that for any $f\in \mathcal{F}_{n}^*$, $f|_{x_i=0}$ or $f|_{x_i=1}$ depends on the remaining $n-1$ variables, for some variable $x_i$. This existent result suggests a possible way to deal with general Boolean functions via its subfunctions of some restrictions. As an application, we consider the degree lower bound of representing polynomials over finite rings. Let $f\in \mathcal{F}_{n}^*$ and denote the exact representing degree over the ring $\mathbb{Z}_m$ (with the integer $m>2$) as $d_m(f)$. Let $m=Π_{i=1}^{r}p_i^{e_i}$, where $p_i$'s are distinct primes, and $r$ and $e_i$'s are positive integers. If $f$ is symmetric, then $m\cdot d_{p_1^{e_1}}(f)... d_{p_r^{e_r}}(f) > n$. If $f$ is non-symmetric, by the second moment method we prove almost always $m\cdot d_{p_1^{e_1}}(f)... d_{p_r^{e_r}}(f) > \lg{n}-1$. In particular, as $m=pq$ where $p$ and $q$ are arbitrary distinct primes, we have $d_p(f)d_q(f)=Ω(n)$ for symmetric $f$ and $d_p(f)d_q(f)=Ω(\lg{n}-1)$ almost always for non-symmetric $f$. Hence any $n$-variate symmetric Boolean function can have exact representing degree $o(\sqrt{n})$ in at most one finite field, and for non-symmetric functions, with $o(\sqrt{\lg{n}})$-degree in at most one finite field.