OpenRaiser/Intern-Atlas huggingface dataset:
FakeCatcher: Detection of Synthetic Portrait Videos using Biological Signals
Venue: arXiv cs.CV 2020
Year: 2020

The recent proliferation of fake portrait videos poses direct threats on society, law, and privacy. Believing the fake video of a politician, distributing fake pornographic content of celebrities, fabricating impersonated fake videos as evidence in courts are just a few real world consequences of deep fakes. We present a novel approach to detect synthetic content in portrait videos, as a preventive solution for the emerging threat of deep fakes. In other words, we introduce a deep fake detector. We observe that detectors blindly utilizing deep learning are not effective in catching fake content, as generative models produce formidably realistic results. Our key assertion follows that biological signals hidden in portrait videos can be used as an implicit descriptor of authenticity, because they are neither spatially nor temporally preserved in fake content. To prove and exploit this assertion, we first engage several signal transformations for the pairwise separation problem, achieving 99.39% accuracy. Second, we utilize those findings to formulate a generalized classifier for fake content, by analyzing proposed signal transformations and corresponding feature sets. Third, we generate novel signal maps and employ a CNN to improve our traditional classifier for detecting synthetic content. Lastly, we release an "in the wild" dataset of fake portrait videos that we collected as a part of our evaluation process. We evaluate FakeCatcher on several datasets, resulting with 96%, 94.65%, 91.50%, and 91.07% accuracies, on Face Forensics, Face Forensics++, CelebDF, and on our new Deep Fakes Dataset respectively. We also analyze signals from various facial regions, under image distortions, with varying segment durations, from different generators, against unseen datasets, and under several dimensionality reduction techniques.
A Survey of Biological Building Blocks for Synthetic Molecular Communication Systems
Venue: arXiv cs.ET 2020
Year: 2020

Synthetic molecular communication (MC) is a new communication engineering paradigm which is expected to enable revolutionary applications such as smart drug delivery and real-time health monitoring. The design and implementation of synthetic MC systems (MCSs) at nano- and microscale is very challenging. This is particularly true for synthetic MCSs employing biological components as transmitters and receivers or as interfaces with natural biological MCSs. Nevertheless, since such biological components have been optimized by nature over billions of years, using them in synthetic MCSs is highly promising. This paper provides a survey of biological components that can potentially serve as the main building blocks, i.e., transmitter, receiver, and signaling particles, for the design and implementation of synthetic MCSs. Nature uses a large variety of signaling particles of different sizes and with vastly different properties for communication among biological entities. Here, we focus on three important classes of signaling particles: cations (specifically protons and calcium ions), neurotransmitters (specifically acetylcholine, dopamine, and serotonin), and phosphopeptides. For each of these candidate signaling particles, we present several specific transmitter and receiver structures mainly built upon proteins that are capable of performing the distinct physiological functionalities required from the transmitters and receivers of MCSs. Moreover, we present options for both microscale implementation of MCSs as well as the micro-to-macroscale interfaces needed for experimental evaluation of MCSs. Furthermore, we outline new research directions for the implementation and the theoretical design and analysis of the proposed transmitter and receiver architectures.
Life is Random, Time is Not: Markov Decision Processes with Window Objectives
Venue: arXiv cs.LO 2020
Year: 2020

The window mechanism was introduced by Chatterjee et al. to strengthen classical game objectives with time bounds. It permits to synthesize system controllers that exhibit acceptable behaviors within a configurable time frame, all along their infinite execution, in contrast to the traditional objectives that only require correctness of behaviors in the limit. The window concept has proved its interest in a variety of two-player zero-sum games because it enables reasoning about such time bounds in system specifications, but also thanks to the increased tractability that it usually yields. In this work, we extend the window framework to stochastic environments by considering Markov decision processes. A fundamental problem in this context is the threshold probability problem: given an objective it aims to synthesize strategies that guarantee satisfying runs with a given probability. We solve it for the usual variants of window objectives, where either the time frame is set as a parameter, or we ask if such a time frame exists. We develop a generic approach for window-based objectives and instantiate it for the classical mean-payoff and parity objectives, already considered in games. Our work paves the way to a wide use of the window mechanism in stochastic models.
Creative AI Through Evolutionary Computation
Venue: arXiv cs.NE 2020
Year: 2020

