OpenRaiser/Intern-Atlas huggingface dataset:
Pulling back error to the hidden-node parameter technology: Single-hidden-layer feedforward network without output weight
Venue: arXiv cs.NE 2014
Year: 2014

According to conventional neural network theories, the feature of single-hidden-layer feedforward neural networks(SLFNs) resorts to parameters of the weighted connections and hidden nodes. SLFNs are universal approximators when at least the parameters of the networks including hidden-node parameter and output weight are exist. Unlike above neural network theories, this paper indicates that in order to let SLFNs work as universal approximators, one may simply calculate the hidden node parameter only and the output weight is not needed at all. In other words, this proposed neural network architecture can be considered as a standard SLFNs with fixing output weight equal to an unit vector. Further more, this paper presents experiments which show that the proposed learning method tends to extremely reduce network output error to a very small number with only 1 hidden node. Simulation results demonstrate that the proposed method can provide several to thousands of times faster than other learning algorithm including BP, SVM/SVR and other ELM methods.
claspfolio 2: Advances in Algorithm Selection for Answer Set Programming
Venue: arXiv cs.AI 2014
Year: 2014

To appear in Theory and Practice of Logic Programming (TPLP). Building on the award-winning, portfolio-based ASP solver claspfolio, we present claspfolio 2, a modular and open solver architecture that integrates several different portfolio-based algorithm selection approaches and techniques. The claspfolio 2 solver framework supports various feature generators, solver selection approaches, solver portfolios, as well as solver-schedule-based pre-solving techniques. The default configuration of claspfolio 2 relies on a light-weight version of the ASP solver clasp to generate static and dynamic instance features. The flexible open design of claspfolio 2 is a distinguishing factor even beyond ASP. As such, it provides a unique framework for comparing and combining existing portfolio-based algorithm selection approaches and techniques in a single, unified framework. Taking advantage of this, we conducted an extensive experimental study to assess the impact of different feature sets, selection approaches and base solver portfolios. In addition to gaining substantial insights into the utility of the various approaches and techniques, we identified a default configuration of claspfolio 2 that achieves substantial performance gains not only over clasp's default configuration and the earlier version of claspfolio 2, but also over manually tuned configurations of clasp.
Learning Boolean Halfspaces with Small Weights from Membership Queries
Venue: arXiv cs.LG 2014
Year: 2014

We consider the problem of proper learning a Boolean Halfspace with integer weights $\{0,1,\ldots,t\}$ from membership queries only. The best known algorithm for this problem is an adaptive algorithm that asks $n^{O(t^5)}$ membership queries where the best lower bound for the number of membership queries is $n^t$ [Learning Threshold Functions with Small Weights Using Membership Queries. COLT 1999] In this paper we close this gap and give an adaptive proper learning algorithm with two rounds that asks $n^{O(t)}$ membership queries. We also give a non-adaptive proper learning algorithm that asks $n^{O(t^3)}$ membership queries.
A Concurrent Pattern Calculus
Venue: arXiv cs.LO 2014
Year: 2014

Concurrent pattern calculus (CPC) drives interaction between processes by comparing data structures, just as sequential pattern calculus drives computation. By generalising from pattern matching to pattern unification, interaction becomes symmetrical, with information flowing in both directions. CPC provides a natural language to express trade where information exchange is pivotal to interaction. The unification allows some patterns to be more discriminating than others; hence, the behavioural theory must take this aspect into account, so that bisimulation becomes subject to compatibility of patterns. Many popular process calculi can be encoded in CPC; this allows for a gain in expressiveness, formalised through encodings.
Efficient Cooperative Anycasting for AMI Mesh Networks
Venue: arXiv cs.NI 2014
Year: 2014

