OpenRaiser/Intern-Atlas huggingface dataset:
Tight Approximation Bounds for the Seminar Assignment Problem
Venue: arXiv cs.DS 2016
Year: 2016

The seminar assignment problem is a variant of the generalized assignment problem in which items have unit size and the amount of space allowed in each bin is restricted to an arbitrary set of values. The problem has been shown to be NP-complete and to not admit a PTAS. However, the only constant factor approximation algorithm known to date is randomized and it is not guaranteed to always produce a feasible solution. In this paper we show that a natural greedy algorithm outputs a solution with value within a factor of $(1 - e^{-1})$ of the optimal, and that unless $NP\subseteq DTIME(n^{\log\log n})$, this is the best approximation guarantee achievable by any polynomial time algorithm.
Power-Law Distributions in a Two-sided Market and Net Neutrality
Venue: arXiv cs.GT 2016
Year: 2016

"Net neutrality" often refers to the policy dictating that an Internet service provider (ISP) cannot charge content providers (CPs) for delivering their content to consumers. Many past quantitative models designed to determine whether net neutrality is a good idea have been rather equivocal in their conclusions. Here we propose a very simple two-sided market model, in which the types of the consumers and the CPs are {\em power-law distributed} --- a kind of distribution known to often arise precisely in connection with Internet-related phenomena. We derive mostly analytical, closed-form results for several regimes: (a) Net neutrality, (b) social optimum, (c) maximum revenue by the ISP, or (d) maximum ISP revenue under quality differentiation. One unexpected conclusion is that (a) and (b) will differ significantly, unless average CP productivity is very high.
Power Control for Packet Streaming with Head-of-Line Deadlines
Venue: arXiv cs.NI 2016
Year: 2016

We consider a mathematical model for streaming media packets (as the motivating key example) from a transmitter buffer to a receiver over a wireless link while controlling the transmitter power (hence, the packet/job processing rate). When each packet comes to the head-of-line (HOL) in the buffer, it is given a deadline $D$ which is the maximum number of times the transmitter can attempt retransmission in order to successfully transmit the packet. If this number of transmission attempts is exhausted, the packet is ejected from the buffer and the next packet comes to the HOL. Costs are incurred in each time slot for holding packets in the buffer, expending transmitter power, and ejecting packets which exceed their deadlines. We investigate how transmission power should be chosen so as to minimize the total cost of transmitting the items in the buffer. We formulate the optimal power control problem in a dynamic programming framework and then hone in on the special case of fixed interference. For this special case, we are able to provide a precise analytic characterization of how the power control should vary with the backlog and how the power control should react to approaching deadlines. In particular, we show monotonicity results for how the transmitter should adapt power levels to the backlog and approaching deadlines. We leverage these analytic results from the special case to build a power control scheme for the general case. Monte Carlo simulations are used to evaluate the performance of the resulting power control scheme as compared to the optimal scheme. The resulting power control scheme is sub-optimal but it provides a low-complexity approximation of the optimal power control. Simulations show that our proposed schemes outperform benchmark algorithms. We also discuss applications of the model to other practical operational scenarios.
Making Mainstream Synthesizers with Csound
Venue: arXiv cs.SD 2016
Year: 2016

For more than the past twenty years, Csound has been one of the leaders in the world of the computer music research, implementing innovative synthesis methods and making them available beyond the academic environments from which they often arise, and into the hands of musicians and sound designers throughout the world. In its present state, Csound offers an efficient environment for sound experimentation, allowing the user to work with almost any known sound synthesis or signal processing method through its vast collection of ready-made opcodes. But despite all this potential, the shared resource of Csound instruments still lacks quality reproductions of well-known synthesizers; even with its ability to generate commercial standard user interfaces and with the possibility to compile Csound instruments in such as fashion so that they can be used with no knowledge of Csound code. To fill this gap, the authors have implemented two commercial-style synthesizers as VST plug-ins using the Csound front-end "Cabbage". This paper describes their architecture and some of the Csound specific challenges involved in the development of fully featured synthesizers.
Improving Short Utterance PLDA Speaker Verification using SUV Modelling and Utterance Partitioning Approach
Venue: arXiv cs.SD 2016
Year: 2016

