OpenRaiser/Intern-Atlas huggingface dataset:
On the Linear Belief Compression of POMDPs: A re-examination of current methods
Venue: arXiv cs.AI 2015
Year: 2015

Belief compression improves the tractability of large-scale partially observable Markov decision processes (POMDPs) by finding projections from high-dimensional belief space onto low-dimensional approximations, where solving to obtain action selection policies requires fewer computations. This paper develops a unified theoretical framework to analyse three existing linear belief compression approaches, including value-directed compression and two non-negative matrix factorisation (NMF) based algorithms. The results indicate that all the three known belief compression methods have their own critical deficiencies. Therefore, projective NMF belief compression is proposed (P-NMF), aiming to overcome the drawbacks of the existing techniques. The performance of the proposed algorithm is examined on four POMDP problems of reasonably large scale, in comparison with existing techniques. Additionally, the competitiveness of belief compression is compared empirically to a state-of-the-art heuristic search based POMDP solver and their relative merits in solving large-scale POMDPs are investigated.
INsight: A Neuromorphic Computing System for Evaluation of Large Neural Networks
Venue: arXiv cs.NE 2015
Year: 2015

Deep neural networks have been demonstrated impressive results in various cognitive tasks such as object detection and image classification. In order to execute large networks, Von Neumann computers store the large number of weight parameters in external memories, and processing elements are timed-shared, which leads to power-hungry I/O operations and processing bottlenecks. This paper describes a neuromorphic computing system that is designed from the ground up for the energy-efficient evaluation of large-scale neural networks. The computing system consists of a non-conventional compiler, a neuromorphic architecture, and a space-efficient microarchitecture that leverages existing integrated circuit design methodologies. The compiler factorizes a trained, feedforward network into a sparsely connected network, compresses the weights linearly, and generates a time delay neural network reducing the number of connections. The connections and units in the simplified network are mapped to silicon synapses and neurons. We demonstrate an implementation of the neuromorphic computing system based on a field-programmable gate array that performs the MNIST hand-written digit classification with 97.64% accuracy.
Computational complexity of distance edge labeling
Venue: arXiv cs.DM 2015
Year: 2015

The problem of Distance Edge Labeling is a variant of Distance Vertex Labeling (also known as $L_{2,1}$ labeling) that has been studied for more than twenty years and has many applications, such as frequency assignment. The Distance Edge Labeling problem asks whether the edges of a given graph can be labeled such that the labels of adjacent edges differ by at least two and the labels of edges of distance two differ by at least one. Labels are chosen from the set $\{0,1,\dots,λ\}$ for $λ$ fixed. We present a full classification of its computational complexity - a dichotomy between the polynomially solvable cases and the remaining cases which are NP-complete. We characterise graphs with $λ\le 4$ which leads to a polynomial-time algorithm recognizing the class and we show NP-completeness for $λ\ge 5$ by several reductions from Monotone Not All Equal 3-SAT.
Edge modification criteria for enhancing the communicability of digraphs
Venue: arXiv cs.SI 2015
Year: 2015

We introduce new broadcast and receive communicability indices that can be used as global measures of how effectively information is spread in a directed network. Furthermore, we describe fast and effective criteria for the selection of edges to be added to (or deleted from) a given directed network so as to enhance these network communicability measures. Numerical experiments illustrate the effectiveness of the proposed techniques.
Topic Stability over Noisy Sources
Venue: arXiv cs.CL 2015
Year: 2015

Topic modelling techniques such as LDA have recently been applied to speech transcripts and OCR output. These corpora may contain noisy or erroneous texts which may undermine topic stability. Therefore, it is important to know how well a topic modelling algorithm will perform when applied to noisy data. In this paper we show that different types of textual noise will have diverse effects on the stability of different topic models. From these observations, we propose guidelines for text corpus generation, with a focus on automatic speech transcription. We also suggest topic model selection methods for noisy corpora.
Representing Directed Trees as Straight Skeletons
Venue: arXiv cs.CG 2015
Year: 2015

