OpenRaiser/Intern-Atlas huggingface dataset:
Universal representations:The missing link between faces, text, planktons, and cat breeds
Venue: arXiv cs.CV 2017
Year: 2017

With the advent of large labelled datasets and high-capacity models, the performance of machine vision systems has been improving rapidly. However, the technology has still major limitations, starting from the fact that different vision problems are still solved by different models, trained from scratch or fine-tuned on the target data. The human visual system, in stark contrast, learns a universal representation for vision in the early life of an individual. This representation works well for an enormous variety of vision problems, with little or no change, with the major advantage of requiring little training data to solve any of them. In this paper we investigate whether neural networks may work as universal representations by studying their capacity in relation to the â€œsizeâ€ of a large combination of vision problems. We do so by showing that a single neural network can learn simultaneously several very different visual domains (from sketches to planktons and MNIST digits) as well as, or better than, a number of specialized networks. However, we also show that this requires to carefully normalize the information in the network, by using domain-specific scaling factors or, more generically, by using an instance normalization layer.
Divergence Scaling of Fixed-Length, Binary-Output, One-to-One Distribution Matching
Venue: arXiv cs.IT 2017
Year: 2017

Distribution matching is the process of invertibly mapping a uniformly distributed input sequence onto sequences that approximate the output of a desired discrete memoryless source. The special case of a binary output alphabet and one-to-one mapping is studied. A fixed-length distribution matcher is proposed that is optimal in the sense of minimizing the unnormalized informational divergence between its output distribution and a binary memoryless target distribution. Upper and lower bounds on the unnormalized divergence are computed that increase logarithmically in the output block length $n$. It follows that a recently proposed constant composition distribution matcher performs within a constant gap of the minimal achievable informational divergence.
Energy Efficient Mobile Edge Computing in Dense Cellular Networks
Venue: arXiv cs.NI 2017
Year: 2017

Merging Mobile Edge Computing (MEC), which is an emerging paradigm to meet the increasing computation demands from mobile devices, with the dense deployment of Base Stations (BSs), is foreseen as a key step towards the next generation mobile networks. However, new challenges arise for designing energy efficient networks since radio access resources and computing resources of BSs have to be jointly managed, and yet they are complexly coupled with traffic in both spatial and temporal domains. In this paper, we address the challenge of incorporating MEC into dense cellular networks, and propose an efficient online algorithm, called ENGINE (ENErgy constrained offloadINg and slEeping) which makes joint computation offloading and BS sleeping decisions in order to maximize the quality of service while keeping the energy consumption low. Our algorithm leverages Lyapunov optimization technique, works online and achieves a close-to-optimal performance without using future information. Our simulation results show that our algorithm can effectively reduce energy consumption without sacrificing the user quality of service.
Joint Power Allocation and Beamforming for Energy-Efficient Two-Way Multi-Relay Communications
Venue: arXiv cs.IT 2017
Year: 2017

This paper considers the joint design of user power allocation and relay beamforming in relaying communications, in which multiple pairs of single-antenna users exchange information with each other via multiple-antenna relays in two time slots. All users transmit their signals to the relays in the first time slot while the relays broadcast the beamformed signals to all users in the second time slot. The aim is to maximize the system's energy efficiency (EE) subject to quality-of-service (QoS) constraints in terms of exchange throughput requirements. The QoS constraints are nonconvex with many nonlinear cross-terms, so finding a feasible point is already computationally challenging. The sum throughput appears in the numerator while the total consumption power appears in the denominator of the EE objective function. The former is a nonconcave function and the latter is a nonconvex function, making fractional programming useless for EE optimization. Nevertheless, efficient iterations of low complexity to obtain its optimized solutions are developed. The performances of the multiple-user and multiple-relay networks under various scenarios are evaluated to show the merit of the paper development.
Hardware Translation Coherence for Virtualized Systems
Venue: arXiv cs.AR 2017
Year: 2017

To improve system performance, modern operating systems (OSes) often undertake activities that require modification of virtual-to-physical page translation mappings. For example, the OS may migrate data between physical frames to defragment memory and enable superpages. The OS may migrate pages of data between heterogeneous memory devices. We refer to all such activities as page remappings. Unfortunately, page remappings are expensive. We show that translation coherence is a major culprit and that systems employing virtualization are especially badly affected by their overheads. In response, we propose hardware translation invalidation and coherence or HATRIC, a readily implementable hardware mechanism to piggyback translation coherence atop existing cache coherence protocols. We perform detailed studies using KVM-based virtualization, showing that HATRIC achieves up to 30% performance and 10% energy benefits, for per-CPU area overheads of 2%. We also quantify HATRIC's benefits on systems running Xen and find up to 33% performance improvements.
GNC of the SphereX Robot for Extreme Environment Exploration on Mars
Venue: arXiv cs.RO 2017
Year: 2017