The main power of artificial intelligence is not in modeling what we already know, but in creating solutions that are new. Such solutions exist in extremely large, high-dimensional, and complex search spaces. Population-based search techniques, i.e. variants of evolutionary computation, are well suited to finding them. These techniques are also well positioned to take advantage of large-scale parallel computing resources, making creative AI through evolutionary computation the likely "next deep learning".
A Speech Act Classifier for Persian Texts and its Application in Identifying Rumors
Venue: arXiv cs.CL 2020
Year: 2020

Speech Acts (SAs) are one of the important areas of pragmatics, which give us a better understanding of the state of mind of the people and convey an intended language function. Knowledge of the SA of a text can be helpful in analyzing that text in natural language processing applications. This study presents a dictionary-based statistical technique for Persian SA recognition. The proposed technique classifies a text into seven classes of SA based on four criteria: lexical, syntactic, semantic, and surface features. WordNet as the tool for extracting synonym and enriching features dictionary is utilized. To evaluate the proposed technique, we utilized four classification methods including Random Forest (RF), Support Vector Machine (SVM), Naive Bayes (NB), and K-Nearest Neighbors (KNN). The experimental results demonstrate that the proposed method using RF and SVM as the best classifiers achieved a state-of-the-art performance with an accuracy of 0.95 for classification of Persian SAs. Our original vision of this work is introducing an application of SA recognition on social media content, especially the common SA in rumors. Therefore, the proposed system utilized to determine the common SAs in rumors. The results showed that Persian rumors are often expressed in three SA classes including narrative, question, and threat, and in some cases with the request SA.
Precise Performance Analysis of the Box-Elastic Net under Matrix Uncertainties
Venue: arXiv cs.LG 2020
Year: 2020

In this letter, we consider the problem of recovering an unknown sparse signal from noisy linear measurements, using an enhanced version of the popular Elastic-Net (EN) method. We modify the EN by adding a box-constraint, and we call it the Box-Elastic Net (Box-EN). We assume independent identically distributed (iid) real Gaussian measurement matrix with additive Gaussian noise. In many practical situations, the measurement matrix is not perfectly known, and so we only have a noisy estimate of it. In this work, we precisely characterize the mean squared error and the probability of support recovery of the Box-Elastic Net in the high-dimensional asymptotic regime. Numerical simulations validate the theoretical predictions derived in the paper and also show that the boxed variant outperforms the standard EN.
Order polarities
Venue: arXiv cs.LO 2020
Year: 2020

We define an order polarity to be a polarity $(X,Y,R)$ where $X$ and $Y$ are partially ordered, and we define an extension polarity to be a triple $(e_X,e_Y,R)$ such that $e_X:P\to X$ and $e_Y:P\to Y$ are poset extensions and $(X,Y,R)$ is an order polarity. We define a hierarchy of increasingly strong coherence conditions for extension polarities, each equivalent to the existence of a pre-order structure on $X\cup Y$ such that the natural embeddings, $ι_X$ and $ι_Y$, of $X$ and $Y$, respectively, into $X\cup Y$ preserve the order structures of $X$ and $Y$ in increasingly strict ways. We define a Galois polarity to be an extension polarity where $e_X$ and $e_Y$ are meet- and join-extensions respectively, and we show that for such polarities there is a unique pre-order on $X\cup Y$ such that $ι_X$ and $ι_Y$ satisfy particularly strong preservation properties. We define morphisms for polarities, providing the class of Galois polarities with the structure of a category, and we define an adjunction between this category and the category of $Δ_1$-completions and appropriate homomorphisms. We formalize the theory of extension polarities and prove a duality principle to the effect that if a statement is true for all extension polarities then so too must be its dual statement.
A Direct and Generalized Construction of Polyphase Complementary Set with Low PMEPR and High Code-Rate for OFDM System
Venue: arXiv cs.IT 2020
Year: 2020

