OpenRaiser/Intern-Atlas huggingface dataset:
Towards Effective Deep Embedding for Zero-Shot Learning
Venue: arXiv cs.CV 2018
Year: 2018

Zero-shot learning (ZSL) can be formulated as a cross-domain matching problem: after being projected into a joint embedding space, a visual sample will match against all candidate class-level semantic descriptions and be assigned to the nearest class. In this process, the embedding space underpins the success of such matching and is crucial for ZSL. In this paper, we conduct an in-depth study on the construction of embedding space for ZSL and posit that an ideal embedding space should satisfy two criteria: intra-class compactness and inter-class separability. While the former encourages the embeddings of visual samples of one class to distribute tightly close to the semantic description embedding of this class, the latter requires embeddings from different classes to be well separated from each other. Towards this goal, we present a simple but effective two-branch network to simultaneously map semantic descriptions and visual samples into a joint space, on which visual embeddings are forced to regress to their class-level semantic embeddings and the embeddings crossing classes are required to be distinguishable by a trainable classifier. Furthermore, we extend our method to a transductive setting to better handle the model bias problem in ZSL (i.e., samples from unseen classes tend to be categorized into seen classes) with minimal extra supervision. Specifically, we propose a pseudo labeling strategy to progressively incorporate the testing samples into the training process and thus balance the model between seen and unseen classes. Experimental results on five standard ZSL datasets show the superior performance of the proposed method and its transductive extension.
Recognizing Generating Subgraphs in Graphs without Cycles of Lengths 6 and 7
Venue: arXiv cs.CC 2018
Year: 2018

Let $B$ be an induced complete bipartite subgraph of $G$ on vertex sets of bipartition $B_{X}$ and $B_{Y}$. The subgraph $B$ is {\it generating} if there exists an independent set $S$ such that each of $S \cup B_{X}$ and $S \cup B_{Y}$ is a maximal independent set in the graph. If $B$ is generating, it \textit{produces} the restriction $w(B_{X})=w(B_{Y})$. Let $w:V(G) \longrightarrow\mathbb{R}$ be a weight function. We say that $G$ is $w$-well-covered if all maximal independent sets are of the same weight. The graph $G$ is $w$-well-covered if and only if $w$ satisfies all restrictions produced by all generating subgraphs of $G$. Therefore, generating subgraphs play an important role in characterizing weighted well-covered graphs. It is an \textbf{NP}-complete problem to decide whether a subgraph is generating, even when the subgraph is isomorphic to $K_{1,1}$ \cite{bnz:related}. We present a polynomial algorithm for recognizing generating subgraphs for graphs without cycles of lengths 6 and 7.
Leadership in Singleton Congestion Games: What is Hard and What is Easy
Venue: arXiv cs.GT 2018
Year: 2018

We study the problem of computing Stackelberg equilibria Stackelberg games whose underlying structure is in congestion games, focusing on the case where each player can choose a single resource (a.k.a. singleton congestion games) and one of them acts as leader. In particular, we address the cases where the players either have the same action spaces (i.e., the set of resources they can choose is the same for all of them) or different ones, and where their costs are either monotonic functions of the resource congestion or not. We show that, in the case where the players have different action spaces, the cost the leader incurs in a Stackelberg equilibrium cannot be approximated in polynomial time up to within any polynomial factor in the size of the game unless P = NP, independently of the cost functions being monotonic or not. We show that a similar result also holds when the players have nonmonotonic cost functions, even if their action spaces are the same. Differently, we prove that the case with identical action spaces and monotonic cost functions is easy, and propose polynomial-time algorithm for it. We also improve an algorithm for the computation of a socially optimal equilibrium in singleton congestion games with the same action spaces without leadership, and extend it to the computation of a Stackelberg equilibrium for the case where the leader is restricted to pure strategies. For the cases in which the problem of finding an equilibrium is hard, we show how, in the optimistic setting where the followers break ties in favor of the leader, the problem can be formulated via mixed-integer linear programming techniques, which computational experiments show to scale quite well.
Analyze Unstructured Data Patterns for Conceptual Representation
Venue: arXiv cs.IR 2018
Year: 2018

Online news media provides aggregated news and stories from different sources all over the world and up-to-date news coverage. The main goal of this study is to have a solution that considered as a homogeneous source for the news and to represent the news in a new conceptual framework. Furthermore, the user can easily find different updated news in a fast way through the designed interface. The Mobile App implementation is based on modeling the multi-level conceptual analysis discipline. Discovering main concepts of any domain is captured from the hidden unstructured data that are analyzed by the proposed solution. Concepts are discovered through analyzing data patterns to be structured into a tree-based interface for easy navigation for the end user, through the discovered news concepts. Our final experiment results showing that analyzing the news before displaying to the end-user and restructuring the final output in a conceptual multilevel structure, that producing new display frame for the end user to find the related information to his interest.
Understanding Latent Factors Using a GWAP
Venue: arXiv cs.IR 2018
Year: 2018

