OpenRaiser/Intern-Atlas huggingface dataset:
Exceptionally Monadic Error Handling
Venue: arXiv cs.PL 2019
Year: 2019

We notice that the type of catch :: c a -> (e -> c a) -> c a operator is a special case of monadic bind operator (>>=) :: m a -> (a -> m b) -> m b, the semantics (surprisingly) matches, and this observation has many interesting consequences. For instance, the reader is probably aware that the monadic essence of the (>>=) operator of the error monad $λA.E \lor A$ is to behave like identity monad for "normal" values and to stop on "errors". The unappreciated fact is that handling of said "errors" with a catch operator of the "flipped" "conjoined" error monad $λE.E \lor A$ is, too, a monadic computation that treats still unhandled "errors" as "normal" values and stops when an "error" is finally handled. We show that for an appropriately indexed type of computations such a "conjoined" structure naturally follows from the conventional operational semantics of throw and catch operators. Consequently, we show that this structure uniformly generalizes all conventional monadic error handling mechanisms we are aware of. We also demonstrate several more interesting instances of this structure of which at least bi-indexed monadic parser combinators and conventional exceptions implemented via continuations have immediate practical applications. Finally, we notice that these observations provide surprising perspectives on error handling in general and point to a largely unexplored trail in programming language design space.
Effective Feature Representation for Clinical Text Concept Extraction
Venue: arXiv cs.CL 2019
Year: 2019

Crucial information about the practice of healthcare is recorded only in free-form text, which creates an enormous opportunity for high-impact NLP. However, annotated healthcare datasets tend to be small and expensive to obtain, which raises the question of how to make maximally efficient uses of the available data. To this end, we develop an LSTM-CRF model for combining unsupervised word representations and hand-built feature representations derived from publicly available healthcare ontologies. We show that this combined model yields superior performance on five datasets of diverse kinds of healthcare text (clinical, social, scientific, commercial). Each involves the labeling of complex, multi-word spans that pick out different healthcare concepts. We also introduce a new labeled dataset for identifying the treatment relations between drugs and diseases.
Massive MIMO Forward Link Analysis for Cellular Networks
Venue: arXiv cs.IT 2019
Year: 2019

This paper presents analytical expressions for the signal-to-interference ratio (SIR) and the spectral efficiency in macrocellular networks with massive MIMO conjugate beamforming, both with a uniform and a channel-dependent power allocation. These expressions, which apply to very general network geometries, are asymptotic in the strength of the shadowing. Through Monte-Carlo simulation, we verify their accuracy for relevant network topologies and shadowing strengths. Also, since the analysis does not include pilot contamination, we further gauge through Monte-Carlo simulation the deviation that this phenomenon causes with respect to our results, and hence the scope of the analysis.
Connections between physics, mathematics and deep learning
Venue: arXiv cs.LG 2019
Year: 2019

Starting from the Fermat's principle of least action, which governs classical and quantum mechanics and from the theory of exterior differential forms, which governs the geometry of curved manifolds, we show how to derive the equations governing neural networks in an intrinsic, coordinate invariant way, where the loss function plays the role of the Hamiltonian. To be covariant, these equations imply a layer metric which is instrumental in pretraining and explains the role of conjugation when using complex numbers. The differential formalism also clarifies the relation of the gradient descent optimizer with Aristotelian and Newtonian mechanics and why large learning steps break the logic of the linearization procedure. We hope that this formal presentation of the differential geometry of neural networks will encourage some physicists to dive into deep learning, and reciprocally, that the specialists of deep learning will better appreciate the close interconnection of their subject with the foundations of classical and quantum field theory.
Resilient Consensus Through Event-based Communication
Venue: arXiv cs.SY 2019
Year: 2019

We consider resilient versions of discrete-time multi-agent consensus in the presence of faulty or even malicious agents in the network. In particular, we develop event-triggered update rules which can mitigate the influence of the malicious agents and at the same time reduce the necessary communication. Each regular agent updates its state based on a given rule using its neighbors' information. Only when the triggering condition is satisfied, the regular agents send their current states to their neighbors. Otherwise, the neighbors will continue to use the state received the last time. Assuming that a bound on the number of malicious nodes is known, we propose two update rules with event-triggered communication. They follow the so-called mean subsequence reduced (MSR) type algorithms and ignore values received from potentially malicious neighbors. We provide full characterizations for the necessary connectivity in the network for the algorithms to perform correctly, which are stated in terms of the notion of graph robustness. A numerical example is provided to demonstrate the effectiveness of the proposed approach.
Two-Layered Superposition of Broadcast/Multicast and Unicast Signals in Multiuser OFDMA Systems
Venue: arXiv cs.IT 2019
Year: 2019

