OpenRaiser/Intern-Atlas huggingface dataset:
Learning to Bid Without Knowing your Value
Venue: arXiv cs.GT 2018
Year: 2018

We address online learning in complex auction settings, such as sponsored search auctions, where the value of the bidder is unknown to her, evolving in an arbitrary manner and observed only if the bidder wins an allocation. We leverage the structure of the utility of the bidder and the partial feedback that bidders typically receive in auctions, in order to provide algorithms with regret rates against the best fixed bid in hindsight, that are exponentially faster in convergence in terms of dependence on the action space, than what would have been derived by applying a generic bandit algorithm and almost equivalent to what would have been achieved in the full information setting. Our results are enabled by analyzing a new online learning setting with outcome-based feedback, which generalizes learning with feedback graphs. We provide an online learning algorithm for this setting, of independent interest, with regret that grows only logarithmically with the number of actions and linearly only in the number of potential outcomes (the latter being very small in most auction settings). Last but not least, we show that our algorithm outperforms the bandit approach experimentally and that this performance is robust to dropping some of our theoretical assumptions or introducing noise in the feedback that the bidder receives.
Registration and Fusion of Multi-Spectral Images Using a Novel Edge Descriptor
Venue: arXiv cs.CV 2018
Year: 2018

In this paper we introduce a fully end-to-end approach for multi-spectral image registration and fusion. Our method for fusion combines images from different spectral channels into a single fused image by different approaches for low and high frequency signals. A prerequisite of fusion is a stage of geometric alignment between the spectral bands, commonly referred to as registration. Unfortunately, common methods for image registration of a single spectral channel do not yield reasonable results on images from different modalities. For that end, we introduce a new algorithm for multi-spectral image registration, based on a novel edge descriptor of feature points. Our method achieves an accurate alignment of a level that allows us to further fuse the images. As our experiments show, we produce a high quality of multi-spectral image registration and fusion under many challenging scenarios.
Capacity Upper Bounds for Deletion-Type Channels
Venue: arXiv cs.IT 2018
Year: 2018

We develop a systematic approach, based on convex programming and real analysis, for obtaining upper bounds on the capacity of the binary deletion channel and, more generally, channels with i.i.d. insertions and deletions. Other than the classical deletion channel, we give a special attention to the Poisson-repeat channel introduced by Mitzenmacher and Drinea (IEEE Transactions on Information Theory, 2006). Our framework can be applied to obtain capacity upper bounds for any repetition distribution (the deletion and Poisson-repeat channels corresponding to the special cases of Bernoulli and Poisson distributions). Our techniques essentially reduce the task of proving capacity upper bounds to maximizing a univariate, real-valued, and often concave function over a bounded interval. We show the following: 1. The capacity of the binary deletion channel with deletion probability $d$ is at most $(1-d)\logφ$ for $d\geq 1/2$, and, assuming the capacity function is convex, is at most $1-d\log(4/φ)$ for $d<1/2$, where $φ=(1+\sqrt{5})/2$ is the golden ratio. This is the first nontrivial capacity upper bound for any value of $d$ outside the limiting case $d\to 0$ that is fully explicit and proved without computer assistance. 2. We derive the first set of capacity upper bounds for the Poisson-repeat channel. 3. We derive several novel upper bounds on the capacity of the deletion channel. All upper bounds are maximums of efficiently computable, and concave, univariate real functions over a bounded domain. In turn, we upper bound these functions in terms of explicit elementary and standard special functions, whose maximums can be found even more efficiently (and sometimes, analytically, for example for $d=1/2$). Along the way, we develop several new techniques of potentially independent interest in information theory, probability, and mathematical analysis.
Bilinear Controllability of a Class of Advection-Diffusion-Reaction Systems
Venue: arXiv cs.SY 2018
Year: 2018

In this paper, we investigate the exact controllability properties of an advection-diffusion equation on a bounded domain, using time- and space-dependent velocity fields as the control parameters. This partial differential equation (PDE) is the Kolmogorov forward equation for a reflected diffusion process that models the spatiotemporal evolution of a swarm of agents. We prove that if a target probability density has bounded first-order weak derivatives and is uniformly bounded from below by a positive constant, then it can be reached in finite time using control inputs that are bounded in space and time. We then extend this controllability result to a class of advection-diffusion-reaction PDEs that corresponds to a hybrid-switching diffusion process (HSDP), in which case the reaction parameters are additionally incorporated as the control inputs. Our proof for controllability of the advection-diffusion equation is constructive and is based on linear operator semigroup theoretic arguments and spectral properties of the multiplicatively perturbed Neumann Laplacian. For the HSDP, we first constructively prove controllability of the associated continuous-time Markov chain (CTMC) system, in which the state space is finite. Then we show that our controllability results for the advection-diffusion equation and the CTMC can be combined to establish controllability of the forward equation of the HSDP. Lastly, we provide constructive solutions to the problem of asymptotically stabilizing an HSDP to a target non-negative stationary distribution using time-independent state feedback laws, which correspond to spatially-dependent coefficients of the associated system of PDEs.
Probabilistic Model Checking for Continuous Time Markov Chains via Sequential Bayesian Inference
Venue: arXiv cs.LO 2018
Year: 2018