This paper analyses the short utterance probabilistic linear discriminant analysis (PLDA) speaker verification with utterance partitioning and short utterance variance (SUV) modelling approaches. Experimental studies have found that instead of using single long-utterance as enrolment data, if long enrolled utterance is partitioned into multiple short utterances and average of short utterance i-vectors is used as enrolled data, that improves the Gaussian PLDA (GPLDA) speaker verification. This is because short utterance i-vectors have speaker, session and utterance variations, and utterance-partitioning approach compensates the utterance variation. Subsequently, SUV-PLDA is also studied with utterance partitioning approach, and utterance partitioning-based SUV-GPLDA system shows relative improvement of 9% and 16% in EER for NIST 2008 and NIST 2010 truncated 10sec-10sec evaluation condition as utterance partitioning approach compensates the utterance variation and SUV modelling approach compensates the mismatch between full-length development data and short-length evaluation data.
Weekly maintenance scheduling using exact and genetic methods
Venue: arXiv cs.NE 2016
Year: 2016

The weekly maintenance schedule specifies when maintenance activities should be performed on the equipment, taking into account the availability of workers and maintenance bays, and other operational constraints. The current approach to generating this schedule is labour intensive and requires coordination between the maintenance schedulers and operations staff to minimise its impact on the operation of the mine. This paper presents methods for automatically generating this schedule from the list of maintenance tasks to be performed, the availability roster of the maintenance staff, and time windows in which each piece of equipment is available for maintenance. Both Mixed-Integer Linear Programming (MILP) and genetic algorithms are evaluated, with the genetic algorithm shown to significantly outperform the MILP. Two fitness functions for the genetic algorithm are also examined, with a linear fitness function outperforming an inverse fitness function by up to 5% for the same calculation time. The genetic algorithm approach is computationally fast, allowing the schedule to be rapidly recalculated in response to unexpected delays and breakdowns.
Formalising Real Numbers in Homotopy Type Theory
Venue: arXiv cs.LO 2016
Year: 2016

Cauchy reals can be defined as a quotient of Cauchy sequences of rationals. The limit of a Cauchy sequence of Cauchy reals is defined through lifting it to a sequence of Cauchy sequences of rationals. This lifting requires the axiom of countable choice or excluded middle, neither of which is available in homotopy type theory. To address this, the Univalent Foundations Program uses a higher inductive-inductive type to define the Cauchy reals as the free Cauchy complete metric space generated by the rationals. We generalize this construction to define the free Cauchy complete metric space generated by an arbitrary metric space. This forms a monad in the category of metric spaces with Lipschitz functions. When applied to the rationals it defines the Cauchy reals. Finally, we can use Altenkirch and Danielson (2016)'s partiality monad to define a semi-decision procedure comparing a real number and a rational number. The entire construction has been formalized in the Coq proof assistant. It is available at https://github.com/SkySkimmer/HoTTClasses/tree/CPP2017 .
Towards an Accurate Mathematical Model of Generic Nominally-Typed OOP
Venue: arXiv cs.PL 2016
Year: 2016

The construction of GNOOP as a domain-theoretic model of generic nominally-typed OOP is currently underway. This extended abstract presents the concepts of `nominal intervals' and `full generication' that are likely to help in building GNOOP as an accurate mathematical model of generic nominally-typed OOP. The abstract also presents few related category-theoretic suggestions. The presented concepts and suggestions are particularly geared towards enabling GNOOP to offer a precise and simple view of so-far-hard-to-analyze features of generic OOP such as variance annotations (e.g., Java wildcard types) and erased generics (e.g., Java type erasure).
Risk-Aware Algorithms for Adversarial Contextual Bandits
Venue: arXiv cs.LG 2016
Year: 2016

