OpenRaiser/Intern-Atlas huggingface dataset:
DenseAlert: Incremental Dense-Subtensor Detection in Tensor Streams
Venue: arXiv cs.SI 2017
Year: 2017

Consider a stream of retweet events - how can we spot fraudulent lock-step behavior in such multi-aspect data (i.e., tensors) evolving over time? Can we detect it in real time, with an accuracy guarantee? Past studies have shown that dense subtensors tend to indicate anomalous or even fraudulent behavior in many tensor data, including social media, Wikipedia, and TCP dumps. Thus, several algorithms have been proposed for detecting dense subtensors rapidly and accurately. However, existing algorithms assume that tensors are static, while many real-world tensors, including those mentioned above, evolve over time. We propose DenseStream, an incremental algorithm that maintains and updates a dense subtensor in a tensor stream (i.e., a sequence of changes in a tensor), and DenseAlert, an incremental algorithm spotting the sudden appearances of dense subtensors. Our algorithms are: (1) Fast and 'any time': updates by our algorithms are up to a million times faster than the fastest batch algorithms, (2) Provably accurate: our algorithms guarantee a lower bound on the density of the subtensor they maintain, and (3) Effective: our DenseAlert successfully spots anomalies in real-world tensors, especially those overlooked by existing algorithms.
Local List Recovery of High-rate Tensor Codes and Applications
Venue: arXiv cs.IT 2017
Year: 2017

In this work, we give the first construction of high-rate locally list-recoverable codes. List-recovery has been an extremely useful building block in coding theory, and our motivation is to use these codes as such a building block. In particular, our construction gives the first capacity-achieving locally list-decodable codes (over constant-sized alphabet); the first capacity achieving globally list-decodable codes with nearly linear time list decoding algorithm (once more, over constant-sized alphabet); and a randomized construction of binary codes on the Gilbert-Varshamov bound that can be uniquely decoded in near-linear-time, with higher rate than was previously known. Our techniques are actually quite simple, and are inspired by an approach of Gopalan, Guruswami, and Raghavendra (Siam Journal on Computing, 2011) for list-decoding tensor codes. We show that tensor powers of (globally) list-recoverable codes are "approximately" locally list-recoverable, and that the "approximately" modifier may be removed by pre-encoding the message with a suitable locally decodable code. Instantiating this with known constructions of high-rate globally list-recoverable codes and high-rate locally decodable codes finishes the construction.
Dialog Structure Through the Lens of Gender, Gender Environment, and Power
Venue: arXiv cs.CL 2017
Year: 2017

Understanding how the social context of an interaction affects our dialog behavior is of great interest to social scientists who study human behavior, as well as to computer scientists who build automatic methods to infer those social contexts. In this paper, we study the interaction of power, gender, and dialog behavior in organizational interactions. In order to perform this study, we first construct the Gender Identified Enron Corpus of emails, in which we semi-automatically assign the gender of around 23,000 individuals who authored around 97,000 email messages in the Enron corpus. This corpus, which is made freely available, is orders of magnitude larger than previously existing gender identified corpora in the email domain. Next, we use this corpus to perform a large-scale data-oriented study of the interplay of gender and manifestations of power. We argue that, in addition to one's own gender, the "gender environment" of an interaction, i.e., the gender makeup of one's interlocutors, also affects the way power is manifested in dialog. We focus especially on manifestations of power in the dialog structure --- both, in a shallow sense that disregards the textual content of messages (e.g., how often do the participants contribute, how often do they get replies etc.), as well as the structure that is expressed within the textual content (e.g., who issues requests and how are they made, whose requests get responses etc.). We find that both gender and gender environment affect the ways power is manifested in dialog, resulting in patterns that reveal the underlying factors. Finally, we show the utility of gender information in the problem of automatically predicting the direction of power between pairs of participants in email interactions.
On the covariance of X in AX = XB
Venue: arXiv cs.RO 2017
Year: 2017

