OpenRaiser/Intern-Atlas huggingface dataset:
CPOI: A Compact Method to Archive Versioned RDF Triple-Sets
Venue: arXiv cs.DB 2019
Year: 2019

Large amounts of RDF/S data are produced and published lately, and several modern applications require the provision of versioning and archiving services over such datasets. In this paper we propose a novel storage index for archiving versions of such datasets, called CPOI (compact partial order index), that exploits the fact that an RDF Knowledge Base (KB), is a graph (or equivalently a set of triples), and thus it has not a unique serialization (as it happens with text). If we want to keep stored several versions we actually want to store multiple sets of triples. CPOI is a data structure for storing such sets aiming at reducing the storage space since this is important not only for reducing storage costs, but also for reducing the various communication costs and enabling hosting in main memory (and thus processing efficiently) large quantities of data. CPOI is based on a partial order structure over sets of triple identifiers, where the triple identifiers are represented in a gapped form using variable length encoding schemes. For this index we evaluate analytically and experimentally various identifier assignment techniques and their space savings. The results show significant storage savings, specifically, the storage space of the compressed sets in large and realistic synthetic datasets is about the 8% of the size of the uncompressed sets.
Using Deep Cross Modal Hashing and Error Correcting Codes for Improving the Efficiency of Attribute Guided Facial Image Retrieval
Venue: arXiv cs.CV 2019
Year: 2019

With benefits of fast query speed and low storage cost, hashing-based image retrieval approaches have garnered considerable attention from the research community. In this paper, we propose a novel Error-Corrected Deep Cross Modal Hashing (CMH-ECC) method which uses a bitmap specifying the presence of certain facial attributes as an input query to retrieve relevant face images from the database. In this architecture, we generate compact hash codes using an end-to-end deep learning module, which effectively captures the inherent relationships between the face and attribute modality. We also integrate our deep learning module with forward error correction codes to further reduce the distance between different modalities of the same subject. Specifically, the properties of deep hashing and forward error correction codes are exploited to design a cross modal hashing framework with high retrieval performance. Experimental results using two standard datasets with facial attributes-image modalities indicate that our CMH-ECC face image retrieval model outperforms most of the current attribute-based face image retrieval approaches.
Scaling Up Anomaly Detection Using In-DRAM Working Set of Active Flows Table
Venue: arXiv cs.NI 2019
Year: 2019

In the zettabyte era, per-flow measurement becomes more challenging owing to the growth of both traffic volumes and the number of flows. Also, swiftness of detection of anomalies (e.g., DDoS attack, congestion, link failure, and so on) becomes paramount. For fast and accurate anomaly detection, managing an accurate working set of active flows (WSAF) from massive volumes of packet influxes at line rates is a key challenge. WSAF is usually located in a very fast but expensive memory, such as TCAM or SRAM, and thus the number of entries to be stored is quite limited. To cope with the scalability issue of WSAF, we propose to use In-DRAM WSAF with scales, and put a compact data structure called FlowRegulator in front of WSAF to compensate for DRAM's slow access time by substantially reducing massive influxes to WSAF without compromising measurement accuracy. We prototype and evaluated our system in a large scale real-world experiment (connected to monitoring port of our campus main gateway router for 113 hours, and capturing 122.3 million flows). As one key application, FlowRegulator detected heavy hitters with 99.8% accuracy.
DSA-aware multiple patterning for the manufacturing of vias: Connections to graph coloring problems, IP formulations, and numerical experiments
Venue: arXiv cs.DM 2019
Year: 2019

In this paper, we investigate the manufacturing of vias in integrated circuits with a new technology combining lithography and Directed Self Assembly (DSA). Optimizing the production time and costs in this new process entails minimizing the number of lithography steps, which constitutes a generalization of graph coloring. We develop integer programming formulations for several variants of interest in the industry, and then study the computational performance of our formulations on true industrial instances. We show that the best integer programming formulation achieves good computational performance, and indicate potential directions to further speed-up computational time and develop exact approaches feasible for production.
LS-Tree: Model Interpretation When the Data Are Linguistic
Venue: arXiv cs.LG 2019
Year: 2019

We study the problem of interpreting trained classification models in the setting of linguistic data sets. Leveraging a parse tree, we propose to assign least-squares based importance scores to each word of an instance by exploiting syntactic constituency structure. We establish an axiomatic characterization of these importance scores by relating them to the Banzhaf value in coalitional game theory. Based on these importance scores, we develop a principled method for detecting and quantifying interactions between words in a sentence. We demonstrate that the proposed method can aid in interpretability and diagnostics for several widely-used language models.
VC Classes are Adversarially Robustly Learnable, but Only Improperly
Venue: arXiv cs.LG 2019
Year: 2019

