OpenRaiser/Intern-Atlas huggingface dataset:
Generic-Precision algorithm for DCT-Cordic architectures
Venue: arXiv cs.MM 2016
Year: 2016

In this paper we propose a generic algorithm to calculate the rotation parameters of CORDIC angles required for the Discrete Cosine Transform algorithm (DCT). This leads us to increase the precision of calculation meeting any accuracy.Our contribution is to use this decomposition in CORDIC based DCT which is appropriate for domains which require high quality and top precision. We then propose a hardware implementation of the novel transformation, and as expected, a substantial improvement in PSNR quality is found.
(Almost) Practical Tree Codes
Venue: arXiv cs.IT 2016
Year: 2016

We consider the problem of stabilizing an unstable plant driven by bounded noise over a digital noisy communication link, a scenario at the heart of networked control. To stabilize such a plant, one needs real-time encoding and decoding with an error probability profile that decays exponentially with the decoding delay. The works of Schulman and Sahai over the past two decades have developed the notions of tree codes and anytime capacity, and provided the theoretical framework for studying such problems. Nonetheless, there has been little practical progress in this area due to the absence of explicit constructions of tree codes with efficient encoding and decoding algorithms. Recently, linear time-invariant tree codes were proposed to achieve the desired result under maximum-likelihood decoding. In this work, we take one more step towards practicality, by showing that these codes can be efficiently decoded using sequential decoding algorithms, up to some loss in performance (and with some practical complexity caveats). We supplement our theoretical results with numerical simulations that demonstrate the effectiveness of the decoder in a control system setting.
Shared Secret Places: Social Media and Affordances
Venue: arXiv cs.CY 2016
Year: 2016

The Social Media application Strava is used by exercisers to track running and cycling activities. Strava is carried with the exerciser and displays trophies and leaderboards to reward competitive performance. We were prompted by an auto-ethnographic account of Strava use to examine the way in which a particular stretch of running track around a lake showed up differently to the runner once Strava was integrated into their running practice. We look to Gibsons relational notion of affordances and niches to understand this change in direct perception. We propose that these concepts have potential in helping us to research and understand the ways in which groups of Social Media users share and construct a similar experience of place in a way that is largely invisible to non-users. We consider some of the preliminary implications of this differentiated use of place and demonstrate the way in which a relational view of affordances helps us to make sense of this phenomenon.
Fast Switch Scanning Keyboards: Minimal Expected Query Decision Trees
Venue: arXiv cs.HC 2016
Year: 2016

Augmentative and Alternative Communication (AAC) systems allow people with disabilities to provide input to devices which empower them to more fully interact with their environment. Within AAC, switch scanning is a common paradigm for spelling where a set of characters is highlighted and the user is queried as to whether their target character is in the highlighted set. These queries are used to traverse a decision tree which successively prunes away characters until only a single one remains (the estimate). This work seeks a decision tree which requires the fewest expected queries per decision sequence (EQPD). In particular, we remove the constraint that the decision tree needs to be a row-item or group-row-item style tree and minimize EQPD. We pose the problem as a Huffman code with variable, integer cost and solve it with a mild extension of Golin's method in "A dynamic programming algorithm for constructing optimal prefix-free codes with unequal letter costs", IEEE Transactions on Information Theory (1998). Additionally, we model the user on the query level by their probability of detection and false alarm to derive their expected performance on the character level given some decision tree. We perform experiments which show that the min EQPD decision tree (Karp) may reduce selection times, especially for timed (single switch) switch scanning.
Simplified Boardgames
Venue: arXiv cs.AI 2016
Year: 2016

We formalize Simplified Boardgames language, which describes a subclass of arbitrary board games. The language structure is based on the regular expressions, which makes the rules easily machine-processable while keeping the rules concise and fairly human-readable.
Continuously Learning Neural Dialogue Management
Venue: arXiv cs.CL 2016
Year: 2016

We describe a two-step approach for dialogue management in task-oriented spoken dialogue systems. A unified neural network framework is proposed to enable the system to first learn by supervision from a set of dialogue data and then continuously improve its behaviour via reinforcement learning, all using gradient-based algorithms on one single model. The experiments demonstrate the supervised model's effectiveness in the corpus-based evaluation, with user simulation, and with paid human subjects. The use of reinforcement learning further improves the model's performance in both interactive settings, especially under higher-noise conditions.
SWIFT: Using task-based parallelism, fully asynchronous communication, and graph partition-based domain decomposition for strong scaling on more than 100,000 cores
Venue: arXiv cs.DC 2016
Year: 2016