We have, in recent years, witnessed an increased interest towards enabling a Smart Grid which will be a corner stone to build sustainable energy efficient communities. An integral part of the future Smart Grid will be the communications infrastructure which will make real time control of the grid components possible. Automated Metering Infrastructure (AMI) is thought to be a key enabler for monitoring and controlling the customer loads. %RPL is a connectivity enabling mechanism for low power and lossy networks currently being standardized by the IETF ROLL working group. RPL is deemed to be a suitable candidate for AMI networks where the meters are connected to a concentrator over multi hop low power and lossy links. This paper proposes an efficient cooperative anycasting approach for wireless mesh networks with the aim of achieving reduced traffic and increased utilisation of the network resources. The proposed cooperative anycasting has been realised as an enhancement on top of the Routing Protocol for Low Power and Lossy Networks (RPL), a connectivity enabling mechanism in wireless AMI mesh networks. In this protocol, smart meter nodes utilise an anycasting approach to facilitate efficient transport of metering data to the concentrator node. Moreover, it takes advantage of a distributed approach ensuring scalability.
Tableau vs. Sequent Calculi for Minimal Entailment
Venue: arXiv cs.LO 2014
Year: 2014

In this paper we compare two proof systems for minimal entailment: a tableau system OTAB and a sequent calculus MLK, both developed by Olivetti (1992). Our main result shows that OTAB-proofs can be efficiently translated into MLK-proofs, i.e; MLK p-simulates OTAB. The simulation is technically very involved and answers an open question posed by Olivetti (1992) on the relation between the two calculi. We also show that the two systems are exponentially separated, i.e; there are formulas which have polynomial size MLK-proofs, but require exponential-size OTAB- proofs.
Markov Chain Monte Carlo Algorithms for Lattice Gaussian Sampling
Venue: arXiv cs.IT 2014
Year: 2014

Sampling from a lattice Gaussian distribution is emerging as an important problem in various areas such as coding and cryptography. The default sampling algorithm --- Klein's algorithm yields a distribution close to the lattice Gaussian only if the standard deviation is sufficiently large. In this paper, we propose the Markov chain Monte Carlo (MCMC) method for lattice Gaussian sampling when this condition is not satisfied. In particular, we present a sampling algorithm based on Gibbs sampling, which converges to the target lattice Gaussian distribution for any value of the standard deviation. To improve the convergence rate, a more efficient algorithm referred to as Gibbs-Klein sampling is proposed, which samples block by block using Klein's algorithm. We show that Gibbs-Klein sampling yields a distribution close to the target lattice Gaussian, under a less stringent condition than that of the original Klein algorithm.
Structured Learning Modulo Theories
Venue: arXiv cs.AI 2014
Year: 2014

Modelling problems containing a mixture of Boolean and numerical variables is a long-standing interest of Artificial Intelligence. However, performing inference and learning in hybrid domains is a particularly daunting task. The ability to model this kind of domains is crucial in "learning to design" tasks, that is, learning applications where the goal is to learn from examples how to perform automatic {\em de novo} design of novel objects. In this paper we present Structured Learning Modulo Theories, a max-margin approach for learning in hybrid domains based on Satisfiability Modulo Theories, which allows to combine Boolean reasoning and optimization over continuous linear arithmetical constraints. The main idea is to leverage a state-of-the-art generalized Satisfiability Modulo Theory solver for implementing the inference and separation oracles of Structured Output SVMs. We validate our method on artificial and real world scenarios.
Trade-offs between Selection Complexity and Performance when Searching the Plane without Communication
Venue: arXiv cs.DC 2014
Year: 2014