We study optimal delivery strategies of one common and $K$ independent messages from a source to multiple users in wireless environments. In particular, two-layered superposition of broadcast/multicast and unicast signals is considered in a downlink multiuser OFDMA system. In the literature and industry, the two-layer superposition is often considered as a pragmatic approach to make a compromise between the simple but suboptimal orthogonal multiplexing (OM) and the optimal but complex fully-layered non-orthogonal multiplexing. In this work, we show that only two-layers are necessary to achieve the maximum sum-rate when the common message has higher priority than the $K$ individual unicast messages, and OM cannot be sum-rate optimal in general. We develop an algorithm that finds the optimal power allocation over the two-layers and across the OFDMA radio resources in static channels and a class of fading channels. Two main use-cases are considered: i) Multicast and unicast multiplexing when $K$ users with uplink capabilities request both common and independent messages, and ii) broadcast and unicast multiplexing when the common message targets receive-only devices and $K$ users with uplink capabilities additionally request independent messages. Finally, we develop a transceiver design for broadcast/multicast and unicast superposition transmission based on LTE-A-Pro physical layer and show with numerical evaluations in mobile environments with multipath propagation that the capacity improvements can be translated into significant practical performance gains compared to the orthogonal schemes in the 3GPP specifications. We also analyze the impact of real channel estimation and show that significant gains in terms of spectral efficiency or coverage area are still available even with estimation errors and imperfect interference cancellation for the two-layered superposition system.
Optimal Resource Allocation in IEEE 802.11ax Uplink OFDMA with Scheduled Access
Venue: arXiv cs.NI 2019
Year: 2019

We consider the scheduling and resource allocation problem in AP-initiated uplink OFDMA transmissions of IEEE 802.11ax networks. The uplink OFDMA resource allocation problem is known to be non-convex and difficult to solve in general. However, due to the special subcarrier allocation model of IEEE 802.11ax, the utility maximization problem involving the instantaneous rates of stations can be formulated as an assignment problem, and hence can be solved using the Hungarian method. In this paper, we address the more general problem of stochastic network utility maximization. Specifically, we maximize the utility of long-term average rates of stations subject to average rate and power constraints using Lyapunov optimization. The resulting resource allocation policies perform arbitrarily close to optimal and have polynomial time complexity. An important advantage of the proposed framework is that it can be used along with the target wake time mechanism of IEEE 802.11ax to provide guarantees on the average power consumption and/or achievable rates of stations whenever possible. Two key applications of such a design approach are power-constrained IoT networks and battery-powered sensor networks. We complement the theoretical study with computer simulations that evaluate our approach against other existing methods.
Real-time Magnetometer Disturbance Estimation via Online Nonlinear Programming
Venue: arXiv cs.SY 2019
Year: 2019

Magnetometer is a significant sensor for integrated navigation. However, it suffers from many kinds of unknown dynamic magnetic disturbances. We study the problem of online estimating such disturbances via a nonlinear optimization aided by intermediate quaternion estimation from inertial fusion. The proposed optimization is constrained by geographical distribution of magnetic field forming a constrained nonlinear programming. The uniqueness of the solution has been verified mathematically and we design an interior-point-based solver for efficient computation on embedded chips. It is claimed that the designed scheme mainly outperforms in dealing with the challenging bias estimation problem under static motion as previous representatives can hardly achieve. Experimental results demonstrate the effectiveness of the proposed scheme on high accuracy, fast response and low computational load.
Unsupervised Hyperalignment for Multilingual Word Embeddings
Venue: arXiv cs.CL 2019
Year: 2019

We consider the problem of aligning continuous word representations, learned in multiple languages, to a common space. It was recently shown that, in the case of two languages, it is possible to learn such a mapping without supervision. This paper extends this line of work to the problem of aligning multiple languages to a common space. A solution is to independently map all languages to a pivot language. Unfortunately, this degrades the quality of indirect word translation. We thus propose a novel formulation that ensures composable mappings, leading to better alignments. We evaluate our method by jointly aligning word vectors in eleven languages, showing consistent improvement with indirect mappings while maintaining competitive performance on direct word translation.
Compressed Multiple Pattern Matching
Venue: arXiv cs.DS 2019
Year: 2019