Hand-eye calibration, which consists in identifying the rigid- body transformation between a camera mounted on the robot end-effector and the end-effector itself, is a fundamental problem in robot vision. Mathematically, this problem can be formulated as: solve for X in AX = XB. In this paper, we provide a rigorous derivation of the covariance of the solution X, when A and B are randomly perturbed matrices. This fine-grained information is critical for applications that require a high degree of perception precision. Our approach consists in applying covariance propagation methods in SE(3). Experiments involving synthetic and real calibration data confirm that our approach can predict the covariance of the hand-eye transformation with excellent precision.
Exploring the Syntactic Abilities of RNNs with Multi-task Learning
Venue: arXiv cs.CL 2017
Year: 2017

Recent work has explored the syntactic abilities of RNNs using the subject-verb agreement task, which diagnoses sensitivity to sentence structure. RNNs performed this task well in common cases, but faltered in complex sentences (Linzen et al., 2016). We test whether these errors are due to inherent limitations of the architecture or to the relatively indirect supervision provided by most agreement dependencies in a corpus. We trained a single RNN to perform both the agreement task and an additional task, either CCG supertagging or language modeling. Multi-task training led to significantly lower error rates, in particular on complex sentences, suggesting that RNNs have the ability to evolve more sophisticated syntactic representations than shown before. We also show that easily available agreement training data can improve performance on other syntactic tasks, in particular when only a limited amount of training data is available for those tasks. The multi-task paradigm can also be leveraged to inject grammatical knowledge into language models.
Automatic differentiation of hybrid models Illustrated by Diffedge Graphic Methodology. (Survey)
Venue: arXiv cs.SY 2017
Year: 2017

We investigate the automatic differentiation of hybrid models, viz. models that may contain delays, logical tests and discontinuities or loops. We consider differentiation with respect to parameters, initial conditions or the time. We emphasize the case of a small number of derivations and iterated differentiations are mostly treated with a foccus on high order iterations of the same derivation. The models we consider may involve arithmetic operations, elementary functions, logical tests but also more elaborate components such as delays, integrators, equations and differential equations solvers. This survey has no pretention to exhaustivity but tries to fil a gap in the litterature where each kind of of component may be documented, but seldom their common use. The general approach is illustrated by computer algebra experiments, stressing the interest of performing differentiation, whenever possible, on high level objects, before any translation in Fortran or C code. We include ordinary differential systems with discontinuity, with a special interest for those comming from discontinuous Lagrangians. We conclude with an overview of the graphic methodology developped in the Diffedge software for Simulink hybrid models. Not all possibilities are covered, but the methodology can be adapted. The result of automatic differentiation is a new block diagram and so it can be easily translated to produce real time embedded programs. We welcome any comments or suggestions of references that we may have missed.
Blind MultiChannel Identification and Equalization for Dereverberation and Noise Reduction based on Convolutive Transfer Function
Venue: arXiv cs.SD 2017
Year: 2017

This paper addresses the problems of blind channel identification and multichannel equalization for speech dereverberation and noise reduction. The time-domain cross-relation method is not suitable for blind room impulse response identification, due to the near-common zeros of the long impulse responses. We extend the cross-relation method to the short-time Fourier transform (STFT) domain, in which the time-domain impulse responses are approximately represented by the convolutive transfer functions (CTFs) with much less coefficients. The CTFs suffer from the common zeros caused by the oversampled STFT. We propose to identify CTFs based on the STFT with the oversampled signals and the critical sampled CTFs, which is a good compromise between the frequency aliasing of the signals and the common zeros problem of CTFs. In addition, a normalization of the CTFs is proposed to remove the gain ambiguity across sub-bands. In the STFT domain, the identified CTFs is used for multichannel equalization, in which the sparsity of speech signals is exploited. We propose to perform inverse filtering by minimizing the $\ell_1$-norm of the source signal with the relaxed $\ell_2$-norm fitting error between the micophone signals and the convolution of the estimated source signal and the CTFs used as a constraint. This method is advantageous in that the noise can be reduced by relaxing the $\ell_2$-norm to a tolerance corresponding to the noise power, and the tolerance can be automatically set. The experiments confirm the efficiency of the proposed method even under conditions with high reverberation levels and intense noise.
COPSS-lite: Lightweight ICN Based Pub/Sub for IoT Environments
Venue: arXiv cs.NI 2017
Year: 2017