We study the question of learning an adversarially robust predictor. We show that any hypothesis class $\mathcal{H}$ with finite VC dimension is robustly PAC learnable with an improper learning rule. The requirement of being improper is necessary as we exhibit examples of hypothesis classes $\mathcal{H}$ with finite VC dimension that are not robustly PAC learnable with any proper learning rule.
Adversarial Samples on Android Malware Detection Systems for IoT Systems
Venue: arXiv cs.CR 2019
Year: 2019

Many IoT(Internet of Things) systems run Android systems or Android-like systems. With the continuous development of machine learning algorithms, the learning-based Android malware detection system for IoT devices has gradually increased. However, these learning-based detection models are often vulnerable to adversarial samples. An automated testing framework is needed to help these learning-based malware detection systems for IoT devices perform security analysis. The current methods of generating adversarial samples mostly require training parameters of models and most of the methods are aimed at image data. To solve this problem, we propose a \textbf{t}esting framework for \textbf{l}earning-based \textbf{A}ndroid \textbf{m}alware \textbf{d}etection systems(TLAMD) for IoT Devices. The key challenge is how to construct a suitable fitness function to generate an effective adversarial sample without affecting the features of the application. By introducing genetic algorithms and some technical improvements, our test framework can generate adversarial samples for the IoT Android Application with a success rate of nearly 100\% and can perform black-box testing on the system.
Deep Reinforcement Learning from Policy-Dependent Human Feedback
Venue: arXiv cs.LG 2019
Year: 2019

To widen their accessibility and increase their utility, intelligent agents must be able to learn complex behaviors as specified by (non-expert) human users. Moreover, they will need to learn these behaviors within a reasonable amount of time while efficiently leveraging the sparse feedback a human trainer is capable of providing. Recent work has shown that human feedback can be characterized as a critique of an agent's current behavior rather than as an alternative reward signal to be maximized, culminating in the COnvergent Actor-Critic by Humans (COACH) algorithm for making direct policy updates based on human feedback. Our work builds on COACH, moving to a setting where the agent's policy is represented by a deep neural network. We employ a series of modifications on top of the original COACH algorithm that are critical for successfully learning behaviors from high-dimensional observations, while also satisfying the constraint of obtaining reduced sample complexity. We demonstrate the effectiveness of our Deep COACH algorithm in the rich 3D world of Minecraft with an agent that learns to complete tasks by mapping from raw pixels to actions using only real-time human feedback in 10-15 minutes of interaction.
Puppet Dubbing
Venue: arXiv cs.GR 2019
Year: 2019

Dubbing puppet videos to make the characters (e.g. Kermit the Frog) convincingly speak a new speech track is a popular activity with many examples of well-known puppets speaking lines from films or singing rap songs. But manually aligning puppet mouth movements to match a new speech track is tedious as each syllable of the speech must match a closed-open-closed segment of mouth movement for the dub to be convincing. In this work, we present two methods to align a new speech track with puppet video, one semi-automatic appearance-based and the other fully-automatic audio-based. The methods offer complementary advantages and disadvantages. Our appearance-based approach directly identifies closed-open-closed segments in the puppet video and is robust to low-quality audio as well as misalignments between the mouth movements and speech in the original performance, but requires some manual annotation. Our audio-based approach assumes the original performance matches a closed-open-closed mouth segment to each syllable of the original speech. It is fully automatic, robust to visual occlusions and fast puppet movements, but does not handle misalignments in the original performance. We compare the methods and show that both improve the credibility of the resulting video over simple baseline techniques, via quantitative evaluation and user ratings.
Lyapunov Criterion for Stochastic Systems and Its Applications in Distributed Computation
Venue: arXiv cs.SY 2019
Year: 2019

This paper presents new sufficient conditions for convergence and asymptotic or exponential stability of a stochastic discrete-time system, under which the constructed Lyapunov function always decreases in expectation along the system's solutions after a finite number of steps, but without necessarily strict decrease at every step, in contrast to the classical stochastic Lyapunov theory. As the first application of this new Lyapunov criterion, we look at the product of any random sequence of stochastic matrices, including those with zero diagonal entries, and obtain sufficient conditions to ensure the product almost surely converges to a matrix with identical rows; we also show that the rate of convergence can be exponential under additional conditions. As the second application, we study a distributed network algorithm for solving linear algebraic equations. We relax existing conditions on the network structures, while still guaranteeing the equations are solved asymptotically.
The effect of scene context on weakly supervised semantic segmentation
Venue: arXiv cs.CV 2019
Year: 2019