We present a new open-source cosmological code, called SWIFT, designed to solve the equations of hydrodynamics using a particle-based approach (Smooth Particle Hydrodynamics) on hybrid shared/distributed-memory architectures. SWIFT was designed from the bottom up to provide excellent strong scaling on both commodity clusters (Tier-2 systems) and Top100-supercomputers (Tier-0 systems), without relying on architecture-specific features or specialized accelerator hardware. This performance is due to three main computational approaches: (1) Task-based parallelism for shared-memory parallelism, which provides fine-grained load balancing and thus strong scaling on large numbers of cores. (2) Graph-based domain decomposition, which uses the task graph to decompose the simulation domain such that the work, as opposed to just the data, as is the case with most partitioning schemes, is equally distributed across all nodes. (3) Fully dynamic and asynchronous communication, in which communication is modelled as just another task in the task-based scheme, sending data whenever it is ready and deferring on tasks that rely on data from other nodes until it arrives. In order to use these approaches, the code had to be re-written from scratch, and the algorithms therein adapted to the task-based paradigm. As a result, we can show upwards of 60% parallel efficiency for moderate-sized problems when increasing the number of cores 512-fold, on both x86-based and Power8-based architectures.
Maximum Selection and Sorting with Adversarial Comparators and an Application to Density Estimation
Venue: arXiv cs.DS 2016
Year: 2016

We study maximum selection and sorting of $n$ numbers using pairwise comparators that output the larger of their two inputs if the inputs are more than a given threshold apart, and output an adversarially-chosen input otherwise. We consider two adversarial models. A non-adaptive adversary that decides on the outcomes in advance based solely on the inputs, and an adaptive adversary that can decide on the outcome of each query depending on previous queries and outcomes. Against the non-adaptive adversary, we derive a maximum-selection algorithm that uses at most $2n$ comparisons in expectation, and a sorting algorithm that uses at most $2n \ln n$ comparisons in expectation. These numbers are within small constant factors from the best possible. Against the adaptive adversary, we propose a maximum-selection algorithm that uses $Θ(n\log (1/ε))$ comparisons to output a correct answer with probability at least $1-ε$. The existence of this algorithm affirmatively resolves an open problem of Ajtai, Feldman, Hassadim, and Nelson. Our study was motivated by a density-estimation problem where, given samples from an unknown underlying distribution, we would like to find a distribution in a known class of $n$ candidate distributions that is close to underlying distribution in $\ell_1$ distance. Scheffe's algorithm outputs a distribution at an $\ell_1$ distance at most 9 times the minimum and runs in time $Θ(n^2\log n)$. Using maximum selection, we propose an algorithm with the same approximation guarantee but run time of $Θ(n\log n)$.
e-Commerce product classification: our participation at cDiscount 2015 challenge
Venue: arXiv cs.LG 2016
Year: 2016

This report describes our participation in the cDiscount 2015 challenge where the goal was to classify product items in a predefined taxonomy of products. Our best submission yielded an accuracy score of 64.20\% in the private part of the leaderboard and we were ranked 10th out of 175 participating teams. We followed a text classification approach employing mainly linear models. The final solution was a weighted voting system which combined a variety of trained models.
An automata characterisation for multiple context-free languages
Venue: arXiv cs.FL 2016
Year: 2016

We introduce tree stack automata as a new class of automata with storage and identify a restricted form of tree stack automata that recognises exactly the multiple context-free languages.
Large scale biomedical texts classification: a kNN and an ESA-based approaches
Venue: arXiv cs.IR 2016
Year: 2016

With the large and increasing volume of textual data, automated methods for identifying significant topics to classify textual documents have received a growing interest. While many efforts have been made in this direction, it still remains a real challenge. Moreover, the issue is even more complex as full texts are not always freely available. Then, using only partial information to annotate these documents is promising but remains a very ambitious issue. MethodsWe propose two classification methods: a k-nearest neighbours (kNN)-based approach and an explicit semantic analysis (ESA)-based approach. Although the kNN-based approach is widely used in text classification, it needs to be improved to perform well in this specific classification problem which deals with partial information. Compared to existing kNN-based methods, our method uses classical Machine Learning (ML) algorithms for ranking the labels. Additional features are also investigated in order to improve the classifiers' performance. In addition, the combination of several learning algorithms with various techniques for fixing the number of relevant topics is performed. On the other hand, ESA seems promising for this classification task as it yielded interesting results in related issues, such as semantic relatedness computation between texts and text classification. Unlike existing works, which use ESA for enriching the bag-of-words approach with additional knowledge-based features, our ESA-based method builds a standalone classifier. Furthermore, we investigate if the results of this method could be useful as a complementary feature of our kNN-based approach.ResultsExperimental evaluations performed on large standard annotated datasets, provided by the BioASQ organizers, show that the kNN-based method with the Random Forest learning algorithm achieves good performances compared with the current state-of-the-art methods, reaching a competitive f-measure of 0.55% while the ESA-based approach surprisingly yielded reserved results.ConclusionsWe have proposed simple classification methods suitable to annotate textual documents using only partial information. They are therefore adequate for large multi-label classification and particularly in the biomedical domain. Thus, our work contributes to the extraction of relevant information from unstructured documents in order to facilitate their automated processing. Consequently, it could be used for various purposes, including document indexing, information retrieval, etc.
Procrastination with variable present bias
Venue: arXiv cs.GT 2016
Year: 2016