Recommender systems relying on latent factor models often appear as black boxes to their users. Semantic descriptions for the factors might help to mitigate this problem. Achieving this automatically is, however, a non-straightforward task due to the models' statistical nature. We present an output-agreement game that represents factors by means of sample items and motivates players to create such descriptions. A user study shows that the collected output actually reflects real-world characteristics of the factors.
Backdoor Embedding in Convolutional Neural Network Models via Invisible Perturbation
Venue: arXiv cs.CR 2018
Year: 2018

Deep learning models have consistently outperformed traditional machine learning models in various classification tasks, including image classification. As such, they have become increasingly prevalent in many real world applications including those where security is of great concern. Such popularity, however, may attract attackers to exploit the vulnerabilities of the deployed deep learning models and launch attacks against security-sensitive applications. In this paper, we focus on a specific type of data poisoning attack, which we refer to as a {\em backdoor injection attack}. The main goal of the adversary performing such attack is to generate and inject a backdoor into a deep learning model that can be triggered to recognize certain embedded patterns with a target label of the attacker's choice. Additionally, a backdoor injection attack should occur in a stealthy manner, without undermining the efficacy of the victim model. Specifically, we propose two approaches for generating a backdoor that is hardly perceptible yet effective in poisoning the model. We consider two attack settings, with backdoor injection carried out either before model training or during model updating. We carry out extensive experimental evaluations under various assumptions on the adversary model, and demonstrate that such attacks can be effective and achieve a high attack success rate (above $90\%$) at a small cost of model accuracy loss (below $1\%$) with a small injection rate (around $1\%$), even under the weakest assumption wherein the adversary has no knowledge either of the original training data or the classifier model.
Large-Scale Cover Song Detection in Digital Music Libraries Using Metadata, Lyrics and Audio Features
Venue: arXiv cs.IR 2018
Year: 2018

Cover song detection is a very relevant task in Music Information Retrieval (MIR) studies and has been mainly addressed using audio-based systems. Despite its potential impact in industrial contexts, low performances and lack of scalability have prevented such systems from being adopted in practice for large applications. In this work, we investigate whether textual music information (such as metadata and lyrics) can be used along with audio for large-scale cover identification problem in a wide digital music library. We benchmark this problem using standard text and state of the art audio similarity measures. Our studies shows that these methods can significantly increase the accuracy and scalability of cover detection systems on Million Song Dataset (MSD) and Second Hand Song (SHS) datasets. By only leveraging standard tf-idf based text similarity measures on song titles and lyrics, we achieved 35.5% of absolute increase in mean average precision compared to the current scalable audio content-based state of the art methods on MSD. These experimental results suggests that new methodologies can be encouraged among researchers to leverage and identify more sophisticated NLP-based techniques to improve current cover song identification systems in digital music libraries with metadata.
A Radix-M Construction for Complementary Sets
Venue: arXiv cs.IT 2018
Year: 2018

We extend the paraunitary (PU) theory for complementary pairs to comple- mentary sets and complete complementary codes (CCC) by proposing a new PU construction. A special, but very important case of complementary sets (and CC- C), based on standard delays, is analyzed in details and a new 'Radix-M generator' (RM-G) is presented. The RM-G can be viewed as a generalization of the Boolean generator for complementary pairs. An efficient correlator for standard complemen- tary sets and CCC is also presented. Finally, examples of polyphase, QAM and hexagonal PU sets of three sequences are given.
How to Fit a Tree in a Box
Venue: arXiv cs.CG 2018
Year: 2018

We study compact straight-line embeddings of trees. We show that perfect binary trees can be embedded optimally: a tree with $n$ nodes can be drawn on a $\sqrt n$ by $\sqrt n$ grid. We also show that testing whether a given binary tree has an upward embedding with a given combinatorial embedding in a given grid is NP-hard.
Gradual Collective Upgrade of a Swarm of Autonomous Buoys for Dynamic Ocean Monitoring
Venue: arXiv cs.RO 2018
Year: 2018

Swarms of autonomous surface vehicles equipped with environmental sensors and decentralized communications bring a new wave of attractive possibilities for the monitoring of dynamic features in oceans and other waterbodies. However, a key challenge in swarm robotics design is the efficient collective operation of heterogeneous systems. We present both theoretical analysis and field experiments on the responsiveness in dynamic area coverage of a collective of 22 autonomous buoys, where 4 units are upgraded to a new design that allows them to move 80\% faster than the rest. This system is able to react on timescales of the minute to changes in areas on the order of a few thousand square meters. We have observed that this partial upgrade of the system significantly increases its average responsiveness, without necessarily improving the spatial uniformity of the deployment. These experiments show that the autonomous buoy designs and the cooperative control rule described in this work provide an efficient, flexible, and scalable solution for the pervasive and persistent monitoring of water environments.
Pole Dancing: 3D Morphs for Tree Drawings
Venue: arXiv cs.CG 2018
Year: 2018