Probabilistic model checking for systems with large or unbounded state space is a challenging computational problem in formal modelling and its applications. Numerical algorithms require an explicit representation of the state space, while statistical approaches require a large number of samples to estimate the desired properties with high confidence. Here, we show how model checking of time-bounded path properties can be recast exactly as a Bayesian inference problem. In this novel formulation the problem can be efficiently approximated using techniques from machine learning. Our approach is inspired by a recent result in statistical physics which derived closed form differential equations for the first-passage time distribution of stochastic processes. We show on a number of non-trivial case studies that our method achieves both high accuracy and significant computational gains compared to statistical model checking.
Throughput Maximization for Delay-Sensitive Random Access Communication
Venue: arXiv cs.IT 2018
Year: 2018

Future 5G cellular networks supporting ultra-reliable, low-latency communications (URLLC) could employ random access communication to reduce the overhead compared to scheduled access techniques used in 4G networks. We consider a wireless communication system where multiple devices transmit payloads of a given fixed size in a random access fashion over shared radio resources to a common receiver. We allow retransmissions and assume Chase combining at the receiver. The radio resources are partitioned in the time and frequency dimensions, and we determine the optimal partition granularity to maximize throughput, subject to given constraints on latency and outage. In the regime of high and low signal-to-noise ratio (SNR), we derive explicit expressions for the granularity and throughput, first using a Shannon capacity approximation and then using finite block length analysis. Numerical results show that the throughput scaling results are applicable over a range of SNRs. The proposed analytical framework can provide insights for resource allocation strategies in general random access systems and in specific 5G use cases for massive URLLC uplink access.
Wirelessly Powered Crowd Sensing: Joint Power Transfer, Sensing, Compression, and Transmission
Venue: arXiv cs.IT 2018
Year: 2018

Leveraging massive numbers of sensors in user equipment as well as opportunistic human mobility, mobile crowd sensing (MCS) has emerged as a powerful paradigm, where prolonging battery life of constrained devices and motivating human involvement are two key design challenges. To address these, we envision a novel framework, named wirelessly powered crowd sensing (WPCS), which integrates MCS with wireless power transfer (WPT) for supplying the involved devices with extra energy and thus facilitating user incentivization. This paper considers a multiuser WPCS system where an access point (AP) transfers energy to multiple mobile sensors (MSs), each of which performs data sensing, compression, and transmission. Assuming lossless (data) compression, an optimization problem is formulated to simultaneously maximize data utility and minimize energy consumption at the operator side, by jointly controlling wireless-power allocation at the AP as well as sensing-data sizes, compression ratios, and sensor-transmission durations at the MSs. Given fixed compression ratios, the proposed optimal power allocation policy has the threshold-based structure with respect to a defined crowd-sensing priority function for each MS depending on both the operator configuration and the MS information. Further, for fixed sensing-data sizes, the optimal compression policy suggests that compression can reduce the total energy consumption at each MS only if the sensing-data size is sufficiently large. Our solution is also extended to the case of lossy compression, while extensive simulations are offered to confirm the efficiency of the contributed mechanisms.
On the computability of the Fréchet distance of surfaces in the bit-model of real computation
Venue: arXiv cs.CG 2018
Year: 2018

We show that the Fréchet distance of two-dimensional parametrised surfaces in a metric space is computable in the bit-model of real computation. An analogous result in the real RAM model for piecewise-linear surfaces has recently been obtained by Nayyeri and Xu (2016).
TAMU at KBP 2017: Event Nugget Detection and Coreference Resolution
Venue: arXiv cs.CL 2018
Year: 2018

In this paper, we describe TAMU's system submitted to the TAC KBP 2017 event nugget detection and coreference resolution task. Our system builds on the statistical and empirical observations made on training and development data. We found that modifiers of event nuggets tend to have unique syntactic distribution. Their parts-of-speech tags and dependency relations provides them essential characteristics that are useful in identifying their span and also defining their types and realis status. We further found that the joint modeling of event span detection and realis status identification performs better than the individual models for both tasks. Our simple system designed using minimal features achieved the micro-average F1 scores of 57.72, 44.27 and 42.47 for event span detection, type identification and realis status classification tasks respectively. Also, our system achieved the CoNLL F1 score of 27.20 in event coreference resolution task.
Can Deep Reinforcement Learning Solve Erdos-Selfridge-Spencer Games?
Venue: arXiv cs.AI 2018
Year: 2018