We consider the ANTS problem [Feinerman et al.] in which a group of agents collaboratively search for a target in a two-dimensional plane. Because this problem is inspired by the behavior of biological species, we argue that in addition to studying the {\em time complexity} of solutions it is also important to study the {\em selection complexity}, a measure of how likely a given algorithmic strategy is to arise in nature due to selective pressures. In more detail, we propose a new selection complexity metric $χ$, defined for algorithm ${\cal A}$ such that $χ({\cal A}) = b + \log \ell$, where $b$ is the number of memory bits used by each agent and $\ell$ bounds the fineness of available probabilities (agents use probabilities of at least $1/2^\ell$). In this paper, we study the trade-off between the standard performance metric of speed-up, which measures how the expected time to find the target improves with $n$, and our new selection metric. In particular, consider $n$ agents searching for a treasure located at (unknown) distance $D$ from the origin (where $n$ is sub-exponential in $D$). For this problem, we identify $\log \log D$ as a crucial threshold for our selection complexity metric. We first prove a new upper bound that achieves a near-optimal speed-up of $(D^2/n +D) \cdot 2^{O(\ell)}$ for $χ({\cal A}) \leq 3 \log \log D + O(1)$. In particular, for $\ell \in O(1)$, the speed-up is asymptotically optimal. By comparison, the existing results for this problem [Feinerman et al.] that achieve similar speed-up require $χ({\cal A}) = Ω(\log D)$. We then show that this threshold is tight by describing a lower bound showing that if $χ({\cal A}) < \log \log D - ω(1)$, then with high probability the target is not found within $D^{2-o(1)}$ moves per agent. Hence, there is a sizable gap to the straightforward $Ω(D^2/n + D)$ lower bound in this setting.
Like, Comment, Repin: User Interaction on Pinterest
Venue: arXiv cs.SI 2014
Year: 2014

We present the results of a study of the Pinterest activity graph. Pinterest is a relatively new and extremely popular content-based social network. Building on a body of work showing that the hidden network whose edges are actual interactions between users is more informative about social relationships that the follower-following network, we study the activity graph composed of links formed by liking, commenting, and repinning, and show that it is very different from the follow network. We collect data about 14 million pins, 7 million repins, 1.6 million likes, and several hundred thousand users and report interesting results about social activity on Pinterest. In particular, we discover that only 12.3% of a user's followers interact with their pins, and over 70% of activity on each user's boards is done by non-followers, but on average, followers who are active perform twice as many actions as non-followers.
Approximation Algorithms for the Asymmetric Traveling Salesman Problem : Describing two recent methods
Venue: arXiv cs.DS 2014
Year: 2014

The paper provides a description of the two recent approximation algorithms for the Asymmetric Traveling Salesman Problem, giving the intuitive description of the works of Feige-Singh[1] and Asadpour et.al\ [2].\newline [1] improves the previous $O(\log n)$ approximation algorithm, by improving the constant from 0.84 to 0.66 and modifying the work of Kaplan et. al\ [3] and also shows an efficient reduction from ATSPP to ATSP. Combining both the results, they finally establish an approximation ratio of $\left(\frac{4}{3}+ε\right)\log n$ for ATSPP,\ considering a small $ε>0$,\ improving the work of Chekuri and Pal.[4]\newline Asadpour et.al, in their seminal work\ [2], gives an $O\left(\frac{\log n}{\log \log n}\right)$ randomized algorithm for the ATSP, by symmetrizing and modifying the solution of the Held-Karp relaxation problem and then proving an exponential family distribution for probabilistically constructing a maximum entropy spanning tree from a spanning tree polytope and then finally defining the thin-ness property and transforming a thin spanning tree into an Eulerian walk.\ The optimization methods used in\ [2] are quite elegant and the approximation ratio could further be improved, by manipulating the thin-ness of the cuts.
Utilizing Online Social Network and Location-Based Data to Recommend Products and Categories in Online Marketplaces
Venue: arXiv cs.IR 2014
Year: 2014

Recent research has unveiled the importance of online social networks for improving the quality of recommender systems and encouraged the research community to investigate better ways of exploiting the social information for recommendations. To contribute to this sparse field of research, in this paper we exploit users' interactions along three data sources (marketplace, social network and location-based) to assess their performance in a barely studied domain: recommending products and domains of interests (i.e., product categories) to people in an online marketplace environment. To that end we defined sets of content- and network-based user similarity features for each data source and studied them isolated using an user-based Collaborative Filtering (CF) approach and in combination via a hybrid recommender algorithm, to assess which one provides the best recommendation performance. Interestingly, in our experiments conducted on a rich dataset collected from SecondLife, a popular online virtual world, we found that recommenders relying on user similarity features obtained from the social network data clearly yielded the best results in terms of accuracy in case of predicting products, whereas the features obtained from the marketplace and location-based data sources also obtained very good results in case of predicting categories. This finding indicates that all three types of data sources are important and should be taken into account depending on the level of specialization of the recommendation task.
SocRecM: A Scalable Social Recommender Engine for Online Marketplaces
Venue: arXiv cs.IR 2014
Year: 2014