We study the question whether a crossing-free 3D morph between two straight-line drawings of an $n$-vertex tree can be constructed consisting of a small number of linear morphing steps. We look both at the case in which the two given drawings are two-dimensional and at the one in which they are three-dimensional. In the former setting we prove that a crossing-free 3D morph always exists with $O(\log n)$ steps, while for the latter $Θ(n)$ steps are always sufficient and sometimes necessary.
Anomaly Detection in Cyber Network Data Using a Cyber Language Approach
Venue: arXiv cs.CR 2018
Year: 2018

As the amount of cyber data continues to grow, cyber network defenders are faced with increasing amounts of data they must analyze to ensure the security of their networks. In addition, new types of attacks are constantly being created and executed globally. Current rules-based approaches are effective at characterizing and flagging known attacks, but they typically fail when presented with a new attack or new types of data. By comparison, unsupervised machine learning offers distinct advantages by not requiring labeled data to learn from large amounts of network traffic. In this paper, we present a natural language-based technique (suffix trees) as applied to cyber anomaly detection. We illustrate one methodology to generate a language using cyber data features, and our experimental results illustrate positive preliminary results in applying this technique to flow-type data. As an underlying assumption to this work, we make the claim that malicious cyber actors leave observables in the data as they execute their attacks. This work seeks to identify those artifacts and exploit them to identify a wide range of cyber attacks without the need for labeled ground-truth data.
Queue Layouts of Planar 3-Trees
Venue: arXiv cs.DS 2018
Year: 2018

A queue layout of a graph G consists of a linear order of the vertices of G and a partition of the edges of G into queues, so that no two independent edges of the same queue are nested. The queue number of G is the minimum number of queues required by any queue layout of G. In this paper, we continue the study of the queue number of planar 3-trees. As opposed to general planar graphs, whose queue number is not known to be bounded by a constant, the queue number of planar 3-trees has been shown to be at most seven. In this work, we improve the upper bound to five. We also show that there exist planar 3-trees, whose queue number is at least four; this is the first example of a planar graph with queue number greater than three.
Implementing WHERE and ORDER BY as spreadsheet formulas
Venue: arXiv cs.SE 2018
Year: 2018

The WHERE and ORDER BY clauses of the SQL SELECT statement select a subset of rows in the result of a database query and present the result in the specified order. In a spreadsheet program like Microsoft Excel, one could use the filter and sort buttons, or use its Query or its Pivot Table tools to achieve a similar effect. The disadvantage of using those tools is that they don't react automatically to changes in the calculated values of the spreadsheet. In this paper, we develop spreadsheet formulas that implement SQL's WHERE and ORDER BY clauses.
A Game-Theoretic Data-Driven Approach for Pseudo-Measurement Generation in Distribution System State Estimation
Venue: arXiv cs.SY 2018
Year: 2018

In this paper, we present an efficient computational framework with the purpose of generating weighted pseudo-measurements to improve the quality of Distribution System State Estimation (DSSE) and provide observability with Advanced Metering Infrastructure (AMI) against unobservable customers and missing data. The proposed technique is based on a game-theoretic expansion of Relevance Vector Machines (RVM). This platform is able to estimate the customer power consumption data and quantify its uncertainty while reducing the prohibitive computational burden of model training for large AMI datasets. To achieve this objective, the large training set is decomposed and distributed among multiple parallel learning entities. The resulting estimations from the parallel RVMs are then combined using a game-theoretic model based on the idea of repeated games with vector payoff. It is observed that through this approach and by exploiting the seasonal changes in customers' behavior the accuracy of pseudo-measurements can be considerably improved, while introducing robustness against bad training data samples. The proposed pseudo-measurement generation model is integrated into a DSSE using a closed-loop information system, which takes advantage of a Branch Current State Estimator (BCSE) data to further improve the performance of the designed machine learning framework. This method has been tested on a practical distribution feeder model with smart meter data for verification.
Your Actions or Your Associates? Predicting Certification and Dropout in MOOCs with Behavioral and Social Features
Venue: arXiv cs.CY 2018
Year: 2018

