OpenRaiser/Intern-Atlas huggingface dataset:
On the Secrecy Performance of NOMA Systems with both External and Internal Eavesdroppers
Venue: arXiv cs.IT 2019
Year: 2019

Sharing resource blocks in NOMA systems provides more opportunity to the internal users to overhear the messages of the other users. Therefore, some sort of secrecy against the internal users in addition to the external eavesdroppers must be provided. In this paper, we investigate the secrecy performance of a two-user NOMA system in existence of the external and internal passive eavesdroppers, where the far user acts as an internal eavesdropper and tries to overhear the message of the near user. Our system consists of a single antenna base station, two legitimate users and an external passive eavesdropper. We present the closed-forms for the ergodic secrecy rates of the users. Moreover, to derive the secrecy outage probability (SOP) of the system, we use Gaussian-Chebyshev quadrature method, which gives an approximation for the SOP. Numerical results show that this approximation is very close to the exact value of the SOP of the system. Finally, we eliminate the external eavesdropper and present the closed-forms for the ergodic rate of the far user, the ergodic secrecy rate of the near user and also the SOP of the system.
Best-First Width Search for Multi Agent Privacy-preserving Planning
Venue: arXiv cs.AI 2019
Year: 2019

In multi-agent planning, preserving the agents' privacy has become an increasingly popular research topic. For preserving the agents' privacy, agents jointly compute a plan that achieves mutual goals by keeping certain information private to the individual agents. Unfortunately, this can severely restrict the accuracy of the heuristic functions used while searching for solutions. It has been recently shown that, for centralized planning, the performance of goal oriented search can be improved by combining goal oriented search and width-based search. The combination of these techniques has been called best-first width search. In this paper, we investigate the usage of best-first width search in the context of (decentralised) multi-agent privacy-preserving planning, addressing the challenges related to the agents' privacy and performance. In particular, we show that best-first width search is a very effective approach over several benchmark domains, even when the search is driven by heuristics that roughly estimate the distance from goal states, computed without using the private information of other agents. An experimental study analyses the effectiveness of our techniques and compares them with the state-of-the-art.
E-LPIPS: Robust Perceptual Image Similarity via Random Transformation Ensembles
Venue: arXiv cs.CV 2019
Year: 2019

It has been recently shown that the hidden variables of convolutional neural networks make for an efficient perceptual similarity metric that accurately predicts human judgment on relative image similarity assessment. First, we show that such learned perceptual similarity metrics (LPIPS) are susceptible to adversarial attacks that dramatically contradict human visual similarity judgment. While this is not surprising in light of neural networks' well-known weakness to adversarial perturbations, we proceed to show that self-ensembling with an infinite family of random transformations of the input --- a technique known not to render classification networks robust --- is enough to turn the metric robust against attack, while retaining predictive power on human judgments. Finally, we study the geometry imposed by our our novel self-ensembled metric (E-LPIPS) on the space of natural images. We find evidence of "perceptual convexity" by showing that convex combinations of similar-looking images retain appearance, and that discrete geodesics yield meaningful frame interpolation and texture morphing, all without explicit correspondences.
Hierarchical Representation in Neural Language Models: Suppression and Recovery of Expectations
Venue: arXiv cs.CL 2019
Year: 2019

Deep learning sequence models have led to a marked increase in performance for a range of Natural Language Processing tasks, but it remains an open question whether they are able to induce proper hierarchical generalizations for representing natural language from linear input alone. Work using artificial languages as training input has shown that LSTMs are capable of inducing the stack-like data structures required to represent context-free and certain mildly context-sensitive languages---formal language classes which correspond in theory to the hierarchical structures of natural language. Here we present a suite of experiments probing whether neural language models trained on linguistic data induce these stack-like data structures and deploy them while incrementally predicting words. We study two natural language phenomena: center embedding sentences and syntactic island constraints on the filler--gap dependency. In order to properly predict words in these structures, a model must be able to temporarily suppress certain expectations and then recover those expectations later, essentially pushing and popping these expectations on a stack. Our results provide evidence that models can successfully suppress and recover expectations in many cases, but do not fully recover their previous grammatical state.
Fast Hierarchical Neural Network for Feature Learning on Point Cloud
Venue: arXiv cs.CV 2019
Year: 2019

