OpenRaiser/Intern-Atlas huggingface dataset:
Quantifying Infra-Marginality and Its Trade-off with Group Fairness
Venue: arXiv cs.AI 2019
Year: 2019

In critical decision-making scenarios, optimizing accuracy can lead to a biased classifier, hence past work recommends enforcing group-based fairness metrics in addition to maximizing accuracy. However, doing so exposes the classifier to another kind of bias called infra-marginality. This refers to individual-level bias where some individuals/subgroups can be worse off than under simply optimizing for accuracy. For instance, a classifier implementing race-based parity may significantly disadvantage women of the advantaged race. To quantify this bias, we propose a general notion of $η$-infra-marginality that can be used to evaluate the extent of this bias. We prove theoretically that, unlike other fairness metrics, infra-marginality does not have a trade-off with accuracy: high accuracy directly leads to low infra-marginality. This observation is confirmed through empirical analysis on multiple simulated and real-world datasets. Further, we find that maximizing group fairness often increases infra-marginality, suggesting the consideration of both group-level fairness and individual-level infra-marginality. However, measuring infra-marginality requires knowledge of the true distribution of individual-level outcomes correctly and explicitly. We propose a practical method to measure infra-marginality, and a simple algorithm to maximize group-wise accuracy and avoid infra-marginality.
Attention-based Pairwise Multi-Perspective Convolutional Neural Network for Answer Selection in Question Answering
Venue: arXiv cs.CL 2019
Year: 2019

Over the past few years, question answering and information retrieval systems have become widely used. These systems attempt to find the answer of the asked questions from raw text sources. A component of these systems is Answer Selection which selects the most relevant from candidate answers. Syntactic similarities were mostly used to compute the similarity, but in recent works, deep neural networks have been used, making a significant improvement in this field. In this research, a model is proposed to select the most relevant answers to the factoid question from the candidate answers. The proposed model ranks the candidate answers in terms of semantic and syntactic similarity to the question, using convolutional neural networks. In this research, Attention mechanism and Sparse feature vector use the context-sensitive interactions between questions and answer sentence. Wide convolution increases the importance of the interrogative word. Pairwise ranking is used to learn differentiable representations to distinguish positive and negative answers. Our model indicates strong performance on the TrecQA Raw beating previous state-of-the-art systems by 1.4% in MAP and 1.1% in MRR while using the benefits of no additional syntactic parsers and external tools. The results show that using context-sensitive interactions between question and answer sentences can help to find the correct answer more accurately.
Discovering Interesting Cycles in Directed Graphs
Venue: arXiv cs.DS 2019
Year: 2019

Cycles in graphs often signify interesting processes. For example, cyclic trading patterns can indicate inefficiencies or economic dependencies in trade networks, cycles in food webs can identify fragile dependencies in ecosystems, and cycles in financial transaction networks can be an indication of money laundering. Identifying such interesting cycles, which can also be constrained to contain a given set of query nodes, although not extensively studied, is thus a problem of considerable importance. In this paper, we introduce the problem of discovering interesting cycles in graphs. We first address the problem of quantifying the extent to which a given cycle is interesting for a particular analyst. We then show that finding cycles according to this interestingness measure is related to the longest cycle and maximum mean-weight cycle problems (in the unconstrained setting) and to the maximum Steiner cycle and maximum mean Steiner cycle problems (in the constrained setting). A complexity analysis shows that finding interesting cycles is NP-hard, and is NP-hard to approximate within a constant factor in the unconstrained setting, and within a factor polynomial in the input size for the constrained setting. The latter inapproximability result implies a similar result for the maximum Steiner cycle and maximum mean Steiner cycle problems. Motivated by these hardness results, we propose a number of efficient heuristic algorithms. We verify the effectiveness of the proposed methods and demonstrate their practical utility on two real-world use cases: a food web and an international trade-network dataset.
Social Influence-based Attentive Mavens Mining and Aggregative Representation Learning for Group Recommendation
Venue: arXiv cs.SI 2019
Year: 2019

Frequent group activities of human beings have become an indispensable part in their daily life. Group recommendation can recommend satisfactory activities to group members in the recommender systems, and the key issue is how to aggregate preferences in different group members. Most existing group recommendation employed the predefined static aggregation strategies to aggregate the preferences of different group members, but these static strategies cannot simulate the dynamic group decision-making. Meanwhile, most of these methods depend on intuitions or assumptions to analyze the influence of group members and lack of convincing theoretical support. We argue that the influence of group members plays a particularly important role in group decision-making and it can better assist group profile modeling and perform more accurate group recommendation. To tackle the issue of preference aggregation for group recommendation, we propose a novel attentive aggregation representation learning method based on sociological theory for group recommendation, namely SIAGR (short for "Social Influence-based Attentive Group Recommendation"), which takes attention mechanisms and the popular method (BERT) as the aggregation representation for group profile modeling. Specifically, we analyze the influence of group members based on social identity theory and two-step flow theory and exploit an attentive mavens mining method. In addition, we develop a BERT-based representation method to learn the interaction of group members. Lastly, we complete the group recommendation under the neural collaborative filtering framework and verify the effectiveness of the proposed method by experimenting.
Usage of Permissioned Blockchain Architecture for Big Data in Electronic Medical Records
Venue: arXiv cs.CY 2019
Year: 2019