Given $d$ strings over the alphabet $\{0,1,\ldots,σ{-}1\}$, the classical Aho--Corasick data structure allows us to find all $occ$ occurrences of the strings in any text $T$ in $O(|T| + occ)$ time using $O(m\log m)$ bits of space, where $m$ is the number of edges in the trie containing the strings. Fix any constant $\varepsilon \in (0, 2)$. We describe a compressed solution for the problem that, provided $σ\le m^δ$ for a constant $δ< 1$, works in $O(|T| \frac{1}{\varepsilon} \log\frac{1}{\varepsilon} + occ)$ time, which is $O(|T| + occ)$ since $\varepsilon$ is constant, and occupies $mH_k + 1.443 m + \varepsilon m + O(d\log\frac{m}{d})$ bits of space, for all $0 \le k \le \max\{0,α\log_σm - 2\}$ simultaneously, where $α\in (0,1)$ is an arbitrary constant and $H_k$ is the $k$th-order empirical entropy of the trie. Hence, we reduce the $3.443m$ term in the space bounds of previously best succinct solutions to $(1.443 + \varepsilon)m$, thus solving an open problem posed by Belazzougui. Further, we notice that $L = \log\binom{σ(m+1)}{m} - O(\log(σm))$ is a worst-case space lower bound for any solution of the problem and, for $d = o(m)$ and constant $\varepsilon$, our approach allows to achieve $L + \varepsilon m$ bits of space, which gives an evidence that, for $d = o(m)$, the space of our data structure is theoretically optimal up to the $\varepsilon m$ additive term and it is hardly possible to eliminate the term $1.443m$. In addition, we refine the space analysis of previous works by proposing a more appropriate definition for $H_k$. We also simplify the construction for practice adapting the fixed block compression boosting technique, then implement our data structure, and conduct a number of experiments showing that it is comparable to the state of the art in terms of time and is superior in space.
A Novel Predictive-Coding-Inspired Variational RNN Model for Online Prediction and Recognition
Venue: arXiv cs.LG 2019
Year: 2019

This study introduces PV-RNN, a novel variational RNN inspired by the predictive-coding ideas. The model learns to extract the probabilistic structures hidden in fluctuating temporal patterns by dynamically changing the stochasticity of its latent states. Its architecture attempts to address two major concerns of variational Bayes RNNs: how can latent variables learn meaningful representations and how can the inference model transfer future observations to the latent variables. PV-RNN does both by introducing adaptive vectors mirroring the training data, whose values can then be adapted differently during evaluation. Moreover, prediction errors during backpropagation, rather than external inputs during the forward computation, are used to convey information to the network about the external data. For testing, we introduce error regression for predicting unseen sequences as inspired by predictive coding that leverages those mechanisms. The model introduces a weighting parameter, the meta-prior, to balance the optimization pressure placed on two terms of a lower bound on the marginal likelihood of the sequential data. We test the model on two datasets with probabilistic structures and show that with high values of the meta-prior the network develops deterministic chaos through which the data's randomness is imitated. For low values, the model behaves as a random process. The network performs best on intermediate values, and is able to capture the latent probabilistic structure with good generalization. Analyzing the meta-prior's impact on the network allows to precisely study the theoretical value and practical benefits of incorporating stochastic dynamics in our model. We demonstrate better prediction performance on a robot imitation task with our model using error regression compared to a standard variational Bayes model lacking such a procedure.
Underwater Single Image Color Restoration Using Haze-Lines and a New Quantitative Dataset
Venue: arXiv cs.CV 2019
Year: 2019

Underwater images suffer from color distortion and low contrast, because light is attenuated while it propagates through water. Attenuation under water varies with wavelength, unlike terrestrial images where attenuation is assumed to be spectrally uniform. The attenuation depends both on the water body and the 3D structure of the scene, making color restoration difficult. Unlike existing single underwater image enhancement techniques, our method takes into account multiple spectral profiles of different water types. By estimating just two additional global parameters: the attenuation ratios of the blue-red and blue-green color channels, the problem is reduced to single image dehazing, where all color channels have the same attenuation coefficients. Since the water type is unknown, we evaluate different parameters out of an existing library of water types. Each type leads to a different restored image and the best result is automatically chosen based on color distribution. We collected a dataset of images taken in different locations with varying water properties, showing color charts in the scenes. Moreover, to obtain ground truth, the 3D structure of the scene was calculated based on stereo imaging. This dataset enables a quantitative evaluation of restoration algorithms on natural images and shows the advantage of our method.
Supervised learning of an opto-magnetic neural network with ultrashort laser pulses
Venue: arXiv cs.ET 2019
Year: 2019

The explosive growth of data and its related energy consumption is pushing the need to develop energy-efficient brain-inspired schemes and materials for data processing and storage. Here, we demonstrate experimentally that Co/Pt films can be used as artificial synapses by manipulating their magnetization state using circularly-polarized ultrashort optical pulses at room temperature. We also show an efficient implementation of supervised perceptron learning on an opto-magnetic neural network, built from such magnetic synapses. Importantly, we demonstrate that the optimization of synaptic weights can be achieved using a global feedback mechanism, such that the learning does not rely on external storage or additional optimization schemes. These results suggest there is high potential for realizing artificial neural networks using optically-controlled magnetization in technologically relevant materials, that can learn not only fast but also energy-efficient.
A Deep One-Shot Network for Query-based Logo Retrieval
Venue: arXiv cs.CV 2019
Year: 2019