The analyses relying on 3D point clouds are an utterly complex task, often involving million of points, but also requiring computationally efficient algorithms because of many real-time applications; e.g. autonomous vehicle. However, point clouds are intrinsically irregular and the points are sparsely distributed in a non-Euclidean space, which normally requires point-wise processing to achieve high performances. Although shared filter matrices and pooling layers in convolutional neural networks (CNNs) are capable of reducing the dimensionality of the problem and extracting high-level information simultaneously, grids and highly regular data format are required as input. In order to balance model performance and complexity, we introduce a novel neural network architecture exploiting local features from a manually subsampled point set. In our network, a recursive farthest point sampling method is firstly applied to efficiently cover the entire point set. Successively, we employ the k-nearest neighbours (knn) algorithm to gather local neighbourhood for each group of the subsampled points. Finally, a multiple layer perceptron (MLP) is applied on the subsampled points and edges that connect corresponding point and neighbours to extract local features. The architecture has been tested for both shape classification and segmentation using the ModelNet40 and ShapeNet part datasets, in order to show that the network achieves the best trade-off in terms of competitive performance when compared to other state-of-the-art algorithms.
A Multi-task Approach for Named Entity Recognition in Social Media Data
Venue: arXiv cs.CL 2019
Year: 2019

Named Entity Recognition for social media data is challenging because of its inherent noisiness. In addition to improper grammatical structures, it contains spelling inconsistencies and numerous informal abbreviations. We propose a novel multi-task approach by employing a more general secondary task of Named Entity (NE) segmentation together with the primary task of fine-grained NE categorization. The multi-task neural network architecture learns higher order feature representations from word and character sequences along with basic Part-of-Speech tags and gazetteer information. This neural network acts as a feature extractor to feed a Conditional Random Fields classifier. We were able to obtain the first position in the 3rd Workshop on Noisy User-generated Text (WNUT-2017) with a 41.86% entity F1-score and a 40.24% surface F1-score.
The Demand Query Model for Bipartite Matching
Venue: arXiv cs.CC 2019
Year: 2019

We introduce a `concrete complexity' model for studying algorithms for matching in bipartite graphs. The model is based on the "demand query" model used for combinatorial auctions. Most (but not all) known algorithms for bipartite matching seem to be translatable into this model including exact, approximate, sequential, parallel, and online ones. A perfect matching in a bipartite graph can be found in this model with O(n^{3/2}) demand queries (in a bipartite graph with n vertices on each side) and our main open problem is to either improve the upper bound or prove a lower bound. An improved upper bound could yield "normal" algorithms whose running time is better than the fastest ones known, while a lower bound would rule out a faster algorithm for bipartite matching from within a large class of algorithms. Our main result is a lower bound for finding an approximately maximum size matching in parallel: A deterministic algorithm that runs in n^{o(1)} rounds, where each round can make at most n^{1.99} demand queries cannot find a matching whose size is within n^{o(1)} factor of the maximum. This is in contrast to randomized algorithms that can find a matching whose size is $99\%$ of the maximum in O(\log n) rounds, each making n demand queries.
Building High-Quality Auction Fraud Dataset
Venue: arXiv cs.LG 2019
Year: 2019

Given the magnitude of online auction transactions, it is difficult to safeguard consumers from dishonest sellers, such as shill bidders. To date, the application of Machine Learning Techniques (MLTs) to auction fraud has been limited, unlike their applications for combatting other types of fraud. Shill Bidding (SB) is a severe auction fraud, which is driven by modern-day technologies and clever scammers. The difficulty of identifying the behavior of sophisticated fraudsters and the unavailability of training datasets hinder the research on SB detection. In this study, we developed a high-quality SB dataset. To do so, first, we crawled and preprocessed a large number of commercial auctions and bidders' history as well. We thoroughly preprocessed both datasets to make them usable for the computation of the SB metrics. Nevertheless, this operation requires a deep understanding of the behavior of auctions and bidders. Second, we introduced two new SB pattern s and implemented other existing SB patterns. Finally, we removed outliers to improve the quality of training SB data.
Automated Curriculum Learning for Turn-level Spoken Language Understanding with Weak Supervision
Venue: arXiv cs.CL 2019
Year: 2019

We propose a learning approach for turn-level spoken language understanding, which facilitates a user to speak one or more utterances compositionally in a turn for completing a task (e.g., voice ordering). A typical pipelined approach for these understanding tasks requires non-trivial annotation effort for developing its multiple components. Also, the pipeline is difficult to port to a new domain or scale up. To address these problems, we propose an end-to-end statistical model with weak supervision. We employ randomized beam search with memory augmentation (RBSMA) to solve complicated problems for which long promising trajectories are usually difficult to explore. Furthermore, considering the diversity of problem complexity, we explore automated curriculum learning (CL) for weak supervision to accelerate exploration and learning. We evaluate the proposed approach on real-world user logs of a commercial voice ordering system. Results demonstrate that when trained on a small number of end-to-end annotated sessions collected with low cost, our model performs comparably to the deployed pipelined system, saving the development labor over an order of magnitude. The RBSMA algorithm improves the test set accuracy by 7.8% relative compared to the standard beam search. Automated CL leads to better generalization and further improves the test set accuracy by 5% relative.
Boosting Students' Performance With The Aid Of Social Network Analysis
Venue: arXiv cs.SI 2019
Year: 2019

There are various teaching methods developed in order to attain successful delivery of a subject without prior knowledge of the interaction among the students in a class. Social network analysis can be used to identify individual, intermediate and group measures of interaction in a classroom. The idea is on identifying ways to boost the students performance by means of lecturers intervention based on their interaction. The case study was conducted involving third year batch that consisted of 76 female and 24 male students. A friendship network was drawn based on the information obtained at the end of semester 5 and it was investigated based on two metrics namely centrality measures and Girvan Newman algorithm. At the end of semester 5, grades were added as the attributes of the network. 12 clusters were found in this batch and a distinct pattern was identified between performing and poor achieving students. At the beginning of the 6th semester, the students were given the option to choose between 2 groups. Group 1 was unperturbed without any lecturers intervention whereas the performing students clusters in Group 1 were preserved but the students in poor performing clusters were distributed among performing clusters. The students were then asked to carry out assignments and quizzes in their respective groups. The final grades indicated that the performance of the students of Group 1 was much superior and there was clear evidence that those poor performing students in the 5th semester performed much better in semester 6. This shows that by understanding the students interaction and incorporating instructors minimal intervention, the performance of the students can be improved by creating a social contagion effect through group assignment clustering.
Learning Powerful Policies by Using Consistent Dynamics Model
Venue: arXiv cs.LG 2019
Year: 2019

Model-based Reinforcement Learning approaches have the promise of being sample efficient. Much of the progress in learning dynamics models in RL has been made by learning models via supervised learning. But traditional model-based approaches lead to `compounding errors' when the model is unrolled step by step. Essentially, the state transitions that the learner predicts (by unrolling the model for multiple steps) and the state transitions that the learner experiences (by acting in the environment) may not be consistent. There is enough evidence that humans build a model of the environment, not only by observing the environment but also by interacting with the environment. Interaction with the environment allows humans to carry out experiments: taking actions that help uncover true causal relationships which can be used for building better dynamics models. Analogously, we would expect such interactions to be helpful for a learning agent while learning to model the environment dynamics. In this paper, we build upon this intuition by using an auxiliary cost function to ensure consistency between what the agent observes (by acting in the real world) and what it imagines (by acting in the `learned' world). We consider several tasks - Mujoco based control tasks and Atari games - and show that the proposed approach helps to train powerful policies and better dynamics models.
Evaluation of Seed Set Selection Approaches and Active Learning Strategies in Predictive Coding
Venue: arXiv cs.IR 2019
Year: 2019