In this paper, we present work-in-progress on SocRecM, a novel social recommendation framework for online marketplaces. We demonstrate that SocRecM is not only easy to integrate with existing Web technologies through a RESTful, scalable and easy-to-extend service-based architecture but also reveal the extent to which various social features and recommendation approaches are useful in an online social marketplace environment.
Modeling Bitcoin Contracts by Timed Automata
Venue: arXiv cs.CR 2014
Year: 2014

Bitcoin is a peer-to-peer cryptographic currency system. Since its introduction in 2008, Bitcoin has gained noticeable popularity, mostly due to its following properties: (1) the transaction fees are very low, and (2) it is not controlled by any central authority, which in particular means that nobody can "print" the money to generate inflation. Moreover, the transaction syntax allows to create the so-called contracts, where a number of mutually-distrusting parties engage in a protocol to jointly perform some financial task, and the fairness of this process is guaranteed by the properties of Bitcoin. Although the Bitcoin contracts have several potential applications in the digital economy, so far they have not been widely used in real life. This is partly due to the fact that they are cumbersome to create and analyze, and hence risky to use. In this paper we propose to remedy this problem by using the methods originally developed for the computer-aided analysis for hardware and software systems, in particular those based on the timed automata. More concretely, we propose a framework for modeling the Bitcoin contracts using the timed automata in the UPPAAL model checker. Our method is general and can be used to model several contracts. As a proof-of-concept we use this framework to model some of the Bitcoin contracts from our recent previous work. We then automatically verify their security in UPPAAL, finding (and correcting) some subtle errors that were difficult to spot by the manual analysis. We hope that our work can draw the attention of the researchers working on formal modeling to the problem of the Bitcoin contract verification, and spark off more research on this topic.
Automatic Annotation of Axoplasmic Reticula in Pursuit of Connectomes using High-Resolution Neural EM Data
Venue: arXiv cs.CV 2014
Year: 2014

Accurately estimating the wiring diagram of a brain, known as a connectome, at an ultrastructure level is an open research problem. Specifically, precisely tracking neural processes is difficult, especially across many image slices. Here, we propose a novel method to automatically identify and annotate small subcellular structures present in axons, known as axoplasmic reticula, through a 3D volume of high-resolution neural electron microscopy data. Our method produces high precision annotations, which can help improve automatic segmentation by using our results as seeds for segmentation, and as cues to aid segment merging.
Structured Approach to Web Development
Venue: arXiv cs.SE 2014
Year: 2014

In today's world of Web application development, programmers are commonly called upon to use the Hypertext Markup Language (HTML) as a programming language, something for which it was never intended and for which it is woefully inadequate. HTML is a data language, nothing more. It lacks high level programming constructions like procedures, conditions, and loops. Moreover it provides no intrinsic mechanism to insert or associate dynamic application data. Lastly, despite the visibly apparent structure of a web page when viewed in a browser, the responsible HTML code bears little to no discernible corresponding structure, making it very difficult to read, augment, and maintain. This paper examines the various drawbacks inherent in HTML when used in Web development and examines the various augmenting technologies available in the industry today and their drawbacks. It then proposes an alternative, complete with the necessary constructs, structure, and data associating facilities based upon server-side, Extensible Stylesheet Language Transforms (XSLT). This alternative approach gives rise to an entirely new, higher level, markup language that can be readily used in web development.
Joint Tabling of Logic Program Abductions and Updates
Venue: arXiv cs.AI 2014
Year: 2014