In this work we consider adversarial contextual bandits with risk constraints. At each round, nature prepares a context, a cost for each arm, and additionally a risk for each arm. The learner leverages the context to pull an arm and then receives the corresponding cost and risk associated with the pulled arm. In addition to minimizing the cumulative cost, the learner also needs to satisfy long-term risk constraints -- the average of the cumulative risk from all pulled arms should not be larger than a pre-defined threshold. To address this problem, we first study the full information setting where in each round the learner receives an adversarial convex loss and a convex constraint. We develop a meta algorithm leveraging online mirror descent for the full information setting and extend it to contextual bandit with risk constraints setting using expert advice. Our algorithms can achieve near-optimal regret in terms of minimizing the total cost, while successfully maintaining a sublinear growth of cumulative risk constraint violation.
Neural Machine Translation Advised by Statistical Machine Translation
Venue: arXiv cs.CL 2016
Year: 2016

Neural Machine Translation (NMT) is a new approach to machine translation that has made great progress in recent years. However, recent studies show that NMT generally produces fluent but inadequate translations (Tu et al. 2016b; Tu et al. 2016a; He et al. 2016; Tu et al. 2017). This is in contrast to conventional Statistical Machine Translation (SMT), which usually yields adequate but non-fluent translations. It is natural, therefore, to leverage the advantages of both models for better translations, and in this work we propose to incorporate SMT model into NMT framework. More specifically, at each decoding step, SMT offers additional recommendations of generated words based on the decoding information from NMT (e.g., the generated partial translation and attention history). Then we employ an auxiliary classifier to score the SMT recommendations and a gating function to combine the SMT recommendations with NMT generations, both of which are jointly trained within the NMT architecture in an end-to-end manner. Experimental results on Chinese-English translation show that the proposed approach achieves significant and consistent improvements over state-of-the-art NMT and SMT systems on multiple NIST test sets.
On Optimizing Hierarchical Modulation in AWGN channel
Venue: arXiv cs.IT 2016
Year: 2016

Hierarchical modulation (HM) is able to provide different levels of protection for data streams and achieve a rate region that cannot be realized by traditional orthogonal schemes, such as time division (TD). Nevertheless, criterions and algorithms for general HM design are not available in existing literatures. In this paper, we jointly optimize the constellation positions and binary labels for HM to be used in additive white gaussian noise (AWGN) channel. Based on bit-interleaved coded modulation (BICM) with successive interference cancellation (SIC) capacity, our main purpose is to maximize the rate of one data stream, with power constrains and the constrain that the rate of other data streams should be larger than given thresholds. Multi-start interior-point algorithm is used to carry out the constellation optimization problems and methods to reduce optimization complexity are also proposed in this paper. Numerical results verify the performance gains of optimized HM compared with optimized quadrature amplidude modulation (QAM) based HM and other orthogonal transmission methods.
Towards the Leveraging of Data Deduplication to Break the Disk Acquisition Speed Limit
Venue: arXiv cs.CY 2016
Year: 2016

Digital forensic evidence acquisition speed is traditionally limited by two main factors: the read speed of the storage device being investigated, i.e., the read speed of the disk, memory, remote storage, mobile device, etc.), and the write speed of the system used for storing the acquired data. Digital forensic investigators can somewhat mitigate the latter issue through the use of high-speed storage options, such as networked RAID storage, in the controlled environment of the forensic laboratory. However, traditionally, little can be done to improve the acquisition speed past its physical read speed from the target device itself. The protracted time taken for data acquisition wastes digital forensic experts' time, contributes to digital forensic investigation backlogs worldwide, and delays pertinent information from potentially influencing the direction of an investigation. In a remote acquisition scenario, a third contributing factor can also become a detriment to the overall acquisition time - typically the Internet upload speed of the acquisition system. This paper explores an alternative to the traditional evidence acquisition model through the leveraging of a forensic data deduplication system. The advantages that a deduplicated approach can provide over the current digital forensic evidence acquisition process are outlined and some preliminary results of a prototype implementation are discussed.
An Interactive Machine Learning Framework
Venue: arXiv cs.HC 2016
Year: 2016