Image semantic segmentation is parsing image into several partitions in such a way that each region of which involves a semantic concept. In a weakly supervised manner, since only image-level labels are available, discriminating objects from the background is challenging, and in some cases, much more difficult. More specifically, some objects which are commonly seen in one specific scene (e.g. 'train' typically is seen on 'railroad track') are much more likely to be confused. In this paper, we propose a method to add the target-specific scenes in order to overcome the aforementioned problem. Actually, we propose a scene recommender which suggests to add some specific scene contexts to the target dataset in order to train the model more accurately. It is notable that this idea could be a complementary part of the baselines of many other methods. The experiments validate the effectiveness of the proposed method for the objects for which the scene context is added.
A Class of Narrow-Sense BCH Codes
Venue: arXiv cs.IT 2019
Year: 2019

BCH codes are an important class of cyclic codes which have applications in satellite communications, DVDs, disk drives, and two-dimensional bar codes. Although BCH codes have been widely studied, their parameters are known for only a few special classes. Recently, Ding et al. made some new progress in BCH codes. However, we still have very limited knowledge on the dimension of BCH codes, not to mention the weight distribution of BCH codes. In this paper, we generalize the results on BCH codes from several previous papers. The dimension of narrow-sense BCH codes of length $\frac{q^m-1}λ$ with designed distance $2\leq δ\leq \frac{q^{\lceil(m+1)/2 \rceil}-1}λ+1$ is settled, where $λ$ is any factor of $q-1$. The weight distributions of two classes of narrow-sense BCH codes of length $\frac{q^m-1}2$ with designed distance $δ=\frac{(q-1)q^{m-1}-q^{\lfloor(m-1)/2\rfloor}-1}2$ and $δ=\frac{(q-1)q^{m-1}-q^{\lfloor(m+1)/2\rfloor}-1}2$ are determined. The weight distribution of a class of BCH codes of length $\frac{q^m-1}{q-1}$ is determined. In particular, a subclass of this class of BCH codes is optimal with respect to the Griesmer bound. Some optimal linear codes obtained from this class of BCH codes are characterized.
Generalized Lineage-Aware Temporal Windows: Supporting Outer and Anti Joins in Temporal-Probabilistic Databases
Venue: arXiv cs.DB 2019
Year: 2019

The result of a temporal-probabilistic (TP) join with negation includes, at each time point, the probability with which a tuple of a positive relation ${\bf p}$ matches none of the tuples in a negative relation ${\bf n}$, for a given join condition $θ$. TP outer and anti joins thus resemble the characteristics of relational outer and anti joins also in the case when there exist time points at which input tuples from ${\bf p}$ have non-zero probabilities to be $true$ and input tuples from ${\bf n}$ have non-zero probabilities to be $false$, respectively. For the computation of TP joins with negation, we introduce generalized lineage-aware temporal windows, a mechanism that binds an output interval to the lineages of all the matching valid tuples of each input relation. We group the windows of two TP relations into three disjoint sets based on the way attributes, lineage expressions and intervals are produced. We compute all windows in an incremental manner, and we show that pipelined computations allow for the direct integration of our approach into PostgreSQL. We thereby alleviate the prevalent redundancies in the interval computations of existing approaches, which is proven by an extensive experimental evaluation with real-world datasets.
Cross-Modal Music Retrieval and Applications: An Overview of Key Methodologies
Venue: arXiv cs.IR 2019
Year: 2019

There has been a rapid growth of digitally available music data, including audio recordings, digitized images of sheet music, album covers and liner notes, and video clips. This huge amount of data calls for retrieval strategies that allow users to explore large music collections in a convenient way. More precisely, there is a need for cross-modal retrieval algorithms that, given a query in one modality (e.g., a short audio excerpt), find corresponding information and entities in other modalities (e.g., the name of the piece and the sheet music). This goes beyond exact audio identification and subsequent retrieval of metainformation as performed by commercial applications like Shazam [1].
Intrinsic Rowhammer PUFs: Leveraging the Rowhammer Effect for Improved Security
Venue: arXiv cs.CR 2019
Year: 2019

Physically Unclonable Functions (PUFs) have become an important and promising hardware primitive for device fingerprinting, device identification, or key storage. Intrinsic PUFs leverage components already found in existing devices, unlike extrinsic silicon PUFs, which are based on customized circuits that involve modification of hardware. In this work, we present a new type of a memory-based intrinsic PUF, which leverages the Rowhammer effect in DRAM modules; the Rowhammer PUF. Our PUF makes use of bit flips, which occur in DRAM cells due to rapid and repeated access of DRAM rows. Prior research has mainly focused on Rowhammer attacks, where the Rowhammer effect is used to illegitimately alter data stored in memory, e.g., to change page table entries or enable privilege escalation attacks. Meanwhile, this is the first work to use the Rowhammer effect in a positive context: to design a novel PUF. We extensively evaluate the Rowhammer PUF using commercial, off-the-shelf devices, not relying on custom hardware or an FPGA-based setup. The evaluation shows that the Rowhammer PUF holds required properties needed for the envisioned security applications, and could be deployed today.
RTbust: Exploiting Temporal Patterns for Botnet Detection on Twitter
Venue: arXiv cs.SI 2019
Year: 2019