The straight skeleton of a polygon is the geometric graph obtained by tracing the vertices during a mitered offsetting process. It is known that the straight skeleton of a simple polygon is a tree, and one can naturally derive directions on the edges of the tree from the propagation of the shrinking process. In this paper, we ask the reverse question: Given a tree with directed edges, can it be the straight skeleton of a polygon? And if so, can we find a suitable simple polygon? We answer these questions for all directed trees where the order of edges around each node is fixed.
Symmetries of matrix multiplication algorithms. I
Venue: arXiv cs.CC 2015
Year: 2015

In this work the algorithms of fast multiplication of matrices are considered. To any algorithm there associated a certain group of automorphisms. These automorphism groups are found for some well-known algorithms, including algorithms of Hopcroft, Laderman, and Pan. The automorphism group is isomorphic to $S_3\times Z_2$ and $S_4$ for Hopcroft anf Laderman algorithms, respectively. The studying of symmetry of algorithms may be a fruitful idea for finding fast algorithms, by an analogy with well-known optimization problems for codes, lattices, and graphs. {\em Keywords}: Strassen algorithm, symmetry, fast matrix multiplication.
Partitioned Shape Modeling with On-the-Fly Sparse Appearance Learning for Anterior Visual Pathway Segmentation
Venue: arXiv cs.CV 2015
Year: 2015

MRI quantification of cranial nerves such as anterior visual pathway (AVP) in MRI is challenging due to their thin small size, structural variation along its path, and adjacent anatomic structures. Segmentation of pathologically abnormal optic nerve (e.g. optic nerve glioma) poses additional challenges due to changes in its shape at unpredictable locations. In this work, we propose a partitioned joint statistical shape model approach with sparse appearance learning for the segmentation of healthy and pathological AVP. Our main contributions are: (1) optimally partitioned statistical shape models for the AVP based on regional shape variations for greater local flexibility of statistical shape model; (2) refinement model to accommodate pathological regions as well as areas of subtle variation by training the model on-the-fly using the initial segmentation obtained in (1); (3) hierarchical deformable framework to incorporate scale information in partitioned shape and appearance models. Our method, entitled PAScAL (PArtitioned Shape and Appearance Learning), was evaluated on 21 MRI scans (15 healthy + 6 glioma cases) from pediatric patients (ages 2-17). The experimental results show that the proposed localized shape and sparse appearance-based learning approach significantly outperforms segmentation approaches in the analysis of pathological data.
On the Efficiency of All-Pay Mechanisms
Venue: arXiv cs.GT 2015
Year: 2015