Individuals working towards a goal often exhibit time inconsistent behavior, making plans and then failing to follow through. One well-known model of such behavioral anomalies is present-bias discounting: individuals over-weight present costs by a bias factor. This model explains many time-inconsistent behaviors, but can make stark predictions in many settings: individuals either follow the most efficient plan for reaching their goal or procrastinate indefinitely. We propose a modification in which the present-bias parameter can vary over time, drawn independently each step from a fixed distribution. Following Kleinberg and Oren (2014), we use a weighted task graph to model task planning, and measure the cost of procrastination as the relative expected cost of the chosen path versus the optimal path. We use a novel connection to optimal pricing theory to describe the structure of the worst-case task graph for any present-bias distribution. We then leverage this structure to derive conditions on the bias distribution under which the worst-case ratio is exponential (in time) or constant. We also examine conditions on the task graph that lead to improved procrastination ratios: graphs with a uniformly bounded distance to the goal, and graphs in which the distance to the goal monotonically decreases on any path.
The Effects of Latency Penalties in Evaluating Push Notification Systems
Venue: arXiv cs.IR 2016
Year: 2016

We examine the effects of different latency penalties in the evaluation of push notification systems, as operationalized in the TREC 2015 Microblog track evaluation. The purpose of this study is to inform the design of metrics for the TREC 2016 Real-Time Summarization track, which is largely modeled after the TREC 2015 evaluation design.
High-Speed Magnetoresistive Random-Access Memory Random Number Generator Using Error-Correcting Code
Venue: arXiv cs.CR 2016
Year: 2016