Within OSNs, many of our supposedly online friends may instead be fake accounts called social bots, part of large groups that purposely re-share targeted content. Here, we study retweeting behaviors on Twitter, with the ultimate goal of detecting retweeting social bots. We collect a dataset of 10M retweets. We design a novel visualization that we leverage to highlight benign and malicious patterns of retweeting activity. In this way, we uncover a 'normal' retweeting pattern that is peculiar of human-operated accounts, and 3 suspicious patterns related to bot activities. Then, we propose a bot detection technique that stems from the previous exploration of retweeting behaviors. Our technique, called Retweet-Buster (RTbust), leverages unsupervised feature extraction and clustering. An LSTM autoencoder converts the retweet time series into compact and informative latent feature vectors, which are then clustered with a hierarchical density-based algorithm. Accounts belonging to large clusters characterized by malicious retweeting patterns are labeled as bots. RTbust obtains excellent detection results, with F1 = 0.87, whereas competitors achieve F1 < 0.76. Finally, we apply RTbust to a large dataset of retweets, uncovering 2 previously unknown active botnets with hundreds of accounts.
Coloring in the Links: Capturing Social Ties as They are Perceived
Venue: arXiv cs.CY 2019
Year: 2019

The richness that characterizes relationships is often absent when they are modeled using computational methods in network science. Typically, relationships are represented simply as links, perhaps with weights. The lack of finer granularity is due in part to the fact that, aside from linkage and strength, no fundamental or immediately obvious dimensions exist along which to categorize relationships. Here we propose a set of dimensions that capture major components of many relationships -- derived both from relevant academic literature and people's everyday descriptions of their relationships. We first review prominent findings in sociology and social psychology, highlighting dimensions that have been widely used to categorize social relationships. Next, we examine the validity of these dimensions empirically in two crowd-sourced experiments. Ultimately, we arrive at a set of ten major dimensions that can be used to categorize relationships: similarity, trust, romance, social support, identity, respect, knowledge exchange, power, fun, and conflict. These ten dimensions, while not dispositive, offer higher resolution than existing models. Indeed, we show that one can more accurately predict missing links in a social graph by using these dimensions than by using a state-of-the-art link embeddedness method. We also describe tinghy.org, an online platform we built to collect data about how social media users perceive their online relationships, allowing us to examine these dimensions at scale. Overall, by proposing a new way of modeling social graphs, our work aims to contribute both to theory in network science and practice in the design of social-networking applications.
Partial and Conditional Expectations in Markov Decision Processes with Integer Weights
Venue: arXiv cs.LO 2019
Year: 2019

The paper addresses two variants of the stochastic shortest path problem ('optimize the accumulated weight until reaching a goal state') in Markov decision processes (MDPs) with integer weights. The first variant optimizes partial expected accumulated weights, where paths not leading to a goal state are assigned weight 0, while the second variant considers conditional expected accumulated weights, where the probability mass is redistributed to paths reaching the goal. Both variants constitute useful approaches to the analysis of systems without guarantees on the occurrence of an event of interest (reaching a goal state), but have only been studied in structures with non-negative weights. Our main results are as follows. There are polynomial-time algorithms to check the finiteness of the supremum of the partial or conditional expectations in MDPs with arbitrary integer weights. If finite, then optimal weight-based deterministic schedulers exist. In contrast to the setting of non-negative weights, optimal schedulers can need infinite memory and their value can be irrational. However, the optimal value can be approximated up to an absolute error of $ε$ in time exponential in the size of the MDP and polynomial in $\log(1/ε)$.
Contrastive Variational Autoencoder Enhances Salient Features
Venue: arXiv cs.LG 2019
Year: 2019

Variational autoencoders are powerful algorithms for identifying dominant latent structure in a single dataset. In many applications, however, we are interested in modeling latent structure and variation that are enriched in a target dataset compared to some background---e.g. enriched in patients compared to the general population. Contrastive learning is a principled framework to capture such enriched variation between the target and background, but state-of-the-art contrastive methods are limited to linear models. In this paper, we introduce the contrastive variational autoencoder (cVAE), which combines the benefits of contrastive learning with the power of deep generative models. The cVAE is designed to identify and enhance salient latent features. The cVAE is trained on two related but unpaired datasets, one of which has minimal contribution from the salient latent features. The cVAE explicitly models latent features that are shared between the datasets, as well as those that are enriched in one dataset relative to the other, which allows the algorithm to isolate and enhance the salient latent features. The algorithm is straightforward to implement, has a similar run-time to the standard VAE, and is robust to noise and dataset purity. We conduct experiments across diverse types of data, including gene expression and facial images, showing that the cVAE effectively uncovers latent structure that is salient in a particular analysis.