OpenRaiser/Intern-Atlas huggingface dataset:
Abstract Learning via Demodulation in a Deep Neural Network
Venue: arXiv cs.LG 2015
Year: 2015

Inspired by the brain, deep neural networks (DNN) are thought to learn abstract representations through their hierarchical architecture. However, at present, how this happens is not well understood. Here, we demonstrate that DNN learn abstract representations by a process of demodulation. We introduce a biased sigmoid activation function and use it to show that DNN learn and perform better when optimized for demodulation. Our findings constitute the first unambiguous evidence that DNN perform abstract learning in practical use. Our findings may also explain abstract learning in the human brain.
A Distributional Representation Model For Collaborative Filtering
Venue: arXiv cs.IR 2015
Year: 2015

In this paper, we propose a very concise deep learning approach for collaborative filtering that jointly models distributional representation for users and items. The proposed framework obtains better performance when compared against current state-of-art algorithms and that made the distributional representation model a promising direction for further research in the collaborative filtering.
Probabilistic Models for High-Order Projective Dependency Parsing
Venue: arXiv cs.CL 2015
Year: 2015

This paper presents generalized probabilistic models for high-order projective dependency parsing and an algorithmic framework for learning these statistical models involving dependency trees. Partition functions and marginals for high-order dependency trees can be computed efficiently, by adapting our algorithms which extend the inside-outside algorithm to higher-order cases. To show the effectiveness of our algorithms, we perform experiments on three languages---English, Chinese and Czech, using maximum conditional likelihood estimation for model training and L-BFGS for parameter estimation. Our methods achieve competitive performance for English, and outperform all previously reported dependency parsers for Chinese and Czech.
Spectrum Allocation for Multi-Operator Device-to-Device Communication
Venue: arXiv cs.NI 2015
Year: 2015

In order to harvest the business potential of device-to-device (D2D) communication, direct communication between devices subscribed to different mobile operators should be supported. This would also support meeting requirements resulting from D2D relevant scenarios, like vehicle-to-vehicle communication. In this paper, we propose to allocate the multi-operator D2D communication over dedicated cellular spectral resources contributed from both operators. Ideally, the operators should negotiate about the amount of spectrum to contribute, without revealing proprietary information to each other and/or to other parties. One possible way to do that is to use the sequence of operators' best responses, i.e., the operators make offers about the amount of spectrum to contribute using a sequential updating procedure until reaching consensus. Besides spectrum allocation, we need a mode selection scheme for the multi-operator D2D users. We use a stochastic geometry framework to capture the impact of mode selection on the distribution of D2D users and assess the performance of the best response iteration algorithm. With the performance metrics considered in the paper, we show that the best response iteration has a unique Nash equilibrium that can be reached from any initial strategy. In general, asymmetric operators would contribute unequal amounts of spectrum for multi-operator D2D communication. Provided that the multi-operator D2D density is not negligible, we show that both operators may experience significant performance gains as compared to the scheme without spectrum sharing.
Gray-Level Image Transitions Driven by Tsallis Entropic Index
Venue: arXiv cs.CV 2015
Year: 2015

The maximum entropy principle is largely used in thresholding and segmentation of images. Among the several formulations of this principle, the most effectively applied is that based on Tsallis non-extensive entropy. Here, we discuss the role of its entropic index in determining the thresholds. When this index is spanning the interval (0,1), for some images, the values of thresholds can have large leaps. In this manner, we observe abrupt transitions in the appearance of corresponding bi-level or multi-level images. These gray-level image transitions are analogous to order or texture transitions observed in physical systems, transitions which are driven by the temperature or by other physical quantities.
Impacts of Bad Data on the PMU based Line Outage Detection
Venue: arXiv cs.CR 2015
Year: 2015