A major drawback of orthogonal frequency division multiplexing (OFDM) systems is their high peak-to-mean envelope power ratio (PMEPR). The PMEPR problem can be solved by adopting large codebooks consisting of complementary sequences with low PMEPR. In this paper, we present a new construction of polyphase complementary sets (CSs) using generalized Boolean functions (GBFs), which generalizes Schmidt's construction in 2007, Paterson's construction in 2000 and Golay complementary pairs (GCPs) given by Davis and Jedwab in 1999. Compared with Schmidt's approach, our proposed CSs lead to lower PMEPR with higher code-rate for sequences constructed from higher-order ($\geq 3$) GBFs. We obtain polyphase complementary sequences with maximum PMEPR of $2^{k+1}$ and $2^{k+2}-2M$ where $k,M$ are non-negative integers that can be easily derived from the GBF associated with the CS.
Time Pressure in Software Engineering: A Systematic Review
Venue: arXiv cs.SE 2020
Year: 2020

Large project overruns and overtime work have been reported in the software industry, resulting in additional expense for companies and personal issues for developers. The present work aims to provide an overview of studies related to time pressure in software engineering; specifically, existing definitions, possible causes, and metrics relevant to time pressure were collected, and a mapping of the studies to software processes and approaches was performed. Moreover, we synthesize results of existing quantitative studies on the effects of time pressure on software development, and offer practical takeaways for practitioners and researchers, based on empirical evidence. Our search strategy examined 5,414 sources, found through repository searches and snowballing. Applying inclusion and exclusion criteria resulted in the selection of 102 papers, which made relevant contributions related to time pressure in software engineering. The majority of high quality studies report increased productivity and decreased quality under time pressure. Frequent categories of studies focus on quality assurance, cost estimation, and process simulation. It appears that time pressure is usually caused by errors in cost estimation. The effect of time pressure is most often identified during software quality assurance. The majority of empirical studies report increased productivity under time pressure, while the most cost estimation and process simulation models assume that compressing the schedule increases the total needed hours. We also find evidence of the mediating effect of knowledge on the effects of time pressure, and that tight deadlines impact tasks with an algorithmic nature more severely. Future research should better contextualize quantitative studies to account for the existing conflicting results and to provide an understanding of situations when time pressure is either beneficial or harmful.
A New Design Framework on Device-to-Device Coded Caching with Optimal Rate and Significantly Less Subpacketizations
Venue: arXiv cs.IT 2020
Year: 2020

In this paper, we propose a new design framework on Device-to-Device (D2D) coded caching networks with optimal rate but significantly less file subpacketizations compared to that of the well-known D2D coded caching scheme proposed by Ji, Caire and Molisch (JCM). The proposed design framework is referred to as the {\em Packet Type-based (PTB) design}, where D2D users are first partitioned into multiple groups, which leads to a so-called {\em raw packet saving gain}. Then the corresponding multicasting group types and packet types are specified based on the prescribed node partition. By a careful selection of transmitters within each multicasting group, a so-called {\em further splitting ratio gain} can also be achieved. By the joint effect of the {\em raw packet saving gain} and the {\em further splitting ratio gain}, an order-wise subpacketization reduction can be achieved compared to the JCM scheme while preserving the optimal rate for large system parameter regimes. In addition, as the first time presented in the literature according to our knowledge, we find that unequal subpacketizaton is a key to achieve a subpacketization gain when the number of users is odd. As a by-product, instead of directly translating shared link caching schemes to D2D caching schemes, at least for the sake of subpackeitzations, a new design framework is indeed needed.
IOTA-based Directed Acyclic Graphs without Orphans
Venue: arXiv cs.DC 2020
Year: 2020