We study the inefficiency of mixed equilibria, expressed as the price of anarchy, of all-pay auctions in three different environments: combinatorial, multi-unit and single-item auctions. First, we consider item-bidding combinatorial auctions where m all-pay auctions run in parallel, one for each good. For fractionally subadditive valuations, we strengthen the upper bound from 2 [Syrgkanis and Tardos STOC'13] to 1.82 by proving some structural properties that characterize the mixed Nash equilibria of the game. Next, we design an all-pay mechanism with a randomized allocation rule for the multi- unit auction. We show that, for bidders with submodular valuations, the mechanism admits a unique, 75% efficient, pure Nash equilibrium. The efficiency of this mechanism outperforms all the known bounds on the price of anarchy of mechanisms used for multi-unit auctions. Finally, we analyze single-item all-pay auctions motivated by their connection to contests and show tight bounds on the price of anarchy of social welfare, revenue and maximum bid.
Pushing towards the Limit of Sampling Rate: Adaptive Chasing Sampling
Venue: arXiv cs.IT 2015
Year: 2015

Measurement samples are often taken in various monitoring applications. To reduce the sensing cost, it is desirable to achieve better sensing quality while using fewer samples. Compressive Sensing (CS) technique finds its role when the signal to be sampled meets certain sparsity requirements. In this paper we investigate the possibility and basic techniques that could further reduce the number of samples involved in conventional CS theory by exploiting learning-based non-uniform adaptive sampling. Based on a typical signal sensing application, we illustrate and evaluate the performance of two of our algorithms, Individual Chasing and Centroid Chasing, for signals of different distribution features. Our proposed learning-based adaptive sampling schemes complement existing efforts in CS fields and do not depend on any specific signal reconstruction technique. Compared to conventional sparse sampling methods, the simulation results demonstrate that our algorithms allow $46\%$ less number of samples for accurate signal reconstruction and achieve up to $57\%$ smaller signal reconstruction error under the same noise condition.
A different perspective on a scale for pairwise comparisons
Venue: arXiv cs.AI 2015
Year: 2015

One of the major challenges for collective intelligence is inconsistency, which is unavoidable whenever subjective assessments are involved. Pairwise comparisons allow one to represent such subjective assessments and to process them by analyzing, quantifying and identifying the inconsistencies. We propose using smaller scales for pairwise comparisons and provide mathematical and practical justifications for this change. Our postulate's aim is to initiate a paradigm shift in the search for a better scale construction for pairwise comparisons. Beyond pairwise comparisons, the results presented may be relevant to other methods using subjective scales. Keywords: pairwise comparisons, collective intelligence, scale, subjective assessment, inaccuracy, inconsistency.
Power Allocation in Multi-hop OFDM Transmission Systems with Amplify-and-Forward Relaying: A Unified Approach
Venue: arXiv cs.IT 2015
Year: 2015

In this paper a unified approach for power allocation (PA) problem in multi-hop orthogonal frequency division multiplexing (OFDM) amplify-and-forward (AF) relaying systems has been developed. In the proposed approach, we consider short and long-term individual and total power constraints at the source and relays, and devise decentralized low complexity PA algorithms when wireless links are subject to channel path-loss and small-scale Rayleigh fading. In particular, aiming at improving the instantaneous rate of multi-hop transmission systems with AF relaying, we develop (i) a near-optimal iterative PA algorithm based on the exact analysis of the received SNR at the destination; (ii) a low complexity-suboptimal iterative PA algorithm based on an approximate expression at high-SNR regime; and (iii) a low complexity-non iterative PA scheme with limited performance loss. Since the PA problem in multi-hop systems is too complex to solve with known optimization solvers, in the proposed formulations, we adopted a two-stage approach, including a power distribution phase among distinct subcarriers, and a power allocation phase among different relays. The individual PA phases are then appropriately linked through an iterative method which tries to compensate the performance loss caused by the distinct two-stage approach. Simulation results show the superior performance of the proposed power allocation algorithms.
On Gobbledygook and Mood of the Philippine Senate: An Exploratory Study on the Readability and Sentiment of Selected Philippine Senators' Microposts
Venue: arXiv cs.CL 2015
Year: 2015

This paper presents the findings of a readability assessment and sentiment analysis of selected six Philippine senators' microposts over the popular Twitter microblog. Using the Simple Measure of Gobbledygook (SMOG), tweets of Senators Cayetano, Defensor-Santiago, Pangilinan, Marcos, Guingona, and Escudero were assessed. A sentiment analysis was also done to determine the polarity of the senators' respective microposts. Results showed that on the average, the six senators are tweeting at an eight to ten SMOG level. This means that, at least a sixth grader will be able to understand the senators' tweets. Moreover, their tweets are mostly neutral and their sentiments vary in unison at some period of time. This could mean that a senator's tweet sentiment is affected by specific Philippine-based events.
Enhanced Usability of Managing Workflows in an Industrial Data Gateway
Venue: arXiv cs.DC 2015
Year: 2015

The Grid and Cloud User Support Environment (gUSE) enables users convenient and easy access to grid and cloud infrastructures by providing a general purpose, workflow-oriented graphical user interface to create and run workflows on various Distributed Computing Infrastructures (DCIs). Its arrangements for creating and modifying existing workflows are, however, non-intuitive and cumbersome due to the technologies and architecture employed by gUSE. In this paper, we outline the first integrated web-based workflow editor for gUSE with the aim of improving the user experience for those with industrial data workflows and the wider gUSE community. We report initial assessments of the editor's utility based on users' feedback. We argue that combining access to diverse scalable resources with improved workflow creation tools is important for all big data applications and research infrastructures.
Using Linguistic Analysis to Translate Arabic Natural Language Queries to SPARQL
Venue: arXiv cs.CL 2015
Year: 2015

The logic-based machine-understandable framework of the Semantic Web often challenges naive users when they try to query ontology-based knowledge bases. Existing research efforts have approached this problem by introducing Natural Language (NL) interfaces to ontologies. These NL interfaces have the ability to construct SPARQL queries based on NL user queries. However, most efforts were restricted to queries expressed in English, and they often benefited from the advancement of English NLP tools. However, little research has been done to support querying the Arabic content on the Semantic Web by using NL queries. This paper presents a domain-independent approach to translate Arabic NL queries to SPARQL by leveraging linguistic analysis. Based on a special consideration on Noun Phrases (NPs), our approach uses a language parser to extract NPs and the relations from Arabic parse trees and match them to the underlying ontology. It then utilizes knowledge in the ontology to group NPs into triple-based representations. A SPARQL query is finally generated by extracting targets and modifiers, and interpreting them into SPARQL. The interpretation of advanced semantic features including negation, conjunctive and disjunctive modifiers is also supported. The approach was evaluated by using two datasets consisting of OWL test data and queries, and the obtained results have confirmed its feasibility to translate Arabic NL queries to SPARQL.
On the Security of Privacy-Preserving Vehicular Communication Authentication with Hierarchical Aggregation and Fast Response
Venue: arXiv cs.CR 2015
Year: 2015

In [3], the authors proposed a highly efficient secure and privacy-preserving scheme for secure vehicular communications. The proposed scheme consists of four protocols: system setup, protocol for STP and STK distribution, protocol for common string synchronization, and protocol for vehicular communications. Here we define the security models for the protocol for STP and STK distribution, and the protocol for vehicular communications,respectively. We then prove that these two protocols are secure in our models.
Distributed and Optimal Resource Allocation for Power Beacon-Assisted Wireless-Powered Communications
Venue: arXiv cs.IT 2015
Year: 2015

In this paper, we investigate optimal resource allocation in a power beacon-assisted wireless-powered communication network (PB-WPCN), which consists of a set of hybrid access point (AP)-source pairs and a power beacon (PB). Each source, which has no embedded power supply, first harvests energy from its associated AP and/or the PB in the downlink (DL) and then uses the harvested energy to transmit information to its AP in the uplink (UL). We consider both cooperative and non-cooperative scenarios based on whether the PB is cooperative with the APs or not. For the cooperative scenario, we formulate a social welfare maximization problem to maximize the weighted sum-throughput of all AP-source pairs, which is subsequently solved by a water-filling based distributed algorithm. In the non-cooperative scenario, all the APs and the PB are assumed to be rational and self-interested such that incentives from each AP are needed for the PB to provide wireless charging service. We then formulate an auction game and propose an auction based distributed algorithm by considering the PB as the auctioneer and the APs as the bidders. Finally, numerical results are performed to validate the convergence of both the proposed algorithms and demonstrate the impacts of various system parameters.
Determining the network throughput and flow rate using GSR And AAL2R
Venue: arXiv cs.NI 2015
Year: 2015

In multi-radio wireless mesh networks, one node is eligible to transmit packets over multiple channels to different destination nodes simultaneously. This feature of multi-radio wireless mesh network makes high throughput for the network and increase the chance for multi path routing. This is because the multiple channel availability for transmission decreases the probability of the most elegant problem called as interference problem which is either of interflow and intraflow type. For avoiding the problem like interference and maintaining the constant network performance or increasing the performance the WMN need to consider the packet aggregation and packet forwarding. Packet aggregation is process of collecting several packets ready for transmission and sending them to the intended recipient through the channel, while the packet forwarding holds the hop-by-hop routing. But choosing the correct path among different available multiple paths is most the important factor in the both case for a routing algorithm. Hence the most challenging factor is to determine a forwarding strategy which will provide the schedule for each node for transmission within the channel. In this research work we have tried to implement two forwarding strategies for the multi path multi radio WMN as the approximate solution for the above said problem. We have implemented Global State Routing (GSR) which will consider the packet forwarding concept and Aggregation Aware Layer 2 Routing (AAL2R) which considers the both concept i.e. both packet forwarding and packet aggregation. After the successful implementation the network performance has been measured by means of simulation study.
Asynchronous Distributed Semi-Stochastic Gradient Optimization
Venue: arXiv cs.LG 2015
Year: 2015

With the recent proliferation of large-scale learning problems,there have been a lot of interest on distributed machine learning algorithms, particularly those that are based on stochastic gradient descent (SGD) and its variants. However, existing algorithms either suffer from slow convergence due to the inherent variance of stochastic gradients, or have a fast linear convergence rate but at the expense of poorer solution quality. In this paper, we combine their merits by proposing a fast distributed asynchronous SGD-based algorithm with variance reduction. A constant learning rate can be used, and it is also guaranteed to converge linearly to the optimal solution. Experiments on the Google Cloud Computing Platform demonstrate that the proposed algorithm outperforms state-of-the-art distributed asynchronous algorithms in terms of both wall clock time and solution quality.
Analysing the Security of Google's implementation of OpenID Connect
Venue: arXiv cs.CR 2015
Year: 2015

Many millions of users routinely use their Google accounts to log in to relying party (RP) websites supporting the Google OpenID Connect service. OpenID Connect, a newly standardised single-sign-on protocol, builds an identity layer on top of the OAuth 2.0 protocol, which has itself been widely adopted to support identity management services. It adds identity management functionality to the OAuth 2.0 system and allows an RP to obtain assurances regarding the authenticity of an end user. A number of authors have analysed the security of the OAuth 2.0 protocol, but whether OpenID Connect is secure in practice remains an open question. We report on a large-scale practical study of Google's implementation of OpenID Connect, involving forensic examination of 103 RP websites which support its use for sign-in. Our study reveals serious vulnerabilities of a number of types, all of which allow an attacker to log in to an RP website as a victim user. Further examination suggests that these vulnerabilities are caused by a combination of Google's design of its OpenID Connect service and RP developers making design decisions which sacrifice security for simplicity of implementation. We also give practical recommendations for both RPs and OPs to help improve the security of real world OpenID Connect systems.
Constant dimension codes from Riemann-Roch spaces
Venue: arXiv cs.IT 2015
Year: 2015

Some families of constant dimension codes arising from Riemann-Roch spaces associated to particular divisors of a curve $\X$ are constructed. These families are generalizations of the one constructed by Hansen
Position Equations of a 3RPR Planar Manipulator
Venue: arXiv cs.RO 2015
Year: 2015

We study parametric equations, which describe the position of an in-parallel planar manipulator. We discuss isometries in the Gauss plane, then we write the loop-closure equations in terms of the rotations as the parameters.
New Guarantees for Blind Compressed Sensing
Venue: arXiv cs.IT 2015
Year: 2015

Blind Compressed Sensing (BCS) is an extension of Compressed Sensing (CS) where the optimal sparsifying dictionary is assumed to be unknown and subject to estimation (in addition to the CS sparse coefficients). Since the emergence of BCS, dictionary learning, a.k.a. sparse coding, has been studied as a matrix factorization problem where its sample complexity, uniqueness and identifiability have been addressed thoroughly. However, in spite of the strong connections between BCS and sparse coding, recent results from the sparse coding problem area have not been exploited within the context of BCS. In particular, prior BCS efforts have focused on learning constrained and complete dictionaries that limit the scope and utility of these efforts. In this paper, we develop new theoretical bounds for perfect recovery for the general unconstrained BCS problem. These unconstrained BCS bounds cover the case of overcomplete dictionaries, and hence, they go well beyond the existing BCS theory. Our perfect recovery results integrate the combinatorial theories of sparse coding with some of the recent results from low-rank matrix recovery. In particular, we propose an efficient CS measurement scheme that results in practical recovery bounds for BCS. Moreover, we discuss the performance of BCS under polynomial-time sparse coding algorithms.