The high level of attrition and low rate of certification in Massive Open Online Courses (MOOCs) has prompted a great deal of research. Prior researchers have focused on predicting dropout based upon behavioral features such as student confusion, click-stream patterns, and social interactions. However, few studies have focused on combining student logs with forum data. In this work, we use data from two different offerings of the same MOOC. We conduct a survival analysis to identify likely dropouts. We then examine two classes of features, social and behavioral, and apply a combination of modeling and feature-selection methods to identify the most relevant features to predict both dropout and certification. We examine the utility of three different model types and we consider the impact of different definitions of dropout on the predictors. Finally, we assess the reliability of the models over time by evaluating whether or not models from week 1 can predict dropout in week 2, and so on. The outcomes of this study will help instructors identify students likely to fail or dropout as soon as the first two weeks and provide them with more support.
A Survey on State Estimation Techniques and Challenges in Smart Distribution Systems
Venue: arXiv cs.SY 2018
Year: 2018

This paper presents a review of the literature on State Estimation (SE) in power systems. While covering some works related to SE in transmission systems, the main focus of this paper is Distribution System State Estimation (DSSE). The paper discusses a few critical topics of DSSE, including mathematical problem formulation, application of pseudo-measurements, metering instrument placement, network topology issues, impacts of renewable penetration, and cyber-security. Both conventional and modern data-driven and probabilistic techniques have been reviewed. This paper can provide researchers and utility engineers with insights into the technical achievements, barriers, and future research directions of DSSE.
Denoising Neural Machine Translation Training with Trusted Data and Online Data Selection
Venue: arXiv cs.CL 2018
Year: 2018

Measuring domain relevance of data and identifying or selecting well-fit domain data for machine translation (MT) is a well-studied topic, but denoising is not yet. Denoising is concerned with a different type of data quality and tries to reduce the negative impact of data noise on MT training, in particular, neural MT (NMT) training. This paper generalizes methods for measuring and selecting data for domain MT and applies them to denoising NMT training. The proposed approach uses trusted data and a denoising curriculum realized by online data selection. Intrinsic and extrinsic evaluations of the approach show its significant effectiveness for NMT to train on data with severe noise.
Nightmare at test time: How punctuation prevents parsers from generalizing
Venue: arXiv cs.CL 2018
Year: 2018

Punctuation is a strong indicator of syntactic structure, and parsers trained on text with punctuation often rely heavily on this signal. Punctuation is a diversion, however, since human language processing does not rely on punctuation to the same extent, and in informal texts, we therefore often leave out punctuation. We also use punctuation ungrammatically for emphatic or creative purposes, or simply by mistake. We show that (a) dependency parsers are sensitive to both absence of punctuation and to alternative uses; (b) neural parsers tend to be more sensitive than vintage parsers; (c) training neural parsers without punctuation outperforms all out-of-the-box parsers across all scenarios where punctuation departs from standard punctuation. Our main experiments are on synthetically corrupted data to study the effect of punctuation in isolation and avoid potential confounds, but we also show effects on out-of-domain data.
3D Segmentation with Exponential Logarithmic Loss for Highly Unbalanced Object Sizes
Venue: arXiv cs.CV 2018
Year: 2018

With the introduction of fully convolutional neural networks, deep learning has raised the benchmark for medical image segmentation on both speed and accuracy, and different networks have been proposed for 2D and 3D segmentation with promising results. Nevertheless, most networks only handle relatively small numbers of labels (<10), and there are very limited works on handling highly unbalanced object sizes especially in 3D segmentation. In this paper, we propose a network architecture and the corresponding loss function which improve segmentation of very small structures. By combining skip connections and deep supervision with respect to the computational feasibility of 3D segmentation, we propose a fast converging and computationally efficient network architecture for accurate segmentation. Furthermore, inspired by the concept of focal loss, we propose an exponential logarithmic loss which balances the labels not only by their relative sizes but also by their segmentation difficulties. We achieve an average Dice coefficient of 82% on brain segmentation with 20 labels, with the ratio of the smallest to largest object sizes as 0.14%. Less than 100 epochs are required to reach such accuracy, and segmenting a 128x128x128 volume only takes around 0.4 s.
Graph Energies of Egocentric Networks and Their Correlation with Vertex Centrality Measures
Venue: arXiv cs.SI 2018
Year: 2018

Graph energy is the energy of the matrix representation of the graph, where the energy of a matrix is the sum of singular values of the matrix. Depending on the definition of a matrix, one can contemplate graph energy, Randić energy, Laplacian energy, distance energy, and many others. Although theoretical properties of various graph energies have been investigated in the past in the areas of mathematics, chemistry, physics, or graph theory, these explorations have been limited to relatively small graphs representing chemical compounds or theoretical graph classes with strictly defined properties. In this paper we investigate the usefulness of the concept of graph energy in the context of large, complex networks. We show that when graph energies are applied to local egocentric networks, the values of these energies correlate strongly with vertex centrality measures. In particular, for some generative network models graph energies tend to correlate strongly with the betweenness and the eigencentrality of vertices. As the exact computation of these centrality measures is expensive and requires global processing of a network, our research opens the possibility of devising efficient algorithms for the estimation of these centrality measures based only on local information.