Wheeled ground robots are limited from exploring extreme environments such as caves, lava tubes and skylights. Small robots that can utilize unconventional mobility through hopping, flying or rolling can overcome these limitations. Mul-tiple robots operating as a team offer significant benefits over a single large ro-bot, as they are not prone to single-point failure, enable distributed command and control and enable execution of tasks in parallel. These robots can complement large rovers and landers, helping to explore inaccessible sites, obtaining samples and for planning future exploration missions. Our robots, the SphereX, are 3-kg in mass, spherical and contain computers equivalent to current smartphones. They contain an array of guidance, navigation and control sensors and electronics. SphereX contains room for a 1-kg science payload, including for sample return. Our work in this field has recognized the need for miniaturized chemical mobility systems that provide power and propulsion. Our research explored the use of miniature rockets, including solid rockets, bi-propellants including RP1/hydrogen-peroxide and polyurethane/ammonium-perchlorate. These propulsion options provide maximum flight times of 10 minutes on Mars. Flying, especially hovering consumes significant fuel; hence, we have been developing our robots to perform ballistic hops that enable the robots to travel efficiently over long distances. Techniques are being developed to enable mid-course correction during a ballistic hop. Using multiple cameras, it is possible to reconstitute an image scene from motion blur. Hence our approach is to enable photo mapping as the robots travel on a ballistic hop. The same images would also be used for navigation and path planning. Using our proposed design approach, we are developing low-cost methods for surface exploration of planetary bodies using a network of small robots.
On the Design of Distributed Programming Models
Venue: arXiv cs.DC 2017
Year: 2017

Programming large-scale distributed applications requires new abstractions and models to be done well. We demonstrate that these models are possible. Following from both the FLP result and CAP theorem, we show that concurrent programming models are necessary, but not sufficient, in the construction of large-scale distributed systems because of the problem of failure and network partitions: languages need to be able to capture and encode the tradeoffs between consistency and availability. We present two programming models, Lasp and Austere, each of which makes a strong tradeoff with respects to the CAP theorem. These two models outline the bounds of distributed model design: strictly AP or strictly CP. We argue that all possible distributed programming models must come from this design space, and present one practical design that allows declarative specification of consistency tradeoffs, called Spry.
Traffic models with adversarial vehicle behaviour
Venue: arXiv cs.CR 2017
Year: 2017

We examine the impact of adversarial actions on vehicles in traffic. Current advances in assisted/autonomous driving technologies are supposed to reduce the number of casualties, but this seems to be desired despite the recently proved insecurity of in-vehicle communication buses or components. Fortunately to some extent, while compromised cars have become a reality, the numerous attacks reported so far on in-vehicle electronics are exclusively concerned with impairments of a single target. In this work we put adversarial behavior under a more complex scenario where driving decisions deluded by corrupted electronics can affect more than one vehicle. Particularly, we focus our attention on chain collisions involving multiple vehicles that can be amplified by simple adversarial interventions, e.g., delaying taillights or falsifying speedometer readings. We provide metrics for assessing adversarial impact and consider safety margins against adversarial actions. Moreover, we discuss intelligent adversarial behaviour by which the creation of rogue platoons is possible and speed manipulations become stealthy to human drivers. We emphasize that our work does not try to show the mere fact that imprudent speeds and headways lead to chain-collisions, but points out that an adversary may favour such scenarios (eventually keeping his actions stealthy for human drivers) and further asks for quantifying the impact of adversarial activity or whether existing traffic regulations are prepared for such situations.
Sparse Ternary Codes for similarity search have higher coding gain than dense binary codes
Venue: arXiv cs.IT 2017
Year: 2017

This paper addresses the problem of Approximate Nearest Neighbor (ANN) search in pattern recognition where feature vectors in a database are encoded as compact codes in order to speed-up the similarity search in large-scale databases. Considering the ANN problem from an information-theoretic perspective, we interpret it as an encoding, which maps the original feature vectors to a less entropic sparse representation while requiring them to be as informative as possible. We then define the coding gain for ANN search using information-theoretic measures. We next show that the classical approach to this problem, which consists of binarization of the projected vectors is sub-optimal. Instead, a properly designed ternary encoding achieves higher coding gains and lower complexity.
Biologically Feasible Gene Trees, Reconciliation Maps and Informative Triples
Venue: arXiv cs.DM 2017
Year: 2017