Deep reinforcement learning has achieved many recent successes, but our understanding of its strengths and limitations is hampered by the lack of rich environments in which we can fully characterize optimal behavior, and correspondingly diagnose individual actions against such a characterization. Here we consider a family of combinatorial games, arising from work of Erdos, Selfridge, and Spencer, and we propose their use as environments for evaluating and comparing different approaches to reinforcement learning. These games have a number of appealing features: they are challenging for current learning approaches, but they form (i) a low-dimensional, simply parametrized environment where (ii) there is a linear closed form solution for optimal behavior from any state, and (iii) the difficulty of the game can be tuned by changing environment parameters in an interpretable way. We use these Erdos-Selfridge-Spencer games not only to compare different algorithms, but test for generalization, make comparisons to supervised learning, analyse multiagent play, and even develop a self play algorithm. Code can be found at: https://github.com/rubai5/ESS_Game
Learning Overcomplete HMMs
Venue: arXiv cs.LG 2018
Year: 2018

We study the problem of learning overcomplete HMMs---those that have many hidden states but a small output alphabet. Despite having significant practical importance, such HMMs are poorly understood with no known positive or negative results for efficient learning. In this paper, we present several new results---both positive and negative---which help define the boundaries between the tractable and intractable settings. Specifically, we show positive results for a large subclass of HMMs whose transition matrices are sparse, well-conditioned, and have small probability mass on short cycles. On the other hand, we show that learning is impossible given only a polynomial number of samples for HMMs with a small output alphabet and whose transition matrices are random regular graphs with large degree. We also discuss these results in the context of learning HMMs which can capture long-term dependencies.
Achievable Rate Analysis of Relay Assisted Cooperative NOMA over Rician Fading Channels
Venue: arXiv cs.IT 2018
Year: 2018

Non-orthogonal multiple access (NOMA) is a key to multiple access techniques for the next generation 5G wireless communication networks. In this paper, to improve the performance gain of NOMA system, a cooperative fixed decode-and-forward (DF) relay system model based on NOMA (CRS-NOMA) is studied over Rician fading channels, considering the achievable rate of signals as the performance metric. In this technique, by exploiting the concept of NOMA, unlike the conventional method of cooperative relaying, the second time slot is also utilized for the realization of information sent from the transmitter end. Moreover, as the data symbols are transmitted by nodes with full power, the compulsion of complex power allocation coefficients is precluded. In conventional cooperative relaying systems, the receiver is only able to receive a single bit of information, while the receiver can reliably bring in two data symbols in two-time slots. In this regard, this scheme is able to acquire higher achievable rate performance than existing cooperative relaying schemes for larger channel powers over most of the transmit SNR regime. Furthermore, a mathematical expression is also derived for the total achievable rate of CRS-NOMA. The results are verified through Monte-Carlo simulations which validate accuracy and consistency of the derived analytical results.
Fidelity-Weighted Learning
Venue: arXiv cs.LG 2018
Year: 2018

Training deep neural networks requires many training samples, but in practice training labels are expensive to obtain and may be of varying quality, as some may be from trusted expert labelers while others might be from heuristics or other sources of weak supervision such as crowd-sourcing. This creates a fundamental quality versus-quantity trade-off in the learning process. Do we learn from the small amount of high-quality data or the potentially large amount of weakly-labeled data? We argue that if the learner could somehow know and take the label-quality into account when learning the data representation, we could get the best of both worlds. To this end, we propose "fidelity-weighted learning" (FWL), a semi-supervised student-teacher approach for training deep neural networks using weakly-labeled data. FWL modulates the parameter updates to a student network (trained on the task we care about) on a per-sample basis according to the posterior confidence of its label-quality estimated by a teacher (who has access to the high-quality labels). Both student and teacher are learned from the data. We evaluate FWL on two tasks in information retrieval and natural language processing where we outperform state-of-the-art alternative semi-supervised methods, indicating that our approach makes better use of strong and weak labels, and leads to better task-dependent data representations.
Active Learning of Points-To Specifications
Venue: arXiv cs.PL 2018
Year: 2018

When analyzing programs, large libraries pose significant challenges to static points-to analysis. A popular solution is to have a human analyst provide points-to specifications that summarize relevant behaviors of library code, which can substantially improve precision and handle missing code such as native code. We propose ATLAS, a tool that automatically infers points-to specifications. ATLAS synthesizes unit tests that exercise the library code, and then infers points-to specifications based on observations from these executions. ATLAS automatically infers specifications for the Java standard library, and produces better results for a client static information flow analysis on a benchmark of 46 Android apps compared to using existing handwritten specifications.
p-FP: Extraction, Classification, and Prediction of Website Fingerprints with Deep Learning
Venue: arXiv cs.CR 2018
Year: 2018

