OpenRaiser/Intern-Atlas huggingface dataset:
Robustness and Algebraic Connectivity of Random Interdependent Networks
Venue: arXiv cs.SI 2015
Year: 2015

We investigate certain structural properties of random interdependent networks. We start by studying a property known as $r$-robustness, which is a strong indicator of the ability of a network to tolerate structural perturbations and dynamical attacks. We show that random $k$-partite graphs exhibit a threshold for $r$-robustness, and that this threshold is the same as the one for the graph to have minimum degree $r$. We then extend this characterization to random interdependent networks with arbitrary intra-layer topologies. Finally, we characterize the algebraic connectivity of such networks, and provide an asymptotically tight rate of growth of this quantity for a certain range of inter-layer edge formation probabilities. Our results arise from a characterization of the isoperimetric constant of random interdependent networks, and yield new insights into the structure and robustness properties of such networks.
Classifying Relations via Long Short Term Memory Networks along Shortest Dependency Path
Venue: arXiv cs.CL 2015
Year: 2015

Relation classification is an important research arena in the field of natural language processing (NLP). In this paper, we present SDP-LSTM, a novel neural network to classify the relation of two entities in a sentence. Our neural architecture leverages the shortest dependency path (SDP) between two entities; multichannel recurrent neural networks, with long short term memory (LSTM) units, pick up heterogeneous information along the SDP. Our proposed model has several distinct features: (1) The shortest dependency paths retain most relevant information (to relation classification), while eliminating irrelevant words in the sentence. (2) The multichannel LSTM networks allow effective information integration from heterogeneous sources over the dependency paths. (3) A customized dropout strategy regularizes the neural network to alleviate overfitting. We test our model on the SemEval 2010 relation classification task, and achieve an $F_1$-score of 83.7\%, higher than competing methods in the literature.
Cracking Intel Sandy Bridge's Cache Hash Function
Venue: arXiv cs.OH 2015
Year: 2015

On Intel Sandy Bridge processor, last level cache (LLC) is divided into cache slices and all physical addresses are distributed across the cache slices using an hash function. With this undocumented hash function existing, it is impossible to implement cache partition based on page coloring. This article cracks the hash functions on two types of Intel Sandy processors by converting the problem of cracking the hash function to the problem of classifying data blocks into different groups based on eviction relationship existing between data blocks that are mapped to the same cache set. Based on the cracking result, this article proves that it's possible to implement cache partition based on page coloring on cache indexed by hashing.
Analysis of Information Theoretic Limitation for Linear Time Invariant Feedback Systems
Venue: arXiv cs.IT 2015
Year: 2015

Information-theoretic fundamental limitation in feedback control system is an important topic for decades. In this paper, a new bode-like fundamental inequality in causal feedback control system is developed. This inequality relates directed information, mutual information and bode sensitivity functions. This inequality recovers previous known results in feedback system as special cases.
Max Point-Tolerance Graphs
Venue: arXiv cs.DM 2015
Year: 2015

A graph $G$ is a \emph{max point-tolerance (MPT)} graph if each vertex $v$ of $G$ can be mapped to a \emph{pointed-interval} $(I_v, p_v)$ where $I_v$ is an interval of $\mathbb{R}$ and $p_v \in I_v$ such that $uv$ is an edge of $G$ iff $I_u \cap I_v \supseteq \{p_u, p_v\}$. MPT graphs model relationships among DNA fragments in genome-wide association studies as well as basic transmission problems in telecommunications. We formally introduce this graph class, characterize it, study combinatorial optimization problems on it, and relate it to several well known graph classes. We characterize MPT graphs as a special case of several 2D geometric intersection graphs; namely, triangle, rectangle, L-shape, and line segment intersection graphs. We further characterize MPT as having certain linear orders on their vertex set. Our last characterization is that MPT graphs are precisely obtained by intersecting special pairs of interval graphs. We also show that, on MPT graphs, the maximum weight independent set problem can be solved in polynomial time, the coloring problem is NP-complete, and the clique cover problem has a 2-approximation. Finally, we demonstrate several connections to known graph classes; e.g., MPT graphs strictly contain interval graphs and outerplanar graphs, but are incomparable to permutation, chordal, and planar graphs.
3D-Computer Animation for a Yoruba Native Folktale
Venue: arXiv cs.GR 2015
Year: 2015

Computer graphics has wide range of applications which are implemented into computer animation, computer modeling among others. Since the invention of computer graphics researchers have not paid much of attentions toward the possibility of converting oral tales otherwise known as folktales into possible cartoon animated videos. This paper is based on how to develop cartoons of local folktales that will be of huge benefits to Nigerians. The activities were divided into 5 stages; analysis, design, development, implementation and evaluation which involved various processes and use of various specialized software and hardware. After the implementation of this project, the video characteristics were evaluated using likert scale. Analysis of 30 user responses indicated that 17 users (56.7 percent) rated the image quality as excellent, the video and image synchronization was rated as excellent by 9 users (30 percent), the Background noise was rated excellent by 18 users (60 percent), the Character Impression was rated Excellent by 11 users (36.67 percent), the general assessment of the storyline was rated excellent by 17 users (56.7 percent), the video Impression was rated excellent by 11 users (36.67 percent) and the voice quality was rated by 10 users (33.33 percent) as excellent.
Two-stage Cascaded Classifier for Purchase Prediction
Venue: arXiv cs.IR 2015
Year: 2015

In this paper we describe our machine learning solution for the RecSys Challenge, 2015. We have proposed a time efficient two-stage cascaded classifier for the prediction of buy sessions and purchased items within such sessions. Based on the model, several interesting features found, and formation of our own test bed, we have achieved a reasonable score. Usage of Random Forests helps us to cope with the effect of the multiplicity of good models depending on varying subsets of features in the purchased items prediction and, in its turn, boosting is used as a suitable technique to overcome severe class imbalance of the buy-session prediction.
Cooperative Data Exchange with Unreliable Clients
Venue: arXiv cs.IT 2015
Year: 2015

Consider a set of clients in a broadcast network, each of which holds a subset of packets in the ground set X. In the (coded) cooperative data exchange problem, the clients need to recover all packets in X by exchanging coded packets over a lossless broadcast channel. Several previous works analyzed this problem under the assumption that each client initially holds a random subset of packets in X. In this paper we consider a generalization of this problem for settings in which an unknown (but of a certain size) subset of clients are unreliable and their packet transmissions are subject to arbitrary erasures. For the special case of one unreliable client, we derive a closed-form expression for the minimum number of transmissions required for each reliable client to obtain all packets held by other reliable clients (with probability approaching 1 as the number of packets tends to infinity). Furthermore, for the cases with more than one unreliable client, we provide an approximation solution in which the number of transmissions per packet is within an arbitrarily small additive factor from the value of the optimal solution.
Knuthian Drawings of Series-Parallel Flowcharts
Venue: arXiv cs.CG 2015
Year: 2015

Inspired by a classic paper by Knuth, we revisit the problem of drawing flowcharts of loop-free algorithms, that is, degree-three series-parallel digraphs. Our drawing algorithms show that it is possible to produce Knuthian drawings of degree-three series-parallel digraphs with good aspect ratios and small numbers of edge bends.
Joint Source-Channel Coding for Broadcast Channel with Cooperating Receivers
Venue: arXiv cs.IT 2015
Year: 2015

It is known that, as opposed to point-to-point channel, separate source and channel coding is not optimal in general for sending correlated sources over multiuser channels. In some works joint source-channel coding has been investigated for some certain multiuser channels; i.g., multiple access channel (MAC) and broadcast channel (BC). In this paper, we obtain a sufficient condition for transmitting arbitrarily correlated sources over a discrete memoryless BC with cooperating receivers, where the receivers are allowed to exchange messages via a pair of noisy cooperative links. It is seen that our results is a general form of previous ones and includes them as its special cases.
Supporting Developers in Porting Software via Combined Textual and Structural Analysis of Software Artifacts
Venue: arXiv cs.SE 2015
Year: 2015

This is position paper accepted to the Computational Science & Engineering Software Sustainability and Productivity Challenges (CSESSP Challenges) Workshop, sponsored by the Networking and Information Technology Research and Development (NITRD) Software Design and Productivity (SDP) Coordinating Group, held October 15th-16th 2015 in Washington DC, USA. It discusses the role recommendation systems, based on textual and structural information in source code, and further enhanced by mining related applications, can have in improving the portability of scientific and engineering software.
A Complete Derivation Of The Association Log-Likelihood Distance For Multi-Object Tracking
Venue: arXiv cs.SY 2015
Year: 2015

The Mahalanobis distance is commonly used in multi-object trackers for measurement-to-track association. Starting with the original definition of the Mahalanobis distance we review its use in association. Given that there is no principle in multi-object tracking that sets the Mahalanobis distance apart as a distinguished statistical distance we revisit the global association hypotheses of multiple hypothesis tracking as the most general association setting. Those association hypotheses induce a distance-like quantity for assignment which we refer to as association log-likelihood distance. We compare the ability of the Mahalanobis distance to the association log-likelihood distance to yield correct association relations in Monte-Carlo simulations. It turns out that on average the distance based on association log-likelihood performs better than the Mahalanobis distance, confirming that the maximization of global association hypotheses is a more fundamental approach to association than the minimization of a certain statistical distance measure.
Contextually proximate approach to develop smart user interface
Venue: arXiv cs.HC 2015
Year: 2015

Researchers and experts are taking efforts in delivering an optimal user experience from a long time. Computer interfaces are being developed to keep user 'in the flow' as well as for making users more connected to the real world wile using virtual environment. Developing ubiquitous user interfaces for novices and experts at the same time is crucial work for interaction designers. This paper molds the designing approach of user interfaces in bit different parameters by reviewing the existing literature and proposing a different way to develop a smart user interface to make user more familiar with the design and to keep user 'in the flow'. Contextually proximate approach (CPA) will help users to minimize their feeling of insecurity as designing process includes local resources of users to develop the user interfaces. These various resources and parameters are explained further in the paper by giving different examples.
Style in the Age of Instagram: Predicting Success within the Fashion Industry using Social Media
Venue: arXiv cs.CY 2015
Year: 2015

Fashion is a multi-billion dollar industry with social and economic implications worldwide. To gain popularity, brands want to be represented by the top popular models. As new faces are selected using stringent (and often criticized) aesthetic criteria, \emph{a priori} predictions are made difficult by information cascades and other fundamental trend-setting mechanisms. However, the increasing usage of social media within and without the industry may be affecting this traditional system. We therefore seek to understand the ingredients of success of fashion models in the age of Instagram. Combining data from a comprehensive online fashion database and the popular mobile image-sharing platform, we apply a machine learning framework to predict the tenure of a cohort of new faces for the 2015 Spring\,/\,Summer season throughout the subsequent 2015-16 Fall\,/\,Winter season. Our framework successfully predicts most of the new popular models who appeared in 2015. In particular, we find that a strong social media presence may be more important than being under contract with a top agency, or than the aesthetic standards sought after by the industry.
Supervised learning of sparse context reconstruction coefficients for data representation and classification
Venue: arXiv cs.LG 2015
Year: 2015

Context of data points, which is usually defined as the other data points in a data set, has been found to play important roles in data representation and classification. In this paper, we study the problem of using context of a data point for its classification problem. Our work is inspired by the observation that actually only very few data points are critical in the context of a data point for its representation and classification. We propose to represent a data point as the sparse linear combination of its context, and learn the sparse context in a supervised way to increase its discriminative ability. To this end, we proposed a novel formulation for context learning, by modeling the learning of context parameter and classifier in a unified objective, and optimizing it with an alternative strategy in an iterative algorithm. Experiments on three benchmark data set show its advantage over state-of-the-art context-based data representation and classification methods.
Image tag completion by local learning
Venue: arXiv cs.CV 2015
Year: 2015

The problem of tag completion is to learn the missing tags of an image. In this paper, we propose to learn a tag scoring vector for each image by local linear learning. A local linear function is used in the neighborhood of each image to predict the tag scoring vectors of its neighboring images. We construct a unified objective function for the learning of both tag scoring vectors and local linear function parame- ters. In the objective, we impose the learned tag scoring vectors to be consistent with the known associations to the tags of each image, and also minimize the prediction error of each local linear function, while reducing the complexity of each local function. The objective function is optimized by an alternate optimization strategy and gradient descent methods in an iterative algorithm. We compare the proposed algorithm against different state-of-the-art tag completion methods, and the results show its advantages.
Compact Routing Messages in Self-Healing Trees
Venue: arXiv cs.DC 2015
Year: 2015

Existing compact routing schemes, e.g., Thorup and Zwick [SPAA 2001] and Chechik [PODC 2013], often have no means to tolerate failures, once the system has been setup and started. This paper presents, to our knowledge, the first self-healing compact routing scheme. Besides, our schemes are developed for low memory nodes, i.e., nodes need only $O(\log^2 n)$ memory, and are thus, compact schemes. We introduce two algorithms of independent interest: The first is CompactFT, a novel compact version (using only $O(\log n)$ local memory) of the self-healing algorithm Forgiving Tree of Hayes et al. [PODC 2008]. The second algorithm (CompactFTZ) combines CompactFT with Thorup-Zwick's tree-based compact routing scheme [SPAA 2001] to produce a fully compact self-healing routing scheme. In the self-healing model, the adversary deletes nodes one at a time with the affected nodes self-healing locally by adding few edges. CompactFT recovers from each attack in only $O(1)$ time and $Δ$ messages, with only +3 degree increase and $O(log Δ)$ graph diameter increase, over any sequence of deletions ($Δ$ is the initial maximum degree). Additionally, CompactFTZ guarantees delivery of a packet sent from sender s as long as the receiver t has not been deleted, with only an additional $O(y \log Δ)$ latency, where $y$ is the number of nodes that have been deleted on the path between $s$ and $t$. If $t$ has been deleted, $s$ gets informed and the packet removed from the network.
Preprint ARPPS Augmented Reality Pipeline Prospect System
Venue: arXiv cs.CV 2015
Year: 2015