The history of gene families - which are equivalent to \emph{event-labeled} gene trees - can be reconstructed from empirically estimated evolutionary event-relations containing pairs of orthologous, paralogous or xenologous genes. The question then arises as whether inferred event-labeled gene trees are \emph{biologically feasible}, that is, if there is a possible true history that would explain a given gene tree. In practice, this problem is boiled down to finding a reconciliation map - also known as DTL-scenario - between the event-labeled gene trees and a (possibly unknown) species tree. In this contribution, we first characterize whether there is a valid reconciliation map for binary event-labeled gene trees $T$ that contain speciation, duplication and horizontal gene transfer events and some unknown species tree $S$ in terms of "informative" triples that are displayed in $T$ and provide information of the topology of $S$. These informative triples are used to infer the unknown species tree $S$ for $T$. We obtain a similar result for non-binary gene trees. To this end, however, the reconciliation map needs to be further restricted. We provide a polynomial-time algorithm to decide whether there is a species tree for a given event-labeled gene tree, and in the positive case, to construct the species tree and the respective (restricted) reconciliation map. However, informative triples as well as DTL-scenarios have its limitations when they are used to explain the biological feasibility of gene trees. While reconciliation maps imply biological feasibility, we show that the converse is not true in general. Moreover, we show that informative triples do neither provide enough information to characterize "relaxed" DTL-scenarios nor non-restricted reconciliation maps for non-binary biologically feasible gene trees.
Analogy and duality between random channel coding and lossy source coding
Venue: arXiv cs.IT 2017
Year: 2017

Here we write in a unified fashion (using "R(P, Q, D)") the random coding exponents in channel coding and lossy source coding. We derive their explicit forms and show, that, for a given random codebook distribution Q, the channel decoding error exponent can be viewed as an encoding success exponent in lossy source coding, and the channel correct-decoding exponent can be viewed as an encoding failure exponent in lossy source coding. We then extend the channel exponents to arbitrary D, which corresponds for D > 0 to erasure decoding and for D < 0 to list decoding. For comparison, we also derive the exact random coding exponent for Forney's optimum tradeoff decoder.
Fast Xor-based Erasure Coding based on Polynomial Ring Transforms
Venue: arXiv cs.IT 2017
Year: 2017

The complexity of software implementations of MDS erasure codes mainly depends on the efficiency of the finite field operations implementation. In this paper, we propose a method to reduce the complexity of the finite field multiplication by using fast transforms between a field and a ring to perform the multiplication in a ring. We show that moving to a ring reduces the complexity of the operations. Then, we show that this construction allows the use of simple scheduling to reduce the number of operations.
Information-geometrical characterization of statistical models which are statistically equivalent to probability simplexes
Venue: arXiv cs.IT 2017
Year: 2017

The probability simplex is the set of all probability distributions on a finite set and is the most fundamental object in the finite probability theory. In this paper we give a characterization of statistical models on finite sets which are statistically equivalent to probability simplexes in terms of $α$-families including exponential families and mixture families. The subject has a close relation to some fundamental aspects of information geometry such as $α$-connections and autoparallelity.
An FPTAS for the parametric knapsack problem
Venue: arXiv cs.DS 2017
Year: 2017

In this paper, we investigate the parametric knapsack problem, in which the item profits are affine functions depending on a real-valued parameter. The aim is to provide a solution for all values of the parameter. It is well-known that any exact algorithm for the problem may need to output an exponential number of knapsack solutions. We present a fully polynomial-time approximation scheme (FPTAS) for the problem that, for any desired precision $\varepsilon \in (0,1)$, computes $(1-\varepsilon)$-approximate solutions for all values of the parameter. This is the first FPTAS for the parametric knapsack problem that does not require the slopes and intercepts of the affine functions to be non-negative but works for arbitrary integral values. Our FPTAS outputs $\mathcal{O}(\frac{n^2}{\varepsilon})$ knapsack solutions and runs in strongly polynomial-time $\mathcal{O}(\frac{n^4}{\varepsilon^2})$. Even for the special case of positive input data, this is the first FPTAS with a strongly polynomial running time. We also show that this time bound can be further improved to $\mathcal{O}(\frac{n^2}{\varepsilon} \cdot A(n,\varepsilon))$, where $A(n,\varepsilon)$ denotes the running time of any FPTAS for the traditional (non-parametric) knapsack problem.
Cooling Codes: Thermal-Management Coding for High-Performance Interconnects
Venue: arXiv cs.IT 2017
Year: 2017

