OpenRaiser/Intern-Atlas huggingface dataset:
BreakingNews: Article Annotation by Image and Text Processing
Venue: arXiv cs.CV 2016
Year: 2016

Building upon recent Deep Neural Network architectures, current approaches lying in the intersection of computer vision and natural language processing have achieved unprecedented breakthroughs in tasks like automatic captioning or image retrieval. Most of these learning methods, though, rely on large training sets of images associated with human annotations that specifically describe the visual content. In this paper we propose to go a step further and explore the more complex cases where textual descriptions are loosely related to the images. We focus on the particular domain of News articles in which the textual content often expresses connotative and ambiguous relations that are only suggested but not directly inferred from images. We introduce new deep learning methods that address source detection, popularity prediction, article illustration and geolocation of articles. An adaptive CNN architecture is proposed, that shares most of the structure for all the tasks, and is suitable for multitask and transfer learning. Deep Canonical Correlation Analysis is deployed for article illustration, and a new loss function based on Great Circle Distance is proposed for geolocation. Furthermore, we present BreakingNews, a novel dataset with approximately 100K news articles including images, text and captions, and enriched with heterogeneous meta-data (such as GPS coordinates and popularity metrics). We show this dataset to be appropriate to explore all aforementioned problems, for which we provide a baseline performance using various Deep Learning architectures, and different representations of the textual and visual features. We report very promising results and bring to light several limitations of current state-of-the-art in this kind of domain, which we hope will help spur progress in the field.
The trace monoids in the queue monoid and in the direct product of two free monoids
Venue: arXiv cs.FL 2016
Year: 2016

We prove that a trace monoid embeds into the queue monoid if and only if it embeds into the direct product of two free monoids. We also give a decidable characterization of these trace monoids.
Sequential Mechanisms with ex-post Participation Guarantees
Venue: arXiv cs.GT 2016
Year: 2016

We provide a characterization of revenue-optimal dynamic mechanisms in settings where a monopolist sells k items over k periods to a buyer who realizes his value for item i in the beginning of period i. We require that the mechanism satisfies a strong individual rationality constraint, requiring that the stage utility of each agent be positive during each period. We show that the optimum mechanism can be computed by solving a nested sequence of static (single-period) mechanisms that optimize a tradeoff between the surplus of the allocation and the buyer's utility. We also provide a simple dynamic mechanism that obtains at least half of the optimal revenue. The mechanism either ignores history and posts the optimal monopoly price in each period, or allocates with a probability that is independent of the current report of the agent and is based only on previous reports. Our characterization extends to multi-agent auctions. We also formulate a discounted infinite horizon version of the problem, where we study the performance of "Markov mechanisms."
Heredity for generalized power domination
Venue: arXiv cs.DM 2016
Year: 2016

In this paper, we study the behaviour of the generalized power domination number of a graph by small changes on the graph, namely edge and vertex deletion and edge contraction. We prove optimal bounds for $γ\_{p,k}(G-e)$, $γ\_{p,k}(G/e)$ and for $γ\_{p,k}(G-v)$ in terms of $γ\_{p,k}(G)$, and give examples for which these bounds are tight. We characterize all graphs for which $γ\_{p,k}(G-e) = γ\_{p,k}(G)+1$ for any edge $e$. We also consider the behaviour of the propagation radius of graphs by similar modifications.
On the Theory and Practice of Privacy-Preserving Bayesian Data Analysis
Venue: arXiv cs.LG 2016
Year: 2016

Bayesian inference has great promise for the privacy-preserving analysis of sensitive data, as posterior sampling automatically preserves differential privacy, an algorithmic notion of data privacy, under certain conditions (Dimitrakakis et al., 2014; Wang et al., 2015). While this one posterior sample (OPS) approach elegantly provides privacy "for free," it is data inefficient in the sense of asymptotic relative efficiency (ARE). We show that a simple alternative based on the Laplace mechanism, the workhorse of differential privacy, is as asymptotically efficient as non-private posterior inference, under general assumptions. This technique also has practical advantages including efficient use of the privacy budget for MCMC. We demonstrate the practicality of our approach on a time-series analysis of sensitive military records from the Afghanistan and Iraq wars disclosed by the Wikileaks organization.
Attentive Contexts for Object Detection
Venue: arXiv cs.CV 2016
Year: 2016