With the advent of blockchain technology, multiple research avenues and platforms for dialogue have opened up. However technology transfer to the pubic has not been implemented, such that regular public can access and make use of secure and decentralized software. Most blockchain solutions till date deal with financial applications or monetary transactions, which may not be helpful or be accessible to the general public, especially the lower levels of the financial society. Medi-Chain is a people-first medical blockchain with a usable desktop application and interface which makes use of cutting-edge blockchain technology along with BFT consensus protocols to ensure highly secure and private medical data records. This paper aims to bring about a change in how blockchains-as-a-service is perceived and how adoption of new technology is largely based on usability and ease of adoption.
Feasibility of Using Automatic Speech Recognition with Voices of Deaf and Hard-of-Hearing Individuals
Venue: arXiv cs.HC 2019
Year: 2019

Many personal devices have transitioned from visual-controlled interfaces to speech-controlled interfaces to reduce device costs and interactive friction. This transition has been hastened by the increasing capabilities of speech-controlled interfaces, e.g., Amazon Echo or Apple's Siri. A consequence is that people who are deaf or hard of hearing (DHH) may be unable to use these speech-controlled devices. We show that deaf speech has a high error rate compared to hearing speech, in commercial speech-controlled interfaces. Deaf speech had approximately a 78% word error rate (WER) compared to a hearing speech 18% WER. Our findings show that current speech-controlled interfaces are not usable by deaf and hard of hearing people. Therefore, it might be wise to pursue other methods for deaf persons to deliver natural commands to computers.
Towards automated feature engineering for credit card fraud detection using multi-perspective HMMs
Venue: arXiv cs.LG 2019
Year: 2019

Machine learning and data mining techniques have been used extensively in order to detect credit card frauds. However, most studies consider credit card transactions as isolated events and not as a sequence of transactions. In this framework, we model a sequence of credit card transactions from three different perspectives, namely (i) The sequence contains or doesn't contain a fraud (ii) The sequence is obtained by fixing the card-holder or the payment terminal (iii) It is a sequence of spent amount or of elapsed time between the current and previous transactions. Combinations of the three binary perspectives give eight sets of sequences from the (training) set of transactions. Each one of these sequences is modelled with a Hidden Markov Model (HMM). Each HMM associates a likelihood to a transaction given its sequence of previous transactions. These likelihoods are used as additional features in a Random Forest classifier for fraud detection. Our multiple perspectives HMM-based approach offers automated feature engineering to model temporal correlations so as to improve the effectiveness of the classification task and allows for an increase in the detection of fraudulent transactions when combined with the state of the art expert based feature engineering strategy for credit card fraud detection. In extension to previous works, we show that this approach goes beyond ecommerce transactions and provides a robust feature engineering over different datasets, hyperparameters and classifiers. Moreover, we compare strategies to deal with structural missing values.
Online Analytical Processsing on Graph Data
Venue: arXiv cs.DB 2019
Year: 2019

Online Analytical Processing (OLAP) comprises tools and algorithms that allow querying multidimensional databases. It is based on the multidimensional model, where data can be seen as a cube such that each cell contains one or more measures that can be aggregated along dimensions. In a Big Data scenario, traditional data warehousing and OLAP operations are clearly not sufficient to address current data analysis requirements, for example, social network analysis. Furthermore, OLAP operations and models can expand the possibilities of graph analysis beyond the traditional graph-based computation. Nevertheless, there is not much work on the problem of taking OLAP analysis to the graph data model. This paper proposes a formal multidimensional model for graph analysis, that considers the basic graph data, and also background information in the form of dimension hierarchies. The graphs in this model are node- and edge-labelled directed multi-hypergraphs, called graphoids, which can be defined at several different levels of granularity using the dimensions associated with them. Operations analogous to the ones used in typical OLAP over cubes are defined over graphoids. The paper presents a formal definition of the graphoid model for OLAP, proves that the typical OLAP operations on cubes can be expressed over the graphoid model, and shows that the classic data cube model is a particular case of the graphoid data model. Finally, a case study supports the claim that, for many kinds of OLAP-like analysis on graphs, the graphoid model works better than the typical relational OLAP alternative, and for the classic OLAP queries, it remains competitive.
Multi-level Attention network using text, audio and video for Depression Prediction
Venue: arXiv cs.CV 2019
Year: 2019