High temperatures have dramatic negative effects on interconnect performance and, hence, numerous techniques have been proposed to reduce the power consumption of on-chip buses. However, existing methods fall short of fully addressing the thermal challenges posed by high-performance interconnects. In this paper, we introduce new efficient coding schemes that make it possible to directly control the peak temperature of a bus by effectively cooling its hottest wires. This is achieved by avoiding state transitions on the hottest wires for as long as necessary until their temperature drops off. We also reduce the average power consumption by making sure that the total number of state transitions on all the wires is below a prescribed threshold. We show how each of these two features can be coded for separately or, alternatively, how both can be achieved at the same time. In addition, error-correction for the transmitted information can be provided while controlling the peak temperature and/or the average power consumption. In general, our cooling codes use $n > k$ wires to encode a given $k$-bit bus. One of our goals herein is to determine the minimum possible number of wires $n$ needed to encode $k$ bits while satisfying any combination of the three desired properties. We provide full theoretical analysis in each case. In particular, we show that $n = k+t+1$ suffices to cool the $t$ hottest wires, and this is the best possible. Moreover, although the proposed coding schemes make use of sophisticated tools from combinatorics, discrete geometry, linear algebra, and coding theory, the resulting encoders and decoders are fully practical. They do not require significant computational overhead and can be implemented without sacrificing a large circuit area.
emLam -- a Hungarian Language Modeling baseline
Venue: arXiv cs.CL 2017
Year: 2017

This paper aims to make up for the lack of documented baselines for Hungarian language modeling. Various approaches are evaluated on three publicly available Hungarian corpora. Perplexity values comparable to models of similar-sized English corpora are reported. A new, freely downloadable Hungar- ian benchmark corpus is introduced.
On the Performance of Practical Ultra-Dense Networks: The Major and Minor Factors
Venue: arXiv cs.NI 2017
Year: 2017

In this paper, we conduct performance evaluation for Ultra-Dense Networks (UDNs), and identify which modelling factors play major roles and minor roles. From our study, we draw the following conclusions. First, there are 3 factors/models that have a major impact on the performance of UDNs, and they should be considered when performing theoretical analyses: i) a multi-piece path loss model with line-of-sight (LoS) and non-lineof- sight (NLoS) transmissions; ii) a non-zero antenna height difference between base stations (BSs) and user equipments (UEs); iii) a finite BS/UE density. Second, there are 4 factors/models that have a minor impact on the performance of UDNs, i.e., changing the results quantitatively but not qualitatively, and thus their incorporation into theoretical analyses is less urgent: i) a general multi-path fading model based on Rician fading; ii) a correlated shadow fading model; iii) a BS density dependent transmission power; iv) a deterministic BS/user density. Finally, there are 5 factors/models for future study: i) a BS vertical antenna pattern; ii) multi-antenna and/or multi-BS joint transmissions; iii) a proportional fair BS scheduler; iv) a non-uniform distribution of BSs; v) a dynamic time division duplex (TDD) or full duplex (FD) network. Our conclusions can guide researchers to downselect the assumptions in their theoretical analyses, so as to avoid unnecessarily complicated results, while still capturing the fundamentals of UDNs in a meaningful way.
Scalable Attestation Resilient to Physical Attacks for Embedded Devices in Mesh Networks
Venue: arXiv cs.CR 2017
Year: 2017

Interconnected embedded devices are increasingly used invarious scenarios, including industrial control, building automation, or emergency communication. As these systems commonly process sensitive information or perform safety critical tasks, they become appealing targets for cyber attacks. A promising technique to remotely verify the safe and secure operation of networked embedded devices is remote attestation. However, existing attestation protocols only protect against software attacks or show very limited scalability. In this paper, we present the first scalable attestation protocol for interconnected embedded devices that is resilient to physical attacks. Based on the assumption that physical attacks require an adversary to capture and disable devices for some time, our protocol identifies devices with compromised hardware and software. Compared to existing solutions, our protocol reduces ommunication complexity and runtimes by orders of magnitude, precisely identifies compromised devices, supports highly dynamic and partitioned network topologies, and is robust against failures. We show the security of our protocol and evaluate it in static as well as dynamic network topologies. Our results demonstrate that our protocol is highly efficient in well-connected networks and robust to network disruptions.
Query Performance Optimization in XML Data Warehouses
Venue: arXiv cs.DB 2017
Year: 2017

XML data warehouses form an interesting basis for decision-support applications that exploit complex data. However, native-XML database management systems (DBMSs) currently bear limited performances and it is necessary to research for ways to optimize them. In this chapter, we present two such techniques. First, we propose a join index that is specifically adapted to the multidimensional architecture of XML warehouses. It eliminates join operations while preserving the information contained in the original warehouse. Second, we present a strategy for selecting XML materialized views by clustering the query workload. To validate these proposals, we measure the response time of a set of decision-support XQueries over an XML data warehouse, with and without using our optimization techniques. Our experimental results demonstrate their efficiency, even when queries are complex and data are voluminous.