OpenRaiser/Intern-Atlas huggingface dataset:
Optimized Random Deployment of Energy Harvesting Sensors for Field Reconstruction in Analog and Digital Forwarding Systems
Venue: arXiv cs.IT 2015
Year: 2015

This work examines the large-scale deployment of energy harvesting sensors for the purpose of sensing and reconstruction of a spatially correlated Gaussian random field. The sensors are powered solely by energy harvested from the environment and are deployed randomly according to a spatially nonhomogeneous Poisson point process whose density depends on the energy arrival statistics at different locations. Random deployment is suitable for applications that require deployment over a wide and/or hostile area. During an observation period, each sensor takes a local sample of the random field and reports the data to the closest data-gathering node if sufficient energy is available for transmission. The realization of the random field is then reconstructed at the fusion center based on the reported sensor measurements. For the purpose of field reconstruction, the sensors should, on the one hand, be more spread out over the field to gather more informative samples, but should, on the other hand, be more concentrated at locations with high energy arrival rates or large channel gains toward the closest data-gathering node. This tradeoff is exploited in the optimization of the random sensor deployment in both analog and digital forwarding systems. More specifically, given the statistics of the energy arrival at different locations and a constraint on the average number of sensors, the spatially-dependent sensor density and the energy-aware transmission policy at the sensors are determined for both cases by minimizing an upper bound on the average mean-square reconstruction error. The efficacy of the proposed schemes are demonstrated through numerical simulations.
Advances in Computational Biology: A Real Boost or a Wishful Thinking
Venue: arXiv cs.OH 2015
Year: 2015

Computational biology is on the verge of a paradigm shift in its research practice - from a data-based (computational) paradigm to an information-based (cognitive) paradigm. As in the other research fields, this transition is impeded by lack of a right understanding about what is actually hidden behind the term "information". The paper is intended to clarify this issue and introduces two new notions of "physical information" and "semantic information", which together constitute the term "information". Some implications of this introduction are considered.
Techniques for Deep Query Understanding
Venue: arXiv cs.IR 2015
Year: 2015

Query Understanding concerns about inferring the precise intent of search by the user with his formulated query, which is challenging because the queries are often very short and ambiguous. The report discusses the various kind of queries that can be put to a Search Engine and illustrates the Role of Query Understanding for return of relevant results. With different advances in techniques for deep understanding of queries as well as documents, the Search Technology has witnessed three major era. A lot of interesting real world examples have been used to illustrate the role of Query Understanding in each of them. The Query Understanding Module is responsible to correct the mistakes done by user in the query, to guide him in formulation of query with precise intent, and to precisely infer the intent of the user query. The report describes the complete architecture to handle aforementioned three tasks, and then discusses basic as well as recent advanced techniques for each of the component, through appropriate papers from reputed conferences and journals.
A probabilistic approach to reducing the algebraic complexity of computing Delaunay triangulations
Venue: arXiv cs.CG 2015
Year: 2015