Active learning is a popular methodology in text classification - known in the legal domain as "predictive coding" or "Technology Assisted Review" or "TAR" - due to its potential to minimize the required review effort to build effective classifiers. In this study, we use extensive experimentation to examine the impact of popular seed set selection strategies in active learning, within a predictive coding exercise, and evaluate different active learning strategies against well-researched continuous active learning strategies for the purpose of determining efficient training methods for classifying large populations quickly and precisely. We study how random sampling, keyword models and clustering based seed set selection strategies combined together with top-ranked, uncertain, random, recall inspired, and hybrid active learning document selection strategies affect the performance of active learning for predictive coding. We use the percentage of documents requiring review to reach 75% recall as the "benchmark" metric to evaluate and compare our approaches. In most cases we find that seed set selection methods have a minor impact, though they do show significant impact in lower richness data sets or when choosing a top-ranked active learning selection strategy. Our results also show that active learning selection strategies implementing uncertainty, random, or 75% recall selection strategies has the potential to reach the optimum active learning round much earlier than the popular continuous active learning approach (top-ranked selection). The results of our research shed light on the impact of active learning seed set selection strategies and also the effectiveness of the selection strategies for the following learning rounds. Legal practitioners can use the results of this study to enhance the efficiency, precision, and simplicity of their predictive coding process.
On the Vector Space in Photoplethysmography Imaging
Venue: arXiv cs.CV 2019
Year: 2019