Logo detection in real-world scene images is an important problem with applications in advertisement and marketing. Existing general-purpose object detection methods require large training data with annotations for every logo class. These methods do not satisfy the incremental demand of logo classes necessary for practical deployment since it is practically impossible to have such annotated data for new unseen logo. In this work, we develop an easy-to-implement query-based logo detection and localization system by employing a one-shot learning technique. Given an image of a query logo, our model searches for it within a given target image and predicts the possible location of the logo by estimating a binary segmentation mask. The proposed model consists of a conditional branch and a segmentation branch. The former gives a conditional latent representation of the given query logo which is combined with feature maps of the segmentation branch at multiple scales in order to find the matching position of the query logo in a target image, should it be present. Feature matching between the latent query representation and multi-scale feature maps of segmentation branch using simple concatenation operation followed by 1x1 convolution layer makes our model scale-invariant. Despite its simplicity, our query-based logo retrieval framework achieved superior performance in FlickrLogos-32 and TopLogos-10 dataset over different existing baselines.
Design of Anonymous Endorsement System in Hyperledger Fabric
Venue: arXiv cs.CR 2019
Year: 2019

Permissioned Blockchain has become quite popular with enterprises forming consortium since it prioritizes trust over privacy. One of the popular platforms for distributed ledger solution, Hyperledger Fabric, requires a transaction to be endorsed or approved by a group of special members known as endorsers before undergoing validation. To endorse a transaction, an endorser mentions its identity along with the signature so that it can be verified later. However, for certain transactions, difference in opinion may exist among endorsers. Disclosing the identity of an endorser may lead to conflict within the consortium. In such cases, an endorsement policy which not only allows an endorser to support a transaction discreetly, but at the same time takes into account the decision of the majority is preferred. Thus we propose an Anonymous Endorsement System which uses a threshold endorsement policy in order to address the issue. All these factors motivated us to design a new ring signature scheme, called Fabric' Constant-Sized Linkable Ring Signature (FCsLRS) with Transaction-Oriented linkability for hiding identity of the endorsers. We have implemented the signature scheme in Golang and analyzed its security and performance by varying the RSA (Rivest-Shamir-Adleman) modulus size. Feasibility of implementation is supported by experimental analysis. Signature and tag generation time is quite fast and remains constant irrespective of change in message length or endorsement set size for a given RSA modulus value, assuming all the endorsers generates their signature in parallel. Lastly, we also discuss the integration of the scheme on v1.2 Hyperledger Fabric.
Domain Reduction for Monotonicity Testing: A $o(d)$ Tester for Boolean Functions in $d$-Dimensions
Venue: arXiv cs.DM 2019
Year: 2019

We describe a $\tilde{O}(d^{5/6})$-query monotonicity tester for Boolean functions $f:[n]^d \to \{0,1\}$ on the $n$-hypergrid. This is the first $o(d)$ monotonicity tester with query complexity independent of $n$. Motivated by this independence of $n$, we initiate the study of monotonicity testing of measurable Boolean functions $f:\mathbb{R}^d \to \{0,1\}$ over the continuous domain, where the distance is measured with respect to a product distribution over $\mathbb{R}^d$. We give a $\tilde{O}(d^{5/6})$-query monotonicity tester for such functions. Our main technical result is a domain reduction theorem for monotonicity. For any function $f:[n]^d \to \{0,1\}$, let $ε_f$ be its distance to monotonicity. Consider the restriction $\hat{f}$ of the function on a random $[k]^d$ sub-hypergrid of the original domain. We show that for $k = \text{poly}(d/ε)$, the expected distance of the restriction is $\mathbb{E}[ε_{\hat{f}}] = Ω(ε_f)$. Previously, such a result was only known for $d=1$ (Berman-Raskhodnikova-Yaroslavtsev, STOC 2014). Our result for testing Boolean functions over $[n]^d$ then follows by applying the $d^{5/6}\cdot \text{poly}(1/ε,\log n, \log d)$-query hypergrid tester of Black-Chakrabarty-Seshadhri (SODA 2018). To obtain the result for testing Boolean functions over $\mathbb{R}^d$, we use standard measure theoretic tools to reduce monotonicity testing of a measurable function $f$ to monotonicity testing of a discretized version of $f$ over a hypergrid domain $[N]^d$ for large, but finite, $N$ (that may depend on $f$). The independence of $N$ in the hypergrid tester is crucial to getting the final tester over $\mathbb{R}^d$.