Directed Acylic Graphs (DAGs) are emerging as an attractive alternative to traditional blockchain architectures for distributed ledger technology (DLT). In particular DAG ledgers with stochastic attachment mechanisms potentially offer many advantages over blockchain, including scalability and faster transaction speeds. However, the random nature of the attachment mechanism coupled with the requirement of protection against double-spend transactions leaves open the possibility that not all transactions will be eventually validated. Such transactions are said to be orphaned, and will never be validated. Our principal contribution is to propose a simple modification to the attachment mechanism for the Tangle (the IOTA DAG architecture). This modification ensures that all transactions are validated in finite time, and preserves essential features of the popular Monte-Carlo selection algorithm. In order to demonstrate these results we derive a fluid approximation for the Tangle (in the limit of infinite arrival rate) and prove that this fluid model exhibits the desired behavior. We also present simulations which validate the results for finite arrival rates.
Cascade Submodular Maximization: Question Selection and Sequencing in Online Personality Quiz
Venue: arXiv cs.LG 2020
Year: 2020

Personality quiz is a powerful tool that enables costumer segmentation by actively asking them questions, and marketers are using it as an effective method of generating leads and increasing e-commerce sales. In this paper, we study the problem of how to select and sequence a group of quiz questions so as to optimize the quality of customer segmentation. We assume that the customer will sequentially scan the list of questions. After reading a question, the customer makes two, possibly correlated, random decisions: 1) she first decides whether to answer this question or not, and then 2) decides whether to continue reading the next question or not. We further assume that the utility of questions that have been answered can be captured by a monotone and submodular function. In general, our problem falls into the category of non-adaptive active learning based customer profiling. Note that under the our model, the probability of a question being answered depends on the location of that question, as well as the set of other questions placed ahead of that question, this makes our problem fundamentally different from existing studies on submodular optimization. We develop a series of question selection and sequencing strategies with provable performance bound. Although we focus on the application of quiz design in this paper, our results apply to a broad range of applications, including assortment optimization with position bias effect.
Object Detection based on Region Decomposition and Assembly
Venue: arXiv cs.CV 2020
Year: 2020

Region-based object detection infers object regions for one or more categories in an image. Due to the recent advances in deep learning and region proposal methods, object detectors based on convolutional neural networks (CNNs) have been flourishing and provided the promising detection results. However, the detection accuracy is degraded often because of the low discriminability of object CNN features caused by occlusions and inaccurate region proposals. In this paper, we therefore propose a region decomposition and assembly detector (R-DAD) for more accurate object detection. In the proposed R-DAD, we first decompose an object region into multiple small regions. To capture an entire appearance and part details of the object jointly, we extract CNN features within the whole object region and decomposed regions. We then learn the semantic relations between the object and its parts by combining the multi-region features stage by stage with region assembly blocks, and use the combined and high-level semantic features for the object classification and localization. In addition, for more accurate region proposals, we propose a multi-scale proposal layer that can generate object proposals of various scales. We integrate the R-DAD into several feature extractors, and prove the distinct performance improvement on PASCAL07/12 and MSCOCO18 compared to the recent convolutional detectors.
Heavy-Tailed Universality Predicts Trends in Test Accuracies for Very Large Pre-Trained Deep Neural Networks
Venue: arXiv cs.LG 2020
Year: 2020