A high-speed random number generator (RNG) circuit based on magnetoresistive random-access memory (MRAM) using an error-correcting code (ECC) post processing circuit is presented. ECC post processing increases the quality of randomness by increasing the entropy of random number. { We experimentally show that a small error-correcting capability circuit is sufficient for this post processing. It is shown that the ECC post processing circuit powerfully improves the quality of randomness with minimum overhead, ending up with high-speed random number generation. We also show that coupling with a linear feedback shift resistor is effective for improving randomness
Conflict Resolution in Multiple Access Channels Supporting Simultaneous Successful Transmissions
Venue: arXiv cs.DS 2016
Year: 2016

We consider the Conflict Resolution Problem in the context of a multiple-access system in which several stations can transmit their messages simultaneously to the channel. We assume that there are n stations and that at most k<= n stations are active at the same time, i.e, are willing to transmit a message. If in a certain instant at most d<=k active stations transmit to the channel then their messages are successfully transmitted, whereas if more than d active stations transmit simultaneously then their messages are lost. In this latter case we say that a conflict occurs. The present paper investigates non-adaptive conflict resolution algorithms working under the assumption that active stations receive a feedback from the channel that informs them on whether their messages have been successfully transmitted. If a station becomes aware that its message has been correctly sent over the channel then it becomes immediately inactive. The measure to optimize is the number of time slots needed to solve conflicts among all active stations. The fundamental question is whether this measure decreases linearly with the number d of messages that can be simultaneously transmitted with success. We give a positive answer to this question by providing a conflict resolution algorithm that uses a 1/d ratio of the number of time slots used by the optimal conflict resolution algorithm for the case d=1. Moreover, we derive a lower bound on the number of time slots needed to solve conflicts non-adaptively which is within a log (k/d) factor from the upper bound. To this aim, we introduce a new combinatorial structure that consists in a generalization of Komlos and Greenberg codes. Constructions of these new codes are obtained via a new generalization of selectors, whereas the non-existential result is implied by a non-existential result for a new generalization of the locally thin families.
MAC: a novel systematically multilevel cache replacement policy for PCM memory
Venue: arXiv cs.AR 2016
Year: 2016

The rapid development of multi-core system and increase of data-intensive application in recent years call for larger main memory. Traditional DRAM memory can increase its capacity by reducing the feature size of storage cell. Now further scaling of DRAM faces great challenge, and the frequent refresh operations of DRAM can bring a lot of energy consumption. As an emerging technology, Phase Change Memory (PCM) is promising to be used as main memory. It draws wide attention due to the advantages of low power consumption, high density and nonvolatility, while it incurs finite endurance and relatively long write latency. To handle the problem of write, optimizing the cache replacement policy to protect dirty cache block is an efficient way. In this paper, we construct a systematically multilevel structure, and based on it propose a novel cache replacement policy called MAC. MAC can effectively reduce write traffic to PCM memory with low hardware overhead. We conduct simulation experiments on GEM5 to evaluate the performances of MAC and other related works. The results show that MAC performs best in reducing the amount of writes (averagely 25.12%) without increasing the program execution time.
An Application of Network Lasso Optimization For Ride Sharing Prediction
Venue: arXiv cs.CY 2016
Year: 2016

Ride sharing has important implications in terms of environmental, social and individual goals by reducing carbon footprints, fostering social interactions and economizing commuter costs. The ride sharing systems that are commonly available lack adaptive and scalable techniques that can simultaneously learn from the large scale data and predict in real-time dynamic fashion. In this paper, we study such a problem towards a smart city initiative, where a generic ride sharing system is conceived capable of making predictions about ride share opportunities based on the historically recorded data while satisfying real-time ride requests. Underpinning the system is an application of a powerful machine learning convex optimization framework called Network Lasso that uses the Alternate Direction Method of Multipliers (ADMM) optimization for learning and dynamic prediction. We propose an application of a robust and scalable unified optimization framework within the ride sharing case-study. The application of Network Lasso framework is capable of jointly optimizing and clustering different rides based on their spatial and model similarity. The prediction from the framework clusters new ride requests, making accurate price prediction based on the clusters, detecting hidden correlations in the data and allowing fast convergence due to the network topology. We provide an empirical evaluation of the application of ADMM network Lasso on real trip record and simulated data, proving their effectiveness since the mean squared error of the algorithm's prediction is minimized on the test rides.
Deep Directed Generative Models with Energy-Based Probability Estimation
Venue: arXiv cs.LG 2016
Year: 2016

Training energy-based probabilistic models is confronted with apparently intractable sums, whose Monte Carlo estimation requires sampling from the estimated probability distribution in the inner loop of training. This can be approximately achieved by Markov chain Monte Carlo methods, but may still face a formidable obstacle that is the difficulty of mixing between modes with sharp concentrations of probability. Whereas an MCMC process is usually derived from a given energy function based on mathematical considerations and requires an arbitrarily long time to obtain good and varied samples, we propose to train a deep directed generative model (not a Markov chain) so that its sampling distribution approximately matches the energy function that is being trained. Inspired by generative adversarial networks, the proposed framework involves training of two models that represent dual views of the estimated probability distribution: the energy function (mapping an input configuration to a scalar energy value) and the generator (mapping a noise vector to a generated configuration), both represented by deep neural networks.
Defining the optimal level of business benefits within IS/IT projects: Insights from benefit identification practices adopted in an IT Service Management (ITSM) project
Venue: arXiv cs.CY 2016
Year: 2016

The popularity of benefit realization management (BRM) in today's IT-enabled world is fast gaining traction within IT organisations around the world. However, there appears to be limited attention paid to the intra-organisational practice by which benefits are identified. The purpose of this paper is twofold: firstly, to describe and define a practice approach to the identification of benefits that exploits a number of benefit identification methods in an effort to more comprehensively identify IS/IT related benefits that reflect the ongoing organisational investment. Secondly, to underline the importance of this benefit identification process in the context of IT service management (ITSM). This is achieved through a case study of an information technology infrastructure library (ITIL) implementation in a multi-national organization. The case study exposes a pragmatic practice approach of customising such implementations in an effort to achieve a cost effective implementation of IT services that reflects the context and requirements of that specific organisation.
Disruptive Transformation of Enterprise Supply Chain Performance through Strategic Technology-enabled Networking to Improve Business Value
Venue: arXiv cs.CY 2016
Year: 2016

In a dynamically changing world, businesses must transform themselves to survive. Although the necessity for change may be apparent; how to change is not. Learning from the experiences of successful pioneers in a core business function is useful. Procurement is essential for all organisations. It is how organisations acquire assets and inputs including facilities, materials and people. Traditionally, the business objective from procurement was to increase availability and reduce costs. Subsequently, the objective became more tactical. Leading procurement practice today is disruptive; beyond cost to creating value. The strategy for market leaders has also transformed; from competition to collaboration. Technology-enabled business networks are now driving business disruption globally. Through a rigorous field study of two world-class pioneering corporations, this paper explores how disruption is transforming Enterprise Supply Chains. Lessons, contributions and their implications for current IS theory and practice, are discussed.