Modern deep neural network based object detection methods typically classify candidate proposals using their interior features. However, global and local surrounding contexts that are believed to be valuable for object detection are not fully exploited by existing methods yet. In this work, we take a step towards understanding what is a robust practice to extract and utilize contextual information to facilitate object detection in practice. Specifically, we consider the following two questions: "how to identify useful global contextual information for detecting a certain object?" and "how to exploit local context surrounding a proposal for better inferring its contents?". We provide preliminary answers to these questions through developing a novel Attention to Context Convolution Neural Network (AC-CNN) based object detection model. AC-CNN effectively incorporates global and local contextual information into the region-based CNN (e.g. Fast RCNN) detection model and provides better object detection performance. It consists of one attention-based global contextualized (AGC) sub-network and one multi-scale local contextualized (MLC) sub-network. To capture global context, the AGC sub-network recurrently generates an attention map for an input image to highlight useful global contextual locations, through multiple stacked Long Short-Term Memory (LSTM) layers. For capturing surrounding local context, the MLC sub-network exploits both the inside and outside contextual information of each specific proposal at multiple scales. The global and local context are then fused together for making the final decision for detection. Extensive experiments on PASCAL VOC 2007 and VOC 2012 well demonstrate the superiority of the proposed AC-CNN over well-established baselines. In particular, AC-CNN outperforms the popular Fast-RCNN by 2.0% and 2.2% on VOC 2007 and VOC 2012 in terms of mAP, respectively.
Predicting Cyber Attack Rates with Extreme Values
Venue: arXiv cs.CR 2016
Year: 2016

It is important to understand to what extent, and in what perspectives, cyber attacks can be predicted. Despite its evident importance, this problem was not investigated until very recently, when we proposed using the innovative methodology of {\em gray-box prediction}. This methodology advocates the use of gray-box models, which accommodate the statistical properties/phenomena exhibited by the data. Specifically, we showed that gray-box models that accommodate the Long-Range Dependence (LRD) phenomenon can predict the attack rate (i.e., the number of attacks per unit time) 1-hour ahead-of-time with an accuracy of 70.2-82.1\%. To the best of our knowledge, this is the first result showing the feasibility of prediction in this domain. We observe that the prediction errors are partly caused by the models' incapability in predicting the large attack rates, which are called {\em extreme values} in statistics. This motivates us to analyze the {\em extreme-value phenomenon}, by using two complementary approaches: the Extreme Value Theory (EVT) and the Time Series Theory (TST). In this paper, we show that EVT can offer long-term predictions (e.g., 24-hour ahead-of-time), while gray-box TST models can predict attack rates 1-hour ahead-of-time with an accuracy of 86.0-87.9\%. We explore connections between the two approaches, and point out future research directions. Although our prediction study is based on specific cyber attack data, our methodology can be equally applied to analyze any cyber attack data of its kind.
Time Is of the Essence: Analyzing the Effect of Vertex-Joining Time on Complex Network Evolution
Venue: arXiv cs.SI 2016
Year: 2016

Complex networks have non-trivial characteristics and appear in many real-world systems. Such networks are vitally important, but their full underlying dynamics are not completely understood. Utilizing new data sources, however, can unveil the evolution process of these networks. This study uses the recently published Reddit dataset, containing over 1.65 billion comments, to construct the largest publicly available social network corpus to date. We used this dataset to deeply examine the network evolution process, which resulted in two key observations: First, links are more likely to be created among users who join a network at a similar time. Second, the rate in which new users join a network is a central factor in molding a network's topology; i.e., different user-join patterns create different topological properties. Based on these observations, we developed the \textit{Temporal Preferential Attachment} random network generation model. This model produces not only scale-free networks that have relative high clustering coefficients, but also networks that are sensitive to both the rate and the time in which users join the network. This results in a more accurate and flexible model of how complex networks evolve, one which more closely represents real-world data.
A Classical Realizability Model for a Semantical Value Restriction
Venue: arXiv cs.LO 2016
Year: 2016

We present a new type system with support for proofs of programs in a call-by-value language with control operators. The proof mechanism relies on observational equivalence of (untyped) programs. It appears in two type constructors, which are used for specifying program properties and for encoding dependent products. The main challenge arises from the lack of expressiveness of dependent products due to the value restriction. To circumvent this limitation we relax the syntactic restriction and only require equivalence to a value. The consistency of the system is obtained semantically by constructing a classical realizability model in three layers (values, stacks and terms).
Web Data Knowledge Extraction
Venue: arXiv cs.DB 2016
Year: 2016

A constantly growing amount of information is available through the web. Unfortunately, extracting useful content from this massive amount of data still remains an open issue. The lack of standard data models and structures forces developers to create adhoc solutions from the scratch. The figure of the expert is still needed in many situations where developers do not have the correct background knowledge. This forces developers to spend time acquiring the needed background from the expert. In other directions, there are promising solutions employing machine learning techniques. However, increasing accuracy requires an increase in system complexity that cannot be endured in many projects. In this work, we approach the web knowledge extraction problem using an expertcentric methodology. This methodology defines a set of configurable, extendible and independent components that permit the reutilisation of large pieces of code among projects. Our methodology differs from similar solutions in its expert-driven design. This design, makes it possible for subject-matter expert to drive the knowledge extraction for a given set of documents. Additionally, we propose the utilization of machine assisted solutions that guide the expert during this process. To demonstrate the capabilities of our methodology, we present a real use case scenario in which public procurement data is extracted from the web-based repositories of several public institutions across Europe. We provide insightful details about the challenges we had to deal with in this use case and additional discussions about how to apply our methodology.
Semantic Properties of Customer Sentiment in Tweets
Venue: arXiv cs.CL 2016
Year: 2016