Given two or more Deep Neural Networks (DNNs) with the same or similar architectures, and trained on the same dataset, but trained with different solvers, parameters, hyper-parameters, regularization, etc., can we predict which DNN will have the best test accuracy, and can we do so without peeking at the test data? In this paper, we show how to use a new Theory of Heavy-Tailed Self-Regularization (HT-SR) to answer this. HT-SR suggests, among other things, that modern DNNs exhibit what we call Heavy-Tailed Mechanistic Universality (HT-MU), meaning that the correlations in the layer weight matrices can be fit to a power law (PL) with exponents that lie in common Universality classes from Heavy-Tailed Random Matrix Theory (HT-RMT). From this, we develop a Universal capacity control metric that is a weighted average of PL exponents. Rather than considering small toy NNs, we examine over 50 different, large-scale pre-trained DNNs, ranging over 15 different architectures, trained on ImagetNet, each of which has been reported to have different test accuracies. We show that this new capacity metric correlates very well with the reported test accuracies of these DNNs, looking across each architecture (VGG16/.../VGG19, ResNet10/.../ResNet152, etc.). We also show how to approximate the metric by the more familiar Product Norm capacity measure, as the average of the log Frobenius norm of the layer weight matrices. Our approach requires no changes to the underlying DNN or its loss function, it does not require us to train a model (although it could be used to monitor training), and it does not even require access to the ImageNet data.
Eva-CiM: A System-Level Performance and Energy Evaluation Framework for Computing-in-Memory Architectures
Venue: arXiv cs.AR 2020
Year: 2020

Computing-in-Memory (CiM) architectures aim to reduce costly data transfers by performing arithmetic and logic operations in memory and hence relieve the pressure due to the memory wall. However, determining whether a given workload can really benefit from CiM, which memory hierarchy and what device technology should be adopted by a CiM architecture requires in-depth study that is not only time consuming but also demands significant expertise in architectures and compilers. This paper presents an energy evaluation framework, Eva-CiM, for systems based on CiM architectures. Eva-CiM encompasses a multi-level (from device to architecture) comprehensive tool chain by leveraging existing modeling and simulation tools such as GEM5, McPAT [2] and DESTINY [3]. To support high-confidence prediction, rapid design space exploration and ease of use, Eva-CiM introduces several novel modeling/analysis approaches including models for capturing memory access and dependency-aware ISA traces, and for quantifying interactions between the host CPU and CiM modules. Eva-CiM can readily produce energy estimates of the entire system for a given program, a processor architecture, and the CiM array and technology specifications. Eva-CiM is validated by comparing with DESTINY [3] and [4], and enables findings including practical contributions from CiM-supported accesses, CiM-sensitive benchmarking as well as the pros and cons of increased memory size for CiM. Eva-CiM also enables exploration over different configurations and device technologies, showing 1.3-6.0X energy improvement for SRAM and 2.0-7.9X for FeFET-RAM, respectively.
Black Box Submodular Maximization: Discrete and Continuous Settings
Venue: arXiv cs.LG 2020
Year: 2020

In this paper, we consider the problem of black box continuous submodular maximization where we only have access to the function values and no information about the derivatives is provided. For a monotone and continuous DR-submodular function, and subject to a bounded convex body constraint, we propose Black-box Continuous Greedy, a derivative-free algorithm that provably achieves the tight $[(1-1/e)OPT-ε]$ approximation guarantee with $O(d/ε^3)$ function evaluations. We then extend our result to the stochastic setting where function values are subject to stochastic zero-mean noise. It is through this stochastic generalization that we revisit the discrete submodular maximization problem and use the multi-linear extension as a bridge between discrete and continuous settings. Finally, we extensively evaluate the performance of our algorithm on continuous and discrete submodular objective functions using both synthetic and real data.
Learning Vertex Representations for Bipartite Networks
Venue: arXiv cs.SI 2020
Year: 2020

Recent years have witnessed a widespread increase of interest in network representation learning (NRL). By far most research efforts have focused on NRL for homogeneous networks like social networks where vertices are of the same type, or heterogeneous networks like knowledge graphs where vertices (and/or edges) are of different types. There has been relatively little research dedicated to NRL for bipartite networks. Arguably, generic network embedding methods like node2vec and LINE can also be applied to learn vertex embeddings for bipartite networks by ignoring the vertex type information. However, these methods are suboptimal in doing so, since real-world bipartite networks concern the relationship between two types of entities, which usually exhibit different properties and patterns from other types of network data. For example, E-Commerce recommender systems need to capture the collaborative filtering patterns between customers and products, and search engines need to consider the matching signals between queries and webpages.