Recent advances in learning Deep Neural Network (DNN) architectures have received a great deal of attention due to their ability to outperform state-of-the-art classifiers across a wide range of applications, with little or no feature engineering. In this paper, we broadly study the applicability of deep learning to website fingerprinting. We show that unsupervised DNNs can be used to extract low-dimensional feature vectors that improve the performance of state-of-the-art website fingerprinting attacks. When used as classifiers, we show that they can match or exceed performance of existing attacks across a range of application scenarios, including fingerprinting Tor website traces, fingerprinting search engine queries over Tor, defeating fingerprinting defenses, and fingerprinting TLS-encrypted websites. Finally, we show that DNNs can be used to predict the fingerprintability of a website based on its contents, achieving 99% accuracy on a data set of 4500 website downloads.
A Fully Convolutional Tri-branch Network (FCTN) for Domain Adaptation
Venue: arXiv cs.CV 2018
Year: 2018

A domain adaptation method for urban scene segmentation is proposed in this work. We develop a fully convolutional tri-branch network, where two branches assign pseudo labels to images in the unlabeled target domain while the third branch is trained with supervision based on images in the pseudo-labeled target domain. The re-labeling and re-training processes alternate. With this design, the tri-branch network learns target-specific discriminative representations progressively and, as a result, the cross-domain capability of the segmenter improves. We evaluate the proposed network on large-scale domain adaptation experiments using both synthetic (GTA) and real (Cityscapes) images. It is shown that our solution achieves the state-of-the-art performance and it outperforms previous methods by a significant margin.
Scheduling with regular performance measures and optional job rejection on a single machine
Venue: arXiv cs.DM 2018
Year: 2018

We address single machine problems with optional jobs - rejection, studied recently in Zhang et al. [21] and Cao et al. [2]. In these papers, the authors focus on minimizing regular performance measures, i.e., functions that are non-decreasing in the jobs completion time, subject to the constraint that the total rejection cost cannot exceed a predefined upper bound. They also prove that the considered problems are ordinary NP-hard and provide pseudo-polynomial-time Dynamic Programming (DP) solutions. In this paper, we focus on three of these problems: makespan with release-dates; total completion times; and total weighted completion, and present enhanced DP solutions demonstrating both theoretical and practical improvements. Moreover, we provide extensive numerical studies verifying their efficiency.
Time-Windowed Contiguous Hotspot Queries
Venue: arXiv cs.CG 2018
Year: 2018

A hotspot of a moving entity is a region in which it spends a significant amount of time. Given the location of a moving object through a certain time interval, i.e. its trajectory, our goal is to find its hotspots. We consider axis-parallel square hotspots of fixed side length, which contain the longest contiguous portion of the trajectory. Gudmundsson, van Kreveld, and Staals (2013) presented an algorithm to find a hotspot of a trajectory in $O(n \log n)$, in which $n$ is the number of vertices of the trajectory. We present an algorithm for answering \emph{time-windowed} hotspot queries, to find a hotspot in any given time interval. The algorithm has an approximation factor of $1/2$ and answers each query with the time complexity $O(\log^2 n)$. The time complexity of the preprocessing step of the algorithm is $O(n)$. When the query contains the whole trajectory, it implies an $O(n)$ algorithm for finding approximate contiguous hotspots.
Dynamic Analysis of Executables to Detect and Characterize Malware
Venue: arXiv cs.CR 2018
Year: 2018

It is needed to ensure the integrity of systems that process sensitive information and control many aspects of everyday life. We examine the use of machine learning algorithms to detect malware using the system calls generated by executables-alleviating attempts at obfuscation as the behavior is monitored rather than the bytes of an executable. We examine several machine learning techniques for detecting malware including random forests, deep learning techniques, and liquid state machines. The experiments examine the effects of concept drift on each algorithm to understand how well the algorithms generalize to novel malware samples by testing them on data that was collected after the training data. The results suggest that each of the examined machine learning algorithms is a viable solution to detect malware-achieving between 90% and 95% class-averaged accuracy (CAA). In real-world scenarios, the performance evaluation on an operational network may not match the performance achieved in training. Namely, the CAA may be about the same, but the values for precision and recall over the malware can change significantly. We structure experiments to highlight these caveats and offer insights into expected performance in operational environments. In addition, we use the induced models to gain a better understanding about what differentiates the malware samples from the goodware, which can further be used as a forensics tool to understand what the malware (or goodware) was doing to provide directions for investigation and remediation.