Computing Delaunay triangulations in $\mathbb{R}^d$ involves evaluating the so-called in\_sphere predicate that determines if a point $x$ lies inside, on or outside the sphere circumscribing $d+1$ points $p_0,\ldots ,p_d$. This predicate reduces to evaluating the sign of a multivariate polynomial of degree $d+2$ in the coordinates of the points $x, \, p_0,\, \ldots,\, p_d$. Despite much progress on exact geometric computing, the fact that the degree of the polynomial increases with $d$ makes the evaluation of the sign of such a polynomial problematic except in very low dimensions. In this paper, we propose a new approach that is based on the witness complex, a weak form of the Delaunay complex introduced by Carlsson and de Silva. The witness complex $\mathrm{Wit} (L,W)$ is defined from two sets $L$ and $W$ in some metric space $X$: a finite set of points $L$ on which the complex is built, and a set $W$ of witnesses that serves as an approximation of $X$. A fundamental result of de Silva states that $\mathrm{Wit}(L,W)=\mathrm{Del} (L)$ if $W=X=\mathbb{R}^d$. In this paper, we give conditions on $L$ that ensure that the witness complex and the Delaunay triangulation coincide when $W$ is a finite set, and we introduce a new perturbation scheme to compute a perturbed set $L'$ close to $L$ such that $\mathrm{Del} (L')= \mathrm{wit} (L', W)$. Our perturbation algorithm is a geometric application of the Moser-Tardos constructive proof of the Lovász local lemma. The only numerical operations we use are (squared) distance comparisons (i.e., predicates of degree 2). The time-complexity of the algorithm is sublinear in $|W|$. Interestingly, although the algorithm does not compute any measure of simplex quality, a lower bound on the thickness of the output simplices can be guaranteed.
Distributed Adaptive Fault-Tolerant Control of Uncertain Multi-Agent Systems
Venue: arXiv cs.SY 2015
Year: 2015

This paper presents an adaptive fault-tolerant control (FTC) scheme for a class of nonlinear uncertain multi-agent systems. A local FTC scheme is designed for each agent using local measurements and suitable information exchanged between neighboring agents. Each local FTC scheme consists of a fault diagnosis module and a reconfigurable controller module comprised of a baseline controller and two adaptive fault-tolerant controllers activated after fault detection and after fault isolation, respectively. Under certain assumptions, the closed-loop system's stability and leader-follower consensus properties are rigorously established under different modes of the FTC system, including the time-period before possible fault detection, between fault detection and possible isolation, and after fault isolation.
Constructing Intrinsic Delaunay Triangulations from the Dual of Geodesic Voronoi Diagrams
Venue: arXiv cs.CG 2015
Year: 2015

Intrinsic Delaunay triangulation (IDT) is a fundamental data structure in computational geometry and computer graphics. However, except for some theoretical results, such as existence and uniqueness, little progress has been made towards computing IDT on simplicial surfaces. To date the only way for constructing IDTs is the edge-flipping algorithm, which iteratively flips the non-Delaunay edge to be locally Delaunay. Although the algorithm is conceptually simple and guarantees to stop in finite steps, it has no known time complexity. Moreover, the edge-flipping algorithm may produce non-regular triangulations, which contain self-loops and/or faces with only two edges. In this paper, we propose a new method for constructing IDT on manifold triangle meshes. Based on the duality of geodesic Voronoi diagrams, our method can guarantee the resultant IDTs are regular. Our method has a theoretical worst-case time complexity $O(n^2\log n)$ for a mesh with $n$ vertices. We observe that most real-world models are far from their Delaunay triangulations, thus, the edge-flipping algorithm takes many iterations to fix the non-Delaunay edges. In contrast, our method is non-iterative and insensitive to the number of non-Delaunay edges. Empirically, it runs in linear time $O(n)$ on real-world models.
A mechanized proof of loop freedom of the (untimed) AODV routing protocol
Venue: arXiv cs.NI 2015
Year: 2015

The Ad hoc On-demand Distance Vector (AODV) routing protocol allows the nodes in a Mobile Ad hoc Network (MANET) or a Wireless Mesh Network (WMN) to know where to forward data packets. Such a protocol is 'loop free' if it never leads to routing decisions that forward packets in circles. This paper describes the mechanization of an existing pen-and-paper proof of loop freedom of AODV in the interactive theorem prover Isabelle/HOL. The mechanization relies on a novel compositional approach for lifting invariants to networks of nodes. We exploit the mechanization to analyse several improvements of AODV and show that Isabelle/HOL can re-establish most proof obligations automatically and identify exactly the steps that are no longer valid.
Operating Power Grids with Few Flow Control Buses
Venue: arXiv cs.SY 2015
Year: 2015

Future power grids will offer enhanced controllability due to the increased availability of power flow control units (FACTS). As the installation of control units in the grid is an expensive investment, we are interested in using few controllers to achieve high controllability. In particular, two questions arise: How many flow control buses are necessary to obtain globally optimal power flows? And if fewer flow control buses are available, what can we achieve with them? Using steady state IEEE benchmark data sets, we explore experimentally that already a small number of controllers placed at certain grid buses suffices to achieve globally optimal power flows. We present a graph-theoretic explanation for this behavior. To answer the second question we perform a set of experiments that explore the existence and costs of feasible power flow solutions at increased loads with respect to the number of flow control buses in the grid. We observe that adding a small number of flow control buses reduces the flow costs and extends the existence of feasible solutions at increased load.
GazeDPM: Early Integration of Gaze Information in Deformable Part Models
Venue: arXiv cs.CV 2015
Year: 2015

An increasing number of works explore collaborative human-computer systems in which human gaze is used to enhance computer vision systems. For object detection these efforts were so far restricted to late integration approaches that have inherent limitations, such as increased precision without increase in recall. We propose an early integration approach in a deformable part model, which constitutes a joint formulation over gaze and visual data. We show that our GazeDPM method improves over the state-of-the-art DPM baseline by 4% and a recent method for gaze-supported object detection by 3% on the public POET dataset. Our approach additionally provides introspection of the learnt models, can reveal salient image structures, and allows us to investigate the interplay between gaze attracting and repelling areas, the importance of view-specific models, as well as viewers' personal biases in gaze patterns. We finally study important practical aspects of our approach, such as the impact of using saliency maps instead of real fixations, the impact of the number of fixations, as well as robustness to gaze estimation error.
An Improved Upper Bound for the Most Informative Boolean Function Conjecture
Venue: arXiv cs.IT 2015
Year: 2015

Suppose $X$ is a uniformly distributed $n$-dimensional binary vector and $Y$ is obtained by passing $X$ through a binary symmetric channel with crossover probability $α$. A recent conjecture by Courtade and Kumar postulates that $I(f(X);Y)\leq 1-h(α)$ for any Boolean function $f$. So far, the best known upper bound was $I(f(X);Y)\leq (1-2α)^2$. In this paper, we derive a new upper bound that holds for all balanced functions, and improves upon the best known bound for all $\tfrac{1}{3}<α<\tfrac{1}{2}$.
Finite-SNR Analysis of Partial Relaying with Relay Selection in Channel-coded Cooperative Networks
Venue: arXiv cs.IT 2015
Year: 2015

This work studies the performance of a cooperative network which consists of two channel-coded sources, multiple relays, and one destination. Due to spectral efficiency constraint, we assume only one time slot is dedicated for relaying. Conventional network coding based cooperation (NCC) selects the best relay which uses network coding to serve two sources simultaneously. The performance in terms of bit error rate (BER) of NCC, however, is not available in the literature. In this paper, we first derive the closed-form expression for the BER of NCC and analytically show that NCC always achieves diversity of order two regardless the number of available relays and the channel code. Secondly, motivated by a loss in diversity in NCC, we propose a novel relaying scheme based on partial relaying cooperation (PARC) in which two best relays are selected, each forwarding half of the codeword to help one source. Closed-form expression for BER and system diversity order of the proposed scheme are derived. Analytical results show that the diversity order of PARC is a function of the operating signal-to-noise ratio (SNR) and the minimum distance of the channel code. More importantly, full diversity order in PARC can be achieved for practically operating finite SNRs with the proper channel code. Finally, intensive simulations present a huge SNR gain of PARC over NCC and reference schemes without relay selection.
Motion Planning with Safety Constraints and High-Level Task Specifications
Venue: arXiv cs.RO 2015
Year: 2015

We present a method to solve planning problems involving sequential decision making in unpredictable environments while accomplishing a high level task specification expressed using the formalism of linear temporal logic. Our method improves the state of the art by introducing a pruning step that preserves correctness while significantly reducing the time needed to compute an optimal policy. Our theoretical contribution is coupled with simulations substantiating the value of the proposed method.
Vehicular Communications: Survey and Challenges of Channel and Propagation Models
Venue: arXiv cs.NI 2015
Year: 2015

Vehicular communication is characterized by a dynamic environment, high mobility, and comparatively low antenna heights on the communicating entities (vehicles and roadside units). These characteristics make vehicular propagation and channel modeling particularly challenging. In this article, we classify and describe the most relevant vehicular propagation and channel models, with a particular focus on the usability of the models for the evaluation of protocols and applications. We first classify the models based on the propagation mechanisms they employ and their implementation approach. We also classify the models based on the channel properties they implement and pay special attention to the usability of the models, including the complexity of implementation, scalability, and the input requirements (e.g., geographical data input). We also discuss the less-explored aspects in vehicular channel modeling, including modeling specific environments (e.g., tunnels, overpasses, and parking lots) and types of communicating vehicles (e.g., scooters and public transportation vehicles). We conclude by identifying the underresearched aspects of vehicular propagation and channel modeling that require further modeling and measurement studies.
A randomized covering-packing duality between source-coding and channel-coding
Venue: arXiv cs.IT 2015
Year: 2015

A randomized covering-packing duality between source and channel coding will be discussed by considering the source coding problem of coding a source with a certain distortion level and by considering a channel which communicates the source within a certain distortion level. An operational view of source-channel separation for communication with a fidelity criterion will be discussed in brief.
Keyphrase Based Evaluation of Automatic Text Summarization
Venue: arXiv cs.CL 2015
Year: 2015

The development of methods to deal with the informative contents of the text units in the matching process is a major challenge in automatic summary evaluation systems that use fixed n-gram matching. The limitation causes inaccurate matching between units in a peer and reference summaries. The present study introduces a new Keyphrase based Summary Evaluator KpEval for evaluating automatic summaries. The KpEval relies on the keyphrases since they convey the most important concepts of a text. In the evaluation process, the keyphrases are used in their lemma form as the matching text unit. The system was applied to evaluate different summaries of Arabic multi-document data set presented at TAC2011. The results showed that the new evaluation technique correlates well with the known evaluation systems: Rouge1, Rouge2, RougeSU4, and AutoSummENG MeMoG. KpEval has the strongest correlation with AutoSummENG MeMoG, Pearson and spearman correlation coefficient measures are 0.8840, 0.9667 respectively.
On the Tradeoff between Energy Harvesting and Caching in Wireless Networks
Venue: arXiv cs.IT 2015
Year: 2015

Self-powered, energy harvesting small cell base stations (SBS) are expected to be an integral part of next-generation wireless networks. However, due to uncertainties in harvested energy, it is necessary to adopt energy efficient power control schemes to reduce an SBSs' energy consumption and thus ensure quality-of-service (QoS) for users. Such energy-efficient design can also be done via the use of content caching which reduces the usage of the capacity-limited SBS backhaul. of popular content at SBS can also prove beneficial in this regard by reducing the backhaul usage. In this paper, an online energy efficient power control scheme is developed for an energy harvesting SBS equipped with a wireless backhaul and local storage. In our model, energy arrivals are assumed to be Poisson distributed and the popularity distribution of requested content is modeled using Zipf's law. The power control problem is formulated as a (discounted) infinite horizon dynamic programming problem and solved numerically using the value iteration algorithm. Using simulations, we provide valuable insights on the impact of energy harvesting and caching on the energy and sum-throughput performance of the SBS as the network size is varied. Our results also show that the size of cache and energy harvesting equipment at the SBS can be traded off, while still meeting the desired system performance.
Infinite subgame perfect equilibrium in the Hausdorff difference hierarchy
Venue: arXiv cs.GT 2015
Year: 2015

Subgame perfect equilibria are specific Nash equilibria in perfect information games in extensive form. They are important because they relate to the rationality of the players. They always exist in infinite games with continuous real-valued payoffs, but may fail to exist even in simple games with slightly discontinuous payoffs. This article considers only games whose outcome functions are measurable in the Hausdorff difference hierarchy of the open sets (\textit{i.e.} $Δ^0_2$ when in the Baire space), and it characterizes the families of linear preferences such that every game using these preferences has a subgame perfect equilibrium: the preferences without infinite ascending chains (of course), and such that for all players $a$ and $b$ and outcomes $x,y,z$ we have $\neg(z <_a y <_a x \,\wedge\, x <_b z <_b y)$. Moreover at each node of the game, the equilibrium constructed for the proof is Pareto-optimal among all the outcomes occurring in the subgame. Additional results for non-linear preferences are presented.
The evolutionary origins of hierarchy
Venue: arXiv cs.NE 2015
Year: 2015

Hierarchical organization -- the recursive composition of sub-modules -- is ubiquitous in biological networks, including neural, metabolic, ecological, and genetic regulatory networks, and in human-made systems, such as large organizations and the Internet. To date, most research on hierarchy in networks has been limited to quantifying this property. However, an open, important question in evolutionary biology is why hierarchical organization evolves in the first place. It has recently been shown that modularity evolves because of the presence of a cost for network connections. Here we investigate whether such connection costs also tend to cause a hierarchical organization of such modules. In computational simulations, we find that networks without a connection cost do not evolve to be hierarchical, even when the task has a hierarchical structure. However, with a connection cost, networks evolve to be both modular and hierarchical, and these networks exhibit higher overall performance and evolvability (i.e. faster adaptation to new environments). Additional analyses confirm that hierarchy independently improves adaptability after controlling for modularity. Overall, our results suggest that the same force--the cost of connections--promotes the evolution of both hierarchy and modularity, and that these properties are important drivers of network performance and adaptability. In addition to shedding light on the emergence of hierarchy across the many domains in which it appears, these findings will also accelerate future research into evolving more complex, intelligent computational brains in the fields of artificial intelligence and robotics.
Deep Speaker Vectors for Semi Text-independent Speaker Verification
Venue: arXiv cs.CL 2015
Year: 2015

Recent research shows that deep neural networks (DNNs) can be used to extract deep speaker vectors (d-vectors) that preserve speaker characteristics and can be used in speaker verification. This new method has been tested on text-dependent speaker verification tasks, and improvement was reported when combined with the conventional i-vector method. This paper extends the d-vector approach to semi text-independent speaker verification tasks, i.e., the text of the speech is in a limited set of short phrases. We explore various settings of the DNN structure used for d-vector extraction, and present a phone-dependent training which employs the posterior features obtained from an ASR system. The experimental results show that it is possible to apply d-vectors on semi text-independent speaker recognition, and the phone-dependent training improves system performance.
Affine and Regional Dynamic Time Warpng
Venue: arXiv cs.CV 2015
Year: 2015

Pointwise matches between two time series are of great importance in time series analysis, and dynamic time warping (DTW) is known to provide generally reasonable matches. There are situations where time series alignment should be invariant to scaling and offset in amplitude or where local regions of the considered time series should be strongly reflected in pointwise matches. Two different variants of DTW, affine DTW (ADTW) and regional DTW (RDTW), are proposed to handle scaling and offset in amplitude and provide regional emphasis respectively. Furthermore, ADTW and RDTW can be combined in two different ways to generate alignments that incorporate advantages from both methods, where the affine model can be applied either globally to the entire time series or locally to each region. The proposed alignment methods outperform DTW on specific simulated datasets, and one-nearest-neighbor classifiers using their associated difference measures are competitive with the difference measures associated with state-of-the-art alignment methods on real datasets.