Power systems become more prone to cyber-attacks due to the high integration of information technologies. In this paper, we demonstrate that the outages of some lines can be masked by injecting false data into a set of measurements. The success of the topology attack can be guaranteed by making that: 1)the injected false data obeys KCL and KVL to avoid being detected by the bad data detection program in the state estimation; 2)the residual is increased such that the line outage cannot be detected by PMU data. A quadratic programming problem is set up to determine the optimal attack vector that can maximize the residual of the outaged line. The IEEE 39-bus system is used to demonstrate the masking scheme.
Geometric Spanning Cycles in Bichromatic Point Sets
Venue: arXiv cs.CG 2015
Year: 2015

Given a set of points in the plane each colored either red or blue, we find non-self-intersecting geometric spanning cycles of the red points and of the blue points such that each edge of the red spanning cycle is crossed at most three times by the blue spanning cycle and vice-versa.
Lattices with non-Shannon Inequalities
Venue: arXiv cs.IT 2015
Year: 2015

We study the existence or absence of non-Shannon inequalities for variables that are related by functional dependencies. Although the power-set on four variables is the smallest Boolean lattice with non-Shannon inequalities there exist lattices with many more variables without non-Shannon inequalities. We search for conditions that ensures that no non-Shannon inequalities exist. It is demonstrated that 3-dimensional distributive lattices cannot have non-Shannon inequalities and planar modular lattices cannot have non-Shannon inequalities. The existence of non-Shannon inequalities is related to the question of whether a lattice is isomorphic to a lattice of subgroups of a group.
On topological lower bounds for algebraic computation trees
Venue: arXiv cs.CC 2015
Year: 2015

We prove that the height of any algebraic computation tree for deciding membership in a semialgebraic set is bounded from below (up to a multiplicative constant) by the logarithm of m-th Betti number (with respect to singular homology) of the set, divided by m+1. This result complements the well known lower bound by Yao for locally closed semialgebraic sets in terms of the total Borel-Moore Betti number. We also prove that the height is bounded from below by the logarithm of m-th Betti number of a projection of the set onto a coordinate subspace, divided by (m+1)^2. We illustrate these general results by examples of lower complexity bounds for some specific computational problems.
Link Prediction in Networks with Nodes Attributes by Similarity Propagation
Venue: arXiv cs.SI 2015
Year: 2015

The problem of link prediction has attracted considerable recent attention from various domains such as sociology, anthropology, information science, and computer sciences. A link prediction algorithm is proposed based on link similarity score propagation by a random walk in networks with nodes attributes. In the algorithm, each link in the network is assigned a transmission probability according to the similarity of the attributes on the nodes connected by the link. The link similarity score between the nodes are then propagated via the links according to their transmission probability. Our experimental results show that it can obtain higher quality results on the networks with node attributes than other algorithms.
General Rank Multiuser Downlink Beamforming With Shaping Constraints Using Real-valued OSTBC
Venue: arXiv cs.IT 2015
Year: 2015

In this paper we consider optimal multiuser downlink beamforming in the presence of a massive number of arbitrary quadratic shaping constraints. We combine beamforming with full-rate high dimensional real-valued orthogonal space time block coding (OSTBC) to increase the number of beamforming weight vectors and associated degrees of freedom in the beamformer design. The original multi-constraint beamforming problem is converted into a convex optimization problem using semidefinite relaxation (SDR) which can be solved efficiently. In contrast to conventional (rank-one) beamforming approaches in which an optimal beamforming solution can be obtained only when the SDR solution (after rank reduction) exhibits the rank-one property, in our approach optimality is guaranteed when a rank of eight is not exceeded. We show that our approach can incorporate up to 79 additional shaping constraints for which an optimal beamforming solution is guaranteed as compared to a maximum of two additional constraints that bound the conventional rank-one downlink beamforming designs. Simulation results demonstrate the flexibility of our proposed beamformer design.
Smaller Selection Networks for Cardinality Constraints Encoding
Venue: arXiv cs.DS 2015
Year: 2015