Information Centric Networking is a new networking paradigm that treats content as first class entity. It provides content to users without regards to the current location of the content. The publish/subscribe systems have gained popularity in Internet. Pub/sub systems dismisses the need for users to request every content of their interest. Instead, the content is supplied to interested users (subscribers) as and when it is published. CCN/NDN are popular ICN proposals widely accepted in the ICN community however, they do not provide an efficient pub/sub mechanism. COPSS enhances CCN/NDN with an efficient pub/sub capability. Internet of Things (IoT) is a growing topic of interest in both Academia and Industry. The current designs for IoT relies on IP. However, the IoT devices are constrained in their available resources and IP is heavy for their operation.We observed that IoT's are information centric in nature and hence ICN is a more suitable candidate to support IoT environments. Although NDN and COPSS work well for the Internet, their current full fledged implementations cannot be used by the resource constrained IoT devices. CCN-lite is a light weight, inter-operable version of the CCNx protocol for supporting the IoT devices. However, CCN-lite like its ancestors lacks the support for an efficient pub/sub mechanism. In this paper, we developed COPSS-lite, an efficient and light weight implementation of pub/sub for IoT. COPSS-lite is developed to enhance CCN-lite and also support multi-hop connection by incorporating the famous RPL protocol for low power and lossy networks. We provide a preliminary evaluation to show proof of operability with real world sensor devices in IoT lab. Our results show that COPSS-lite is compact, operates on all platforms that support CCN-lite and we observe significant performance benefits with COPSS-lite in IoT environments.
Designing Deterministic Polynomial-Space Algorithms by Color-Coding Multivariate Polynomials
Venue: arXiv cs.DS 2017
Year: 2017

In recent years, several powerful techniques have been developed to design {\em randomized} polynomial-space parameterized algorithms. In this paper, we introduce an enhancement of color coding to design deterministic polynomial-space parameterized algorithms. Our approach aims at reducing the number of random choices by exploiting the special structure of a solution. Using our approach, we derive the following deterministic algorithms (see Introduction for problem definitions). 1. Polynomial-space $O^*(3.86^k)$-time (exponential-space $O^*(3.41^k)$-time) algorithm for {\sc $k$-Internal Out-Branching}, improving upon the previously fastest {\em exponential-space} $O^*(5.14^k)$-time algorithm for this problem. 2. Polynomial-space $O^*((2e)^{k+o(k)})$-time (exponential-space $O^*(4.32^k)$-time) algorithm for {\sc $k$-Colorful Out-Branching} on arc-colored digraphs and {\sc $k$-Colorful Perfect Matching} on planar edge-colored graphs. To obtain our polynomial space algorithms, we show that $(n,k,αk)$-splitters ($α\ge 1$) and in particular $(n,k)$-perfect hash families can be enumerated one by one with polynomial delay.
Applying Software Patterns to Address Interoperability in Blockchain-based Healthcare Apps
Venue: arXiv cs.CY 2017
Year: 2017

Since the inception of the Bitcoin technology, its underlying data structure--the blockchain--has garnered much attention due to properties such as decentralization, transparency, and immutability. These properties make blockchains suitable for apps that require disintermediation through trustless exchange, consistent and incorruptible transaction records, and operational models beyond cryptocurrency. In particular, blockchain and its smart contract capabilities have the potential to address healthcare interoperability issues, such as enabling effective interactions between users and medical applications, delivering patient data securely to a variety of organizations and devices, and improving the overall efficiency of medical practice workflow. Despite the interest in using blockchain for healthcare interoperability, however, little information is available on the concrete architectural styles and patterns for applying blockchain to healthcare apps. This paper provides an initial step in filling this gap by showing: (1) the features and implementation challenges in healthcare interoperability, (2) an end-to-end case study of a blockchain-based healthcare app we are developing, and (3) how applying foundational software patterns can help address common interoperability challenges faced by blockchain-based healthcare apps.
Strongly Normalizing Audited Computation
Venue: arXiv cs.LO 2017
Year: 2017