Machine learning (ML) is believed to be an effective and efficient tool to build reliable prediction model or extract useful structure from an avalanche of data. However, ML is also criticized by its difficulty in interpretation and complicated parameter tuning. In contrast, visualization is able to well organize and visually encode the entangled information in data and guild audiences to simpler perceptual inferences and analytic thinking. But large scale and high dimensional data will usually lead to the failure of many visualization methods. In this paper, we close a loop between ML and visualization via interaction between ML algorithm and users, so machine intelligence and human intelligence can cooperate and improve each other in a mutually rewarding way. In particular, we propose "transparent boosting tree (TBT)", which visualizes both the model structure and prediction statistics of each step in the learning process of gradient boosting tree to user, and involves user's feedback operations to trees into the learning process. In TBT, ML is in charge of updating weights in learning model and filtering information shown to user from the big data, while visualization is in charge of providing a visual understanding of ML model to facilitate user exploration. It combines the advantages of both ML in big data statistics and human in decision making based on domain knowledge. We develop a user friendly interface for this novel learning method, and apply it to two datasets collected from real applications. Our study shows that making ML transparent by using interactive visualization can significantly improve the exploration of ML algorithms, give rise to novel insights of ML models, and integrates both machine and human intelligence.
Simulation of electrical machines - A FEM-BEM coupling scheme
Venue: arXiv cs.CE 2016
Year: 2016

Electrical machines commonly consist of moving and stationary parts. The field simulation of such devices can be very demanding if the underlying numerical scheme is solely based on a domain discretization, such as in case of the Finite Element Method (FEM). Here, a coupling scheme based on FEM together with Boundary Element Methods (BEM) is presented that neither hinges on re-meshing techniques nor deals with a special treatment of sliding interfaces. While the numerics are certainly more involved the reward is obvious: The modeling costs decrease and the application engineer is provided with an easy-to-use, versatile, and accurate simulation tool.
SoK: An Analysis of Protocol Design: Avoiding Traps for Implementation and Deployment
Venue: arXiv cs.CR 2016
Year: 2016

Today's Internet utilizes a multitude of different protocols. While some of these protocols were first implemented and used and later documented, other were first specified and then implemented. Regardless of how protocols came to be, their definitions can contain traps that lead to insecure implementations or deployments. A classical example is insufficiently strict authentication requirements in a protocol specification. The resulting Misconfigurations, i.e., not enabling strong authentication, are common root causes for Internet security incidents. Indeed, Internet protocols have been commonly designed without security in mind which leads to a multitude of misconfiguration traps. While this is slowly changing, to strict security considerations can have a similarly bad effect. Due to complex implementations and insufficient documentation, security features may remain unused, leaving deployments vulnerable. In this paper we provide a systematization of the security traps found in common Internet protocols. By separating protocols in four classes we identify major factors that lead to common security traps. These insights together with observations about end-user centric usability and security by default are then used to derive recommendations for improving existing and designing new protocols---without such security sensitive traps for operators, implementors and users.
Weighted Positive Binary Decision Diagrams for Exact Probabilistic Inference
Venue: arXiv cs.AI 2016
Year: 2016

Recent work on weighted model counting has been very successfully applied to the problem of probabilistic inference in Bayesian networks. The probability distribution is encoded into a Boolean normal form and compiled to a target language, in order to represent local structure expressed among conditional probabilities more efficiently. We show that further improvements are possible, by exploiting the knowledge that is lost during the encoding phase and incorporating it into a compiler inspired by Satisfiability Modulo Theories. Constraints among variables are used as a background theory, which allows us to optimize the Shannon decomposition. We propose a new language, called Weighted Positive Binary Decision Diagrams, that reduces the cost of probabilistic inference by using this decomposition variant to induce an arithmetic circuit of reduced size.
Auxiliary Beam Pair Enabled AoD and AoA Estimation in Closed-Loop Large-Scale mmWave MIMO Systems
Venue: arXiv cs.IT 2016
Year: 2016