We study the vector space of visible wavelength intensities from face videos widely used as input features in Photoplethysmography Imaging (PPGI). Based upon theoretical principles of Group invariance in the Euclidean space we derive a change of the topology where the corresponding distance between successive measurements is defined as geodesic on a Riemannian manifold. This lower dimensional embedding of the sensor signal unifies the invariance properties with respect to translation of the features as discussed by several former approaches. The resulting operator acts implicit on the feature space without requiring any kind of prior knowledge and does not need parameter tuning. The resulting feature's time varying quasi-periodic shaping naturally occurs in form of the canonical state space representation according to the known Diffusion process of blood volume changes. The computational complexity is low and the implementation becomes fairly simple. During experiments the operator achieved robust and competitive estimation performance of heart rate from face videos on two public databases.
Bag of Color Features For Color Constancy
Venue: arXiv cs.CV 2019
Year: 2019

In this paper, we propose a novel color constancy approach, called Bag of Color Features (BoCF), building upon Bag-of-Features pooling. The proposed method substantially reduces the number of parameters needed for illumination estimation. At the same time, the proposed method is consistent with the color constancy assumption stating that global spatial information is not relevant for illumination estimation and local information ( edges, etc.) is sufficient. Furthermore, BoCF is consistent with color constancy statistical approaches and can be interpreted as a learning-based generalization of many statistical approaches. To further improve the illumination estimation accuracy, we propose a novel attention mechanism for the BoCF model with two variants based on self-attention. BoCF approach and its variants achieve competitive, compared to the state of the art, results while requiring much fewer parameters on three benchmark datasets: ColorChecker RECommended, INTEL-TUT version 2, and NUS8.
Reinforcement Learning of Minimalist Numeral Grammars
Venue: arXiv cs.CL 2019
Year: 2019

Speech-controlled user interfaces facilitate the operation of devices and household functions to laymen. State-of-the-art language technology scans the acoustically analyzed speech signal for relevant keywords that are subsequently inserted into semantic slots to interpret the user's intent. In order to develop proper cognitive information and communication technologies, simple slot-filling should be replaced by utterance meaning transducers (UMT) that are based on semantic parsers and a \emph{mental lexicon}, comprising syntactic, phonetic and semantic features of the language under consideration. This lexicon must be acquired by a cognitive agent during interaction with its users. We outline a reinforcement learning algorithm for the acquisition of the syntactic morphology and arithmetic semantics of English numerals, based on minimalist grammar (MG), a recent computational implementation of generative linguistics. Number words are presented to the agent by a teacher in form of utterance meaning pairs (UMP) where the meanings are encoded as arithmetic terms from a suitable term algebra. Since MG encodes universal linguistic competence through inference rules, thereby separating innate linguistic knowledge from the contingently acquired lexicon, our approach unifies generative grammar and reinforcement learning, hence potentially resolving the still pending Chomsky-Skinner controversy.
Almost Optimal Semi-streaming Maximization for k-Extendible Systems
Venue: arXiv cs.DS 2019
Year: 2019

In this paper we consider the problem of finding a maximum weight set subject to a $k$-extendible constraint in the data stream model. The only non-trivial algorithm known for this problem to date---to the best of our knowledge---is a semi-streaming $k^2(1 + \varepsilon)$-approximation algorithm (Crouch and Stubbs, 2014), but semi-streaming $O(k)$-approximation algorithms are known for many restricted cases of this general problem. In this paper, we close most of this gap by presenting a semi-streaming $O(k \log k)$-approximation algorithm for the general problem, which is almost the best possible even in the offline setting (Feldman et al., 2017).
Competing (Semi)-Selfish Miners in Bitcoin
Venue: arXiv cs.GT 2019
Year: 2019

The Bitcoin protocol prescribes certain behavior by the miners who are responsible for maintaining and extending the underlying blockchain; in particular, miners who successfully solve a puzzle, and hence can extend the chain by a block, are supposed to release that block immediately. Eyal and Sirer showed, however, that a selfish miner is incentivized to deviate from the protocol and withhold its blocks under certain conditions. The analysis by Eyal and Sirer, as well as in followup work, considers a \emph{single} deviating miner (who may control a large fraction of the hashing power in the network) interacting with a remaining pool of honest miners. Here, we extend this analysis to the case where there are \emph{multiple} (non-colluding) selfish miners. We find that with multiple strategic miners, specific deviations from honest mining by multiple strategic agents can outperform honest mining, even if individually miners would not be incentivised to be dishonest. This previous point effectively renders the Bitcoin protocol to be less secure than previously thought.
A Linear Algorithm for Minimum Dominator Colorings of Orientations of Paths
Venue: arXiv cs.DM 2019
Year: 2019

In this paper we present an algorithm for finding a minimum dominator coloring of orientations of paths. To date this is the first algorithm for dominator colorings of digraphs in any capacity. We prove that the algorithm always provides a minimum dominator coloring of an oriented path and show that it runs in $\mathcal{O}(n)$ time. The algorithm is available at https://github.com/cat-astrophic/MDC-orientations_of_paths/.