Auditing is an increasingly important operation for computer programming, for example in security (e.g. to enable history-based access control) and to enable reproducibility and accountability (e.g. provenance in scientific programming). Most proposed auditing techniques are ad hoc or treat auditing as a second-class, extralinguistic operation; logical or semantic foundations for auditing are not yet well-established. Justification Logic (JL) offers one such foundation; Bavera and Bonelli introduced a computational interpretation of JL called $λ^h$ that supports auditing. However, $λ^h$ is technically complex and strong normalization was only established for special cases. In addition, we show that the equational theory of $λ^h$ is inconsistent. We introduce a new calculus $λ^{hc}$ that is simpler than $λ^h$, consistent, and strongly normalizing. Our proof of strong normalization is formalized in Nominal Isabelle.
Transferring a Semantic Representation for Person Re-Identification and Search
Venue: arXiv cs.CV 2017
Year: 2017

Learning semantic attributes for person re-identification and description-based person search has gained increasing interest due to attributes' great potential as a pose and view-invariant representation. However, existing attribute-centric approaches have thus far underperformed state-of-the-art conventional approaches. This is due to their non-scalable need for extensive domain (camera) specific annotation. In this paper we present a new semantic attribute learning approach for person re-identification and search. Our model is trained on existing fashion photography datasets -- either weakly or strongly labelled. It can then be transferred and adapted to provide a powerful semantic description of surveillance person detections, without requiring any surveillance domain supervision. The resulting representation is useful for both unsupervised and supervised person re-identification, achieving state-of-the-art and near state-of-the-art performance respectively. Furthermore, as a semantic representation it allows description-based person search to be integrated within the same framework.
Portable Trust: biometric-based authentication and blockchain storage for self-sovereign identity systems
Venue: arXiv cs.CR 2017
Year: 2017

We devised a mobile biometric-based authentication system only relying on local processing. Our Android open source solution explores the capability of current smartphones to acquire, process and match fingerprints using only its built-in hardware. Our architecture is specifically designed to run completely locally and autonomously, not requiring any cloud service, server, or permissioned access to fingerprint reader hardware. It involves three main stages, starting with the fingerprint acquisition using the smartphone camera, followed by a processing pipeline to obtain minutiae features and a final step for matching against other locally stored fingerprints, based on Oriented FAST and Rotated BRIEF (ORB) descriptors. We obtained a mean matching accuracy of 55%, with the highest value of 67% for thumb fingers. Our ability to capture and process a finger fingerprint in mere seconds using a smartphone makes this work usable in a wide range of scenarios, for instance, offline remote regions. This work is specifically designed to be a key building block for a self-sovereign identity solution and integrate with our permissionless blockchain for identity and key attestation.
Semantic Entity Retrieval Toolkit
Venue: arXiv cs.CL 2017
Year: 2017

Unsupervised learning of low-dimensional, semantic representations of words and entities has recently gained attention. In this paper we describe the Semantic Entity Retrieval Toolkit (SERT) that provides implementations of our previously published entity representation models. The toolkit provides a unified interface to different representation learning algorithms, fine-grained parsing configuration and can be used transparently with GPUs. In addition, users can easily modify existing models or implement their own models in the framework. After model training, SERT can be used to rank entities according to a textual query and extract the learned entity/word representation for use in downstream algorithms, such as clustering or recommendation.
A Simple Soundness Proof for Dependent Object Types
Venue: arXiv cs.PL 2017
Year: 2017