Abductive logic programs offer a formalism to declaratively represent and reason about problems in a variety of areas: diagnosis, decision making, hypothetical reasoning, etc. On the other hand, logic program updates allow us to express knowledge changes, be they internal (or self) and external (or world) changes. Abductive logic programs and logic program updates thus naturally coexist in problems that are susceptible to hypothetical reasoning about change. Taking this as a motivation, in this paper we integrate abductive logic programs and logic program updates by jointly exploiting tabling features of logic programming. The integration is based on and benefits from the two implementation techniques we separately devised previously, viz., tabled abduction and incremental tabling for query-driven propagation of logic program updates. A prototype of the integrated system is implemented in XSB Prolog.
Understanding Shannon's Entropy metric for Information
Venue: arXiv cs.IT 2014
Year: 2014

Shannon's metric of "Entropy" of information is a foundational concept of information theory. This article is a primer for novices that presents an intuitive way of understanding, remembering, and/or reconstructing Shannon's Entropy metric for information.
On Capacity of the Dirty Paper Channel with Fading Dirt in the Strong Fading Regime
Venue: arXiv cs.IT 2014
Year: 2014

The classical writing on dirty paper capacity result establishes that full interference pre-cancellation can be attained in Gelfand-Pinsker problem with additive state and additive white Gaussian noise. This result holds under the idealized assumption that perfect channel knowledge is available at both transmitter and receiver. While channel knowledge at the receiver can be obtained through pilot tones, transmitter channel knowledge is harder to acquire. For this reason, we are interested in characterizing the capacity under the more realistic assumption that only partial channel knowledge is available at the transmitter. We study, more specifically, the dirty paper channel in which the interference sequence in multiplied by fading value unknown to the transmitter but known at the receiver. For this model, we establish an approximate characterization of capacity for the case in which fading values vary greatly in between channel realizations. In this regime, which we term the strong fading regime, the capacity pre-log factor is equal to the inverse of the number of possible fading realizations.
Support for Various HTTP Methods on the Web
Venue: arXiv cs.NI 2014
Year: 2014

We examine how well various HTTP methods are supported by public web services. We sample 40,870 live URIs from the DMOZ collection (a curated directory of World Wide Web URIs) and found that about 55% URIs claim support (in the Allow header) for GET and POST methods, but less than 2% of the URIs claim support for one or more of PUT, PATCH, or DELETE methods.
Hyperspectral pan-sharpening: a variational convex constrained formulation to impose parallel level lines, solved with ADMM
Venue: arXiv cs.CV 2014
Year: 2014

In this paper, we address the issue of hyperspectral pan-sharpening, which consists in fusing a (low spatial resolution) hyperspectral image HX and a (high spatial resolution) panchromatic image P to obtain a high spatial resolution hyperspectral image. The problem is addressed under a variational convex constrained formulation. The objective favors high resolution spectral bands with level lines parallel to those of the panchromatic image. This term is balanced with a total variation term as regularizer. Fit-to-P data and fit-to-HX data constraints are effectively considered as mathematical constraints, which depend on the statistics of the data noise measurements. The developed Alternating Direction Method of Multipliers (ADMM) optimization scheme enables us to solve this problem efficiently despite the non differentiabilities and the huge number of unknowns.
Efficient Reuse of Previous Experiences to Improve Policies in Real Environment
Venue: arXiv cs.RO 2014
Year: 2014

In this study, we show that a movement policy can be improved efficiently using the previous experiences of a real robot. Reinforcement Learning (RL) is becoming a popular approach to acquire a nonlinear optimal policy through trial and error. However, it is considered very difficult to apply RL to real robot control since it usually requires many learning trials. Such trials cannot be executed in real environments because unrealistic time is necessary and the real system's durability is limited. Therefore, in this study, instead of executing many learning trials, we propose to use a recently developed RL algorithm, importance-weighted PGPE, by which the robot can efficiently reuse previously sampled data to improve it's policy parameters. We apply importance-weighted PGPE to CB-i, our real humanoid robot, and show that it can learn a target reaching movement and a cart-pole swing up movement in a real environment without using any prior knowledge of the task or any carefully designed initial trajectory.