Channel estimation is of critical importance in millimeter-wave (mmWave) multiple-input multiple-output (MIMO) systems. Due to the use of large antenna arrays, low-complexity mmWave specific channel estimation algorithms are required. In this paper, an auxiliary beam pair design is proposed to provide high-resolution estimates of the channel's angle-of-departure (AoD) and angle-of-arrival (AoA) for mmWave MIMO systems. By performing an amplitude comparison with respect to each auxiliary beam pair, a set of ratio measures that characterize the channel's AoD and AoA are obtained by the receiver. Either the best ratio measure or the estimated AoD is quantized and fed back to the transmitter via a feedback channel. The proposed technique can be incorporated into control channel design to minimize initial access delay. Though the design principles are derived assuming a high-power regime, evaluation under more realistic assumption shows that by employing the proposed method, good angle estimation performance is achieved under various signal-to-noise ratio levels and channel conditions.
High-performance K-means Implementation based on a Simplified Map-Reduce Architecture
Venue: arXiv cs.DC 2016
Year: 2016

The k-means algorithm is one of the most common clustering algorithms and widely used in data mining and pattern recognition. The increasing computational requirement of big data applications makes hardware acceleration for the k-means algorithm necessary. In this paper, a simplified Map-Reduce architecture is proposed to implement the k-means algorithm on an FPGA. Algorithmic segmentation, data path elaboration and automatic control are applied to optimize the architecture for high performance. In addition, high level synthesis technique is utilized to reduce development cycles and complexity. For a single iteration in the k-means algorithm, a throughput of 28.74 Gbps is achieved. The performance shows at least 3.93x speedup compared with four representative existing FPGA-based implementations and can satisfy the demand of big data applications.
Compositional Synthesis of Leakage Resilient Programs
Venue: arXiv cs.CR 2016
Year: 2016

A promising approach to defend against side channel attacks is to build programs that are leakage resilient, in a formal sense. One such formal notion of leakage resilience is the n-threshold-probing model proposed in the seminal work by Ishai et al. In a recent work, Eldib and Wang have proposed a method for automatically synthesizing programs that are leakage resilient according to this model, for the case n=1. In this paper, we show that the n-threshold-probing model of leakage resilience enjoys a certain compositionality property that can be exploited for synthesis. We use the property to design a synthesis method that efficiently synthesizes leakage-resilient programs in a compositional manner, for the general case of n > 1. We have implemented a prototype of the synthesis algorithm, and we demonstrate its effectiveness by synthesizing leakage-resilient versions of benchmarks taken from the literature.
Low-rank and Sparse Soft Targets to Learn Better DNN Acoustic Models
Venue: arXiv cs.CL 2016
Year: 2016

Conventional deep neural networks (DNN) for speech acoustic modeling rely on Gaussian mixture models (GMM) and hidden Markov model (HMM) to obtain binary class labels as the targets for DNN training. Subword classes in speech recognition systems correspond to context-dependent tied states or senones. The present work addresses some limitations of GMM-HMM senone alignments for DNN training. We hypothesize that the senone probabilities obtained from a DNN trained with binary labels can provide more accurate targets to learn better acoustic models. However, DNN outputs bear inaccuracies which are exhibited as high dimensional unstructured noise, whereas the informative components are structured and low-dimensional. We exploit principle component analysis (PCA) and sparse coding to characterize the senone subspaces. Enhanced probabilities obtained from low-rank and sparse reconstructions are used as soft-targets for DNN acoustic modeling, that also enables training with untranscribed data. Experiments conducted on AMI corpus shows 4.6% relative reduction in word error rate.