Depression has been the leading cause of mental-health illness worldwide. Major depressive disorder (MDD), is a common mental health disorder that affects both psychologically as well as physically which could lead to loss of lives. Due to the lack of diagnostic tests and subjectivity involved in detecting depression, there is a growing interest in using behavioural cues to automate depression diagnosis and stage prediction. The absence of labelled behavioural datasets for such problems and the huge amount of variations possible in behaviour makes the problem more challenging. This paper presents a novel multi-level attention based network for multi-modal depression prediction that fuses features from audio, video and text modalities while learning the intra and inter modality relevance. The multi-level attention reinforces overall learning by selecting the most influential features within each modality for the decision making. We perform exhaustive experimentation to create different regression models for audio, video and text modalities. Several fusions models with different configurations are constructed to understand the impact of each feature and modality. We outperform the current baseline by 17.52% in terms of root mean squared error.
Adversarial Robustness of Similarity-Based Link Prediction
Venue: arXiv cs.AI 2019
Year: 2019

Link prediction is one of the fundamental problems in social network analysis. A common set of techniques for link prediction rely on similarity metrics which use the topology of the observed subnetwork to quantify the likelihood of unobserved links. Recently, similarity metrics for link prediction have been shown to be vulnerable to attacks whereby observations about the network are adversarially modified to hide target links. We propose a novel approach for increasing robustness of similarity-based link prediction by endowing the analyst with a restricted set of reliable queries which accurately measure the existence of queried links. The analyst aims to robustly predict a collection of possible links by optimally allocating the reliable queries. We formalize the analyst problem as a Bayesian Stackelberg game in which they first choose the reliable queries, followed by an adversary who deletes a subset of links among the remaining (unreliable) queries by the analyst. The analyst in our model is uncertain about the particular target link the adversary attempts to hide, whereas the adversary has full information about the analyst and the network. Focusing on similarity metrics using only local information, we show that the problem is NP-Hard for both players, and devise two principled and efficient approaches for solving it approximately. Extensive experiments with real and synthetic networks demonstrate the effectiveness of our approach.
Asynchronous Time-Parallel Method based on Laplace Transform
Venue: arXiv cs.DC 2019
Year: 2019

Laplace transform method has proved to be very efficient and easy to parallelize for the solution of time-dependent problems. However, the synchronization delay among processors implies an upper bound on the expectable acceleration factor, which leads to a lot of wasted time. In this paper, we propose an original asynchronous Laplace transform method formalized for quasilinear problems based on the well-known Gaver-Stehfest algorithm. Parallel experiments show the convergence of our new method, as well as several interesting properties compared with the classical algorithms.
Minimizing the Societal Cost of Credit Card Fraud with Limited and Imbalanced Data
Venue: arXiv cs.LG 2019
Year: 2019

Machine learning has automated much of financial fraud detection, notifying firms of, or even blocking, questionable transactions instantly. However, data imbalance starves traditionally trained models of the content necessary to detect fraud. This study examines three separate factors of credit card fraud detection via machine learning. First, it assesses the potential for different sampling methods, undersampling and Synthetic Minority Oversampling Technique (SMOTE), to improve algorithm performance in data-starved environments. Additionally, five industry-practical machine learning algorithms are evaluated on total fraud cost savings in addition to traditional statistical metrics. Finally, an ensemble of individual models is trained with a genetic algorithm to attempt to generate higher cost efficiency than its components. Monte Carlo performance distributions discerned random undersampling outperformed SMOTE in lowering fraud costs, and that an ensemble was unable to outperform its individual parts. Most notably,the F-1 Score, a traditional metric often used to measure performance with imbalanced data, was uncorrelated with derived cost efficiency. Assuming a realistic cost structure can be derived, cost-based metrics provide an essential supplement to objective statistical evaluation.
Neural Linguistic Steganography
Venue: arXiv cs.CL 2019
Year: 2019

Whereas traditional cryptography encrypts a secret message into an unintelligible form, steganography conceals that communication is taking place by encoding a secret message into a cover signal. Language is a particularly pragmatic cover signal due to its benign occurrence and independence from any one medium. Traditionally, linguistic steganography systems encode secret messages in existing text via synonym substitution or word order rearrangements. Advances in neural language models enable previously impractical generation-based techniques. We propose a steganography technique based on arithmetic coding with large-scale neural language models. We find that our approach can generate realistic looking cover sentences as evaluated by humans, while at the same time preserving security by matching the cover message distribution with the language model distribution.
Classes of graphs with low complexity: the case of classes with bounded linear rankwidth
Venue: arXiv cs.LO 2019
Year: 2019