An increasing number of people are using online social networking services (SNSs), and a significant amount of information related to experiences in consumption is shared in this new media form. Text mining is an emerging technique for mining useful information from the web. We aim at discovering in particular tweets semantic patterns in consumers' discussions on social media. Specifically, the purposes of this study are twofold: 1) finding similarity and dissimilarity between two sets of textual documents that include consumers' sentiment polarities, two forms of positive vs. negative opinions and 2) driving actual content from the textual data that has a semantic trend. The considered tweets include consumers opinions on US retail companies (e.g., Amazon, Walmart). Cosine similarity and K-means clustering methods are used to achieve the former goal, and Latent Dirichlet Allocation (LDA), a popular topic modeling algorithm, is used for the latter purpose. This is the first study which discover semantic properties of textual data in consumption context beyond sentiment analysis. In addition to major findings, we apply LDA (Latent Dirichlet Allocations) to the same data and drew latent topics that represent consumers' positive opinions and negative opinions on social media.
Part-of-Speech Relevance Weights for Learning Word Embeddings
Venue: arXiv cs.CL 2016
Year: 2016

This paper proposes a model to learn word embeddings with weighted contexts based on part-of-speech (POS) relevance weights. POS is a fundamental element in natural language. However, state-of-the-art word embedding models fail to consider it. This paper proposes to use position-dependent POS relevance weighting matrices to model the inherent syntactic relationship among words within a context window. We utilize the POS relevance weights to model each word-context pairs during the word embedding training process. The model proposed in this paper paper jointly optimizes word vectors and the POS relevance matrices. Experiments conducted on popular word analogy and word similarity tasks all demonstrated the effectiveness of the proposed method.
Early Detection of Combustion Instabilities using Deep Convolutional Selective Autoencoders on Hi-speed Flame Video
Venue: arXiv cs.CV 2016
Year: 2016

This paper proposes an end-to-end convolutional selective autoencoder approach for early detection of combustion instabilities using rapidly arriving flame image frames. The instabilities arising in combustion processes cause significant deterioration and safety issues in various human-engineered systems such as land and air based gas turbine engines. These properties are described as self-sustaining, large amplitude pressure oscillations and show varying spatial scales periodic coherent vortex structure shedding. However, such instability is extremely difficult to detect before a combustion process becomes completely unstable due to its sudden (bifurcation-type) nature. In this context, an autoencoder is trained to selectively mask stable flame and allow unstable flame image frames. In that process, the model learns to identify and extract rich descriptive and explanatory flame shape features. With such a training scheme, the selective autoencoder is shown to be able to detect subtle instability features as a combustion process makes transition from stable to unstable region. As a consequence, the deep learning tool-chain can perform as an early detection framework for combustion instabilities that will have a transformative impact on the safety and performance of modern engines.
Hybridization of Expectation-Maximization and K-Means Algorithms for Better Clustering Performance
Venue: arXiv cs.LG 2016
Year: 2016

The present work proposes hybridization of Expectation-Maximization (EM) and K-Means techniques as an attempt to speed-up the clustering process. Though both K-Means and EM techniques look into different areas, K-means can be viewed as an approximate way to obtain maximum likelihood estimates for the means. Along with the proposed algorithm for hybridization, the present work also experiments with the Standard EM algorithm. Six different datasets are used for the experiments of which three are synthetic datasets. Clustering fitness and Sum of Squared Errors (SSE) are computed for measuring the clustering performance. In all the experiments it is observed that the proposed algorithm for hybridization of EM and K-Means techniques is consistently taking less execution time with acceptable Clustering Fitness value and less SSE than the standard EM algorithm. It is also observed that the proposed algorithm is producing better clustering results than the Cluster package of Purdue University.
Monotone 3-Sat-4 is NP-complete
Venue: arXiv cs.CC 2016
Year: 2016

Monotone 3-Sat-4 is a variant of the satisfiability problem for boolean formulae in conjunctive normal form. In this variant, each clause contains exactly three literals---either all or none of them are positive, i.e., no clause contains both a positive and a negative literal---and every variable appears at most four times in the formula. Moreover, every clause consists of three distinct literals. We show that Monotone 3-Sat-4 is NP-complete.
Quote RTs on Twitter: Usage of the New Feature for Political Discourse
Venue: arXiv cs.SI 2016
Year: 2016