Dependent Object Types (DOT) is intended to be a core calculus for modelling Scala. Its distinguishing feature is abstract type members, fields in objects that hold types rather than values. Proving soundness of DOT has been surprisingly challenging, and existing proofs are complicated, and reason about multiple concepts at the same time (e.g. types, values, evaluation). To serve as a core calculus for Scala, DOT should be easy to experiment with and extend, and therefore its soundness proof needs to be easy to modify. This paper presents a simple and modular proof strategy for reasoning in DOT. The strategy separates reasoning about types from other concerns. It is centred around a theorem that connects the full DOT type system to a restricted variant in which the challenges and paradoxes caused by abstract type members are eliminated. Almost all reasoning in the proof is done in the intuitive world of this restricted type system. Once we have the necessary results about types, we observe that the other aspects of DOT are mostly standard and can be incorporated into a soundness proof using familiar techniques known from other calculi. Our paper comes with a machine-verified version of the proof in Coq.
Attention-based Vocabulary Selection for NMT Decoding
Venue: arXiv cs.CL 2017
Year: 2017

Neural Machine Translation (NMT) models usually use large target vocabulary sizes to capture most of the words in the target language. The vocabulary size is a big factor when decoding new sentences as the final softmax layer normalizes over all possible target words. To address this problem, it is widely common to restrict the target vocabulary with candidate lists based on the source sentence. Usually, the candidate lists are a combination of external word-to-word aligner, phrase table entries or most frequent words. In this work, we propose a simple and yet novel approach to learn candidate lists directly from the attention layer during NMT training. The candidate lists are highly optimized for the current NMT model and do not need any external computation of the candidate pool. We show significant decoding speedup compared with using the entire vocabulary, without losing any translation quality for two language pairs.
Contrast Enhancement Estimation for Digital Image Forensics
Venue: arXiv cs.CV 2017
Year: 2017

Inconsistency in contrast enhancement can be used to expose image forgeries. In this work, we describe a new method to estimate contrast enhancement from a single image. Our method takes advantage of the nature of contrast enhancement as a mapping between pixel values, and the distinct characteristics it introduces to the image pixel histogram. Our method recovers the original pixel histogram and the contrast enhancement simultaneously from a single image with an iterative algorithm. Unlike previous methods, our method is robust in the presence of additive noise perturbations that are used to hide the traces of contrast enhancement. Furthermore, we also develop an e effective method to to detect image regions undergone contrast enhancement transformations that are different from the rest of the image, and use this method to detect composite images. We perform extensive experimental evaluations to demonstrate the efficacy and efficiency of our method method.
Generative Models for Learning from Crowds
Venue: arXiv cs.AI 2017
Year: 2017

In this paper, we propose generative probabilistic models for label aggregation. We use Gibbs sampling and a novel variational inference algorithm to perform the posterior inference. Empirical results show that our methods consistently outperform state-of-the-art methods.
Optimal input design for system identification using spectral decomposition
Venue: arXiv cs.SY 2017
Year: 2017

The aim of this paper is to design a band-limited optimal input with power constraints for identifying a linear multi-input multi-output system. It is assumed that the nominal system parameters are specified. The key idea is to use the spectral decomposition theorem and write the power spectrum as $ϕ_{u}(jω)=\frac{1}{2}H(jω)H^*(jω)$. The matrix $H(jω)$ is expressed in terms of a truncated basis for $\mathcal{L}^2\left(\left[-ω_{\mbox{cut-off}},ω_{\mbox{cut-off}}\right]\right)$. With this parameterization, the elements of the Fisher Information Matrix and the power constraints turn out to be homogeneous quadratics in the basis coefficients. The optimality criterion used are the well-known $\mathcal{D}-$optimality, $\mathcal{A}-$optimality, $\mathcal{T}-$optimality and $\mathcal{E}-$optimality. The resulting optimization problem is non-convex in general. A lower bound on the optimum is obtained through a bi-linear formulation of the problem, while an upper bound is obtained through a convex relaxation. These bounds can be computed efficiently as the associated problems are convex. The lower bound is used as a sub-optimal solution, the sub-optimality of which is determined by the difference in the bounds. Interestingly, the bounds match in many instances and thus, the global optimum is achieved. A discussion on the non-convexity of the optimization problem is also presented. Simulations are provided for corroboration.