Classes with bounded rankwidth are MSO-transductions of trees and classes with bounded linear rankwidth are MSO-transductions of paths -- a result that shows a strong link between the properties of these graph classes considered from the point of view of structural graph theory and from the point of view of finite model theory. We take both views on classes with bounded linear rankwidth and prove structural and model theoretic properties of these classes. The structural results we obtain are the following. 1) The number of unlabeled graphs of order $n$ with linear rank-width at most~$r$ is at most $\bigl[(r/2)!\,2^{\binom{r}{2}}3^{r+2}\bigr]^n$. 2) Graphs with linear rankwidth at most $r$ are linearly $χ$-bounded. Actually, they have bounded $c$-chromatic number, meaning that they can be colored with $f(r)$ colors, each color inducing a cograph. 3) To the contrary, based on a Ramsey-like argument, we prove for every proper hereditary family $F$ of graphs (like cographs) that there is a class with bounded rankwidth that does not have the property that graphs in it can be colored by a bounded number of colors, each inducing a subgraph in $F$. From the model theoretical side we obtain the following results: 1) A direct short proof that graphs with linear rankwidth at most $r$ are first-order transductions of linear orders. This result could also be derived from Colcombet's theorem on first-order transduction of linear orders and the equivalence of linear rankwidth with linear cliquewidth. 2) For a class $C$ with bounded linear rankwidth the following conditions are equivalent: a) $C$ is stable, b) $C$ excludes some half-graph as a semi-induced subgraph, c) $C$ is a first-order transduction of a class with bounded pathwidth. These results open the perspective to study classes admitting low linear rankwidth covers.
Empirical Hypothesis Space Reduction
Venue: arXiv cs.LG 2019
Year: 2019

Selecting appropriate regularization coefficients is critical to performance with respect to regularized empirical risk minimization problems. Existing theoretical approaches attempt to determine the coefficients in order for regularized empirical objectives to be upper-bounds of true objectives, uniformly over a hypothesis space. Such an approach is, however, known to be over-conservative, especially in high-dimensional settings with large hypothesis space. In fact, an existing generalization error bound in variance-based regularization is $O(\sqrt{d \log n/n})$, where $d$ is the dimension of hypothesis space, and thus the number of samples required for convergence linearly increases with respect to $d$. This paper proposes an algorithm that calculates regularization coefficient, one which results in faster convergence of generalization error $O(\sqrt{\log n/n})$ and whose leading term is independent of the dimension $d$. This faster convergence without dependence on the size of the hypothesis space is achieved by means of empirical hypothesis space reduction, which, with high probability, successfully reduces a hypothesis space without losing the true optimum solution. Calculation of uniform upper bounds over reduced spaces, then, enables acceleration of the convergence of generalization error.
Defeating Opaque Predicates Statically through Machine Learning and Binary Analysis
Venue: arXiv cs.CR 2019
Year: 2019

We present a new approach that bridges binary analysis techniques with machine learning classification for the purpose of providing a static and generic evaluation technique for opaque predicates, regardless of their constructions. We use this technique as a static automated deobfuscation tool to remove the opaque predicates introduced by obfuscation mechanisms. According to our experimental results, our models have up to 98% accuracy at detecting and deob-fuscating state-of-the-art opaque predicates patterns. By contrast, the leading edge deobfuscation methods based on symbolic execution show less accuracy mostly due to the SMT solvers constraints and the lack of scalability of dynamic symbolic analyses. Our approach underlines the efficiency of hybrid symbolic analysis and machine learning techniques for a static and generic deobfuscation methodology.
Under the Conditions of Non-Agenda Ownership: Social Media Users in the 2019 Ukrainian Presidential Elections Campaign
Venue: arXiv cs.CY 2019
Year: 2019

Owing to its history and challenging circumstances, social networks community in Ukraine is a very interesting polygon for the study of communications in the constantly changing environment, especially in the political discourse. This unique environment requires three dimensions to ascertain the political position of its participant. But 2019 presidential elections made this object even more spectacular. The winner of elections comedian Volodymyr Zelenskyi reached 73% of votes without any issue ownership, with empty agenda, and this influenced the electoral content of social networks and their authors behavior. We saw, that the issue ownership by other candidates succeeds in making their issues more salient in social networks. But the new phenomena, the non-agenda ownership, overcome any ideological influence, especially under the conditions of punishment mechanism applied to old politicians. Analyzing social media content and users behavior in the period between two rounds of elections, we found considerable overlaps between this campaign and the 2016 Trump campaign. We approved the widespread of filter bubbles, negative campaign messages, fake news and conspiracy theories. Active and powerful core of Ukrainian Facebook that was responsible for the Revolution of dignity now became less significant and even turns into the huge filter bubble of active people. We also proved that manipulations and fake news in the environment of private groups may be as much powerful as in a case of classical communication based around the opinion leaders.