Social media platforms provide several social interactional features. Due to the large scale reach of social media, these interactional features help enable various types of political discourse. Constructive and diversified discourse is important for sustaining healthy communities and reducing the impact of echo chambers. In this paper, we empirically examine the role of a newly introduced Twitter feature, 'quote retweets' (or 'quote RTs') in political discourse, specifically whether it has led to improved, civil, and balanced exchange. Quote RTs allow users to quote the tweet they retweet, while adding a short comment. Our analysis using content, network and crowd labeled data indicates that the feature has increased political discourse and its diffusion, compared to existing features. We discuss the implications of our findings in understanding and reducing online polarization.
ASIC-based Implementation of Synchronous Section-Carry Based Carry Lookahead Adders
Venue: arXiv cs.AR 2016
Year: 2016

The section-carry based carry lookahead adder (SCBCLA) topology was proposed as an improved high-speed alternative to the conventional carry lookahead adder (CCLA) topology in previous works. Self-timed and FPGA-based implementations of SCBCLAs and CCLAs were considered earlier, and it was found that SCBCLAs could help in delay reduction i.e. pave the way for improved speed compared to CCLAs at the expense of some increase in area and/or power parameters. In this work, we consider semi-custom ASIC-based implementations of different variants of SCBCLAs and CCLAs to perform 32-bit dual-operand addition. Based on the simulation results for 32-bit dual-operand addition obtained by targeting a high-end 32/28nm CMOS process, it is found that an optimized SCBCLA architecture reports a 9.8% improvement in figure-of-merit (FOM) compared to an optimized CCLA architecture, where the FOM is defined as the inverse of the product of power, delay, and area. It is generally inferred from the simulations that the SCBCLA architecture could be more beneficial compared to the CCLA architecture in terms of the design metrics whilst benefitting a variety of computer arithmetic operations involving dual-operand and/or multi-operand additions. Also, it is observed that heterogeneous CLA architectures tend to fare well compared to homogeneous CLA architectures, as substantiated by the simulation results.
Unsupervised Category Discovery via Looped Deep Pseudo-Task Optimization Using a Large Scale Radiology Image Database
Venue: arXiv cs.CV 2016
Year: 2016

Obtaining semantic labels on a large scale radiology image database (215,786 key images from 61,845 unique patients) is a prerequisite yet bottleneck to train highly effective deep convolutional neural network (CNN) models for image recognition. Nevertheless, conventional methods for collecting image labels (e.g., Google search followed by crowd-sourcing) are not applicable due to the formidable difficulties of medical annotation tasks for those who are not clinically trained. This type of image labeling task remains non-trivial even for radiologists due to uncertainty and possible drastic inter-observer variation or inconsistency. In this paper, we present a looped deep pseudo-task optimization procedure for automatic category discovery of visually coherent and clinically semantic (concept) clusters. Our system can be initialized by domain-specific (CNN trained on radiology images and text report derived labels) or generic (ImageNet based) CNN models. Afterwards, a sequence of pseudo-tasks are exploited by the looped deep image feature clustering (to refine image labels) and deep CNN training/classification using new labels (to obtain more task representative deep features). Our method is conceptually simple and based on the hypothesized "convergence" of better labels leading to better trained CNN models which in turn feed more effective deep image features to facilitate more meaningful clustering/labels. We have empirically validated the convergence and demonstrated promising quantitative and qualitative results. Category labels of significantly higher quality than those in previous work are discovered. This allows for further investigation of the hierarchical semantic nature of the given large-scale radiology image database.
On Determining the Fair Bandwidth Share for ABR Connections in ATM Networks
Venue: arXiv cs.NI 2016
Year: 2016

In a multi-service network such as ATM, adaptive data services(such as ABR) share the bandwidth unused by higher priority services. The network indicates to the ABR sources the fair and efficient rates at which they should transmit to minimize their cell loss. In this paper, we propose a new method for determining the "effective" number of active connections, and the fair bandwidth share for each connection.
Classifying Syntactic Regularities for Hundreds of Languages
Venue: arXiv cs.CL 2016
Year: 2016

This paper presents a comparison of classification methods for linguistic typology for the purpose of expanding an extensive, but sparse language resource: the World Atlas of Language Structures (WALS) (Dryer and Haspelmath, 2013). We experimented with a variety of regression and nearest-neighbor methods for use in classification over a set of 325 languages and six syntactic rules drawn from WALS. To classify each rule, we consider the typological features of the other five rules; linguistic features extracted from a word-aligned Bible in each language; and genealogical features (genus and family) of each language. In general, we find that propagating the majority label among all languages of the same genus achieves the best accuracy in label pre- diction. Following this, a logistic regression model that combines typological and linguistic features offers the next best performance. Interestingly, this model actually outperforms the majority labels among all languages of the same family.