Selection comparator networks have been studied for many years. Recently, they have been successfully applied to encode cardinality constraints for SAT-solvers. To decrease the size of generated formula there is a need for constructions of selection networks that can be efficiently generated and produce networks of small sizes for the practical range of their two parameters: n - the number of inputs (boolean variables) and k - the number of selected items (a cardinality bound). In this paper we give and analyze a new construction of smaller selection networks that are based on the pairwise selection networks introduced by Codish and Zanon-Ivry. We prove also that standard encodings of cardinality constraints with selection networks preserve arc-consistency.
Improved Monte Carlo Variance Reduction for Space and Energy Self-Shielding
Venue: arXiv cs.NA 2015
Year: 2015

Continued demand for accurate and computationally efficient transport methods to solve optically thick, fixed-source transport problems has inspired research on variance-reduction (VR) techniques for Monte Carlo (MC). Methods that use deterministic results to create VR maps for MC constitute a dominant branch of this research, with Forward Weighted-Consistent Adjoint Driven Importance Sampling (FW-CADIS) being a particularly successful example. However, locations in which energy and spatial self-shielding are combined, such as thin plates embedded in concrete, challenge FW-CADIS. In these cases the deterministic flux cannot appropriately capture transport behavior, and the associated VR parameters result in high variance in and following the plate. This work presents a new method that improves performance in transport calculations that contain regions of combined space and energy self-shielding without significant impact on the solution quality in other parts of the problem. This method is based on FW-CADIS and applies a Resonance Factor correction to the adjoint source. The impact of the Resonance Factor method is investigated in this work through an example problem. It is clear that this new method dramatically improves performance in terms of lowering the maximum 95% confidence interval relative error and reducing the compute time. Based on this work, we recommend that the Resonance Factor method be used when the accuracy of the solution in the presence of combined space and energy self-shielding is important.
Geometry of Resource Interaction - A Minimalist Approach
Venue: arXiv cs.LO 2015
Year: 2015

The Resource $λ$-calculus is a variation of the $λ$-calculus where arguments can be superposed and must be linearly used. Hence it is a model for linear and non-deterministic programming languages, and the target language of Ehrhard-Taylor expansion of $λ$-terms. In a strictly typed restriction of the Resource $λ$-calculus, we study the notion of path persistence, and we define a Geometry of Interaction that characterises it, is invariant under reduction, and counts addends in normal forms.
Corrigendum to "Random grid-based visual secret sharing with abilities of OR and XOR decryptions"[Journal of Visual Communication and Image Representation. 24(2013) 48-62]
Venue: arXiv cs.CR 2015
Year: 2015

It has been observed that the contrast values for (2, 3) VSS scheme, (2, 4) VSS scheme, (3, 5) VSS scheme and (4, 5) VSS scheme claimed by Wu and Sun (2013) are found to be incorrect. Since the same values are cited and compared by many other researchers in their works, we have calculated and presented the correct values of contrast in this note.
Generalized Gradient Learning on Time Series under Elastic Transformations
Venue: arXiv cs.LG 2015
Year: 2015

The majority of machine learning algorithms assumes that objects are represented as vectors. But often the objects we want to learn on are more naturally represented by other data structures such as sequences and time series. For these representations many standard learning algorithms are unavailable. We generalize gradient-based learning algorithms to time series under dynamic time warping. To this end, we introduce elastic functions, which extend functions on time series to matrix spaces. Necessary conditions are presented under which generalized gradient learning on time series is consistent. We indicate how results carry over to arbitrary elastic distance functions and to sequences consisting of symbolic elements. Specifically, four linear classifiers are extended to time series under dynamic time warping and applied to benchmark datasets. Results indicate that generalized gradient learning via elastic functions have the potential to complement the state-of-the-art in statistical pattern recognition on time series.
Evaluation of Security Solutions for Android Systems
Venue: arXiv cs.CR 2015
Year: 2015