This is the preprint version of our paper on ICONIP. Outdoor augmented reality geographic information system (ARGIS) is the hot application of augmented reality over recent years. This paper concludes the key solutions of ARGIS, designs the mobile augmented reality pipeline prospect system (ARPPS), and respectively realizes the machine vision based pipeline prospect system (MVBPPS) and the sensor based pipeline prospect system (SBPPS). With the MVBPPS's realization, this paper studies the neural network based 3D features matching method.
Probabilistic Modelling of Morphologically Rich Languages
Venue: arXiv cs.CL 2015
Year: 2015

This thesis investigates how the sub-structure of words can be accounted for in probabilistic models of language. Such models play an important role in natural language processing tasks such as translation or speech recognition, but often rely on the simplistic assumption that words are opaque symbols. This assumption does not fit morphologically complex language well, where words can have rich internal structure and sub-word elements are shared across distinct word forms. Our approach is to encode basic notions of morphology into the assumptions of three different types of language models, with the intention that leveraging shared sub-word structure can improve model performance and help overcome data sparsity that arises from morphological processes. In the context of n-gram language modelling, we formulate a new Bayesian model that relies on the decomposition of compound words to attain better smoothing, and we develop a new distributed language model that learns vector representations of morphemes and leverages them to link together morphologically related words. In both cases, we show that accounting for word sub-structure improves the models' intrinsic performance and provides benefits when applied to other tasks, including machine translation. We then shift the focus beyond the modelling of word sequences and consider models that automatically learn what the sub-word elements of a given language are, given an unannotated list of words. We formulate a novel model that can learn discontiguous morphemes in addition to the more conventional contiguous morphemes that most previous models are limited to. This approach is demonstrated on Semitic languages, and we find that modelling discontiguous sub-word structures leads to improvements in the task of segmenting words into their contiguous morphemes.
SFX Miscellaneous Free Ejournals Target: Usage Survey among the SFX Community
Venue: arXiv cs.DL 2015
Year: 2015

The number of free or open access articles is increasing rapidly, and their retrieval with library indexes and OpenURL link resolvers has been a challenge. In June 2014, the SFX MISCELLANEOUS FREE EJOURNALS target contained more than 24,000 portfolios of all kinds. The SFX Knowledge Base Advisory Board (KBAB) carried out an international survey to get an overview of the usage of this target by the SFX community and to precisely identify what could be done to improve it. The target is widely used among the community. However, many respondents complained about three major problems: (a) incorrect links, (b) full texts actually not free, and (c) incorrect or missing thresholds (years and volumes information).
A Fast and Efficient Algorithm for Reconstructing MR images From Partial Fourier Samples
Venue: arXiv cs.IT 2015
Year: 2015

In this paper, the problem of Magnetic Resonance (MR) image reconstruction from partial Fourier samples has been considered. To this aim, we leverage the evidence that MR images are sparser than their zero-filled reconstructed ones from incomplete Fourier samples. This information can be used to define an optimization problem which searches for the sparsest possible image conforming with the available Fourier samples. We solve the resulting problem using the well-known Alternating Direction Method of Multipliers (ADMM). Unlike most existing methods that work with small over-lapping image patches, the proposed algorithm considers the whole image without dividing it into small blocks. Experimental results prominently confirm its promising performance and advantages over the existing methods.
Synthesizing and tuning chemical reaction networks with specified behaviours
Venue: arXiv cs.ET 2015
Year: 2015

We consider how to generate chemical reaction networks (CRNs) from functional specifications. We propose a two-stage approach that combines synthesis by satisfiability modulo theories and Markov chain Monte Carlo based optimisation. First, we identify candidate CRNs that have the possibility to produce correct computations for a given finite set of inputs. We then optimise the reaction rates of each CRN using a combination of stochastic search techniques applied to the chemical master equation, simultaneously improving the of correct behaviour and ruling out spurious solutions. In addition, we use techniques from continuous time Markov chain theory to study the expected termination time for each CRN. We illustrate our approach by identifying CRNs for majority decision-making and division computation, which includes the identification of both known and unknown networks.
Robust Subspace Clustering via Smoothed Rank Approximation
Venue: arXiv cs.CV 2015
Year: 2015

Matrix rank minimizing subject to affine constraints arises in many application areas, ranging from signal processing to machine learning. Nuclear norm is a convex relaxation for this problem which can recover the rank exactly under some restricted and theoretically interesting conditions. However, for many real-world applications, nuclear norm approximation to the rank function can only produce a result far from the optimum. To seek a solution of higher accuracy than the nuclear norm, in this paper, we propose a rank approximation based on Logarithm-Determinant. We consider using this rank approximation for subspace clustering application. Our framework can model different kinds of errors and noise. Effective optimization strategy is developed with theoretical guarantee to converge to a stationary point. The proposed method gives promising results on face clustering and motion segmentation tasks compared to the state-of-the-art subspace clustering algorithms.