With the increasing usage of smartphones a plethora of security solutions are being designed and developed. Many of the security solutions fail to cope with advanced attacks and are not aways properly designed for smartphone platforms. Therefore, there is a need for a methodology to evaluate their effectiveness. Since the Android operating system has the highest market share today, we decided to focus on it in this study in which we review some of the state-of-the-art security solutions for Android-based smartphones. In addition, we present a set of evaluation criteria aiming at evaluating security mechanisms that are specifically designed for Android-based smartphones. We believe that the proposed framework will help security solution designers develop more effective solutions and assist security experts evaluate the effectiveness of security solutions for Android-based smartphones.
Count-Min-Log sketch: Approximately counting with approximate counters
Venue: arXiv cs.IR 2015
Year: 2015

Count-Min Sketch is a widely adopted algorithm for approximate event counting in large scale processing. However, the original version of the Count-Min-Sketch (CMS) suffers of some deficiences, especially if one is interested by the low-frequency items, such as in text-mining related tasks. Several variants of CMS have been proposed to compensate for the high relative error for low-frequency events, but the proposed solutions tend to correct the errors instead of preventing them. In this paper, we propose the Count-Min-Log sketch, which uses logarithm-based, approximate counters instead of linear counters to improve the average relative error of CMS at constant memory footprint.
Recognisable languages over monads
Venue: arXiv cs.LO 2015
Year: 2015

The principle behind algebraic language theory for various kinds of structures, such as words or trees, is to use a compositional function from the structures into a finite set. To talk about compositionality, one needs some way of composing structures into bigger structures. It so happens that category theory has an abstract concept for this, namely a monad. The goal of this paper is to propose monads as a unifying framework for discussing existing algebras and designing new algebras.
Inductive Learning for Rule Generation from Ontology
Venue: arXiv cs.AI 2015
Year: 2015

This paper presents an idea of inductive learning use for rule generation from ontologies. The main purpose of the paper is to evaluate the possibility of inductive learning use in rule generation from ontologies and to develop the way how this can be done. Generated rules are necessary to supplement or even to develop the Semantic Web Expert System (SWES) knowledge base. The SWES emerges as the result of evolution of expert system concept toward the Web, and the SWES is based on the Semantic Web technologies. Available publications show that the problem of rule generation from ontologies based on inductive learning is not investigated deeply enough.
"The Whole Is Greater Than the Sum of Its Parts": Optimization in Collaborative Crowdsourcing
Venue: arXiv cs.DB 2015
Year: 2015

In this work, we initiate the investigation of optimization opportunities in collaborative crowdsourcing. Many popular applications, such as collaborative document editing, sentence translation, or citizen science resort to this special form of human-based computing, where, crowd workers with appropriate skills and expertise are required to form groups to solve complex tasks. Central to any collaborative crowdsourcing process is the aspect of successful collaboration among the workers, which, for the first time, is formalized and then optimized in this work. Our formalism considers two main collaboration-related human factors, affinity and upper critical mass, appropriately adapted from organizational science and social theories. Our contributions are (a) proposing a comprehensive model for collaborative crowdsourcing optimization, (b) rigorous theoretical analyses to understand the hardness of the proposed problems, (c) an array of efficient exact and approximation algorithms with provable theoretical guarantees. Finally, we present a detailed set of experimental results stemming from two real-world collaborative crowdsourcing application us- ing Amazon Mechanical Turk, as well as conduct synthetic data analyses on scalability and qualitative aspects of our proposed algorithms. Our experimental results successfully demonstrate the efficacy of our proposed solutions.
Assessing the effectiveness of real-world network simplification
Venue: arXiv cs.SI 2015
Year: 2015

Many real-world networks are large, complex and thus hard to understand, analyze or visualize. The data about networks is not always complete, their structure may be hidden or they change quickly over time. Therefore, understanding how incomplete system differs from complete one is crucial. In this paper, we study the changes in networks under simplification (i.e., reduction in size). We simplify 30 real-world networks with six simplification methods and analyze the similarity between original and simplified networks based on preservation of several properties, for example degree distribution, clustering coefficient, betweenness centrality, density and degree mixing. We propose an approach for assessing the effectiveness of simplification process to define the most appropriate size of simplified networks and to determine the method, which preserves the most properties of original networks. The results reveal the type and size of original networks do not influence the changes of networks under simplification process, while the size of simplified networks does. Moreover, we investigate the performance of simplification methods when the size of simplified networks is 10% of the original networks. The findings show that sampling methods outperform merging ones, particularly random node selection based on degree and breadth-first sampling perform the best.
Determining Training Needs for Cloud Infrastructure Investigations using I-STRIDE
Venue: arXiv cs.CY 2015
Year: 2015

As more businesses and users adopt cloud computing services, security vulnerabilities will be increasingly found and exploited. There are many technological and political challenges where investigation of potentially criminal incidents in the cloud are concerned. Security experts, however, must still be able to acquire and analyze data in a methodical, rigorous and forensically sound manner. This work applies the STRIDE asset-based risk assessment method to cloud computing infrastructure for the purpose of identifying and assessing an organization's ability to respond to and investigate breaches in cloud computing environments. An extension to the STRIDE risk assessment model is proposed to help organizations quickly respond to incidents while ensuring acquisition and integrity of the largest amount of digital evidence possible. Further, the proposed model allows organizations to assess the needs and capacity of their incident responders before an incident occurs.
Twofold exp and log
Venue: arXiv cs.MS 2015
Year: 2015

This article is about twofold arithmetic. Here I introduce algorithms and experimental code for twofold variant of C/C++ standard functions exp() and log(), and expm1() and log1p(). Twofold function $y_0+y_1 \approx f(x_0+x_1)$ is nearly 2x-precise so can assess accuracy of standard one. Performance allows assessing on-fly: twofold texp() over double is ~10x times faster than expq() by GNU quadmath.
SA-CNN: Dynamic Scene Classification using Convolutional Neural Networks
Venue: arXiv cs.CV 2015
Year: 2015

The task of classifying videos of natural dynamic scenes into appropriate classes has gained lot of attention in recent years. The problem especially becomes challenging when the camera used to capture the video is dynamic. In this paper, we analyse the performance of statistical aggregation (SA) techniques on various pre-trained convolutional neural network(CNN) models to address this problem. The proposed approach works by extracting CNN activation features for a number of frames in a video and then uses an aggregation scheme in order to obtain a robust feature descriptor for the video. We show through results that the proposed approach performs better than the-state-of-the arts for the Maryland and YUPenn dataset. The final descriptor obtained is powerful enough to distinguish among dynamic scenes and is even capable of addressing the scenario where the camera motion is dominant and the scene dynamics are complex. Further, this paper shows an extensive study on the performance of various aggregation methods and their combinations. We compare the proposed approach with other dynamic scene classification algorithms on two publicly available datasets - Maryland and YUPenn to demonstrate the superior performance of the proposed approach.
Sherali-Adams relaxations for valued CSPs
Venue: arXiv cs.CC 2015
Year: 2015

We consider Sherali-Adams linear programming relaxations for solving valued constraint satisfaction problems to optimality. The utility of linear programming relaxations in this context have previously been demonstrated using the lowest possible level of this hierarchy under the name of the basic linear programming relaxation (BLP). It has been shown that valued constraint languages containing only finite-valued weighted relations are tractable if, and only if, the integrality gap of the BLP is 1. In this paper, we demonstrate that almost all of the known tractable languages with arbitrary weighted relations have an integrality gap 1 for the Sherali-Adams relaxation with parameters (2,3). The result is closely connected to the notion of bounded relational width for the ordinary constraint satisfaction problem and its recent characterisation.