OpenRaiser/Intern-Atlas huggingface dataset:
A Comparison of Methods for Cascade Prediction
Venue: arXiv cs.SI 2016
Year: 2016

Information cascades exist in a wide variety of platforms on Internet. A very important real-world problem is to identify which information cascades can go viral. A system addressing this problem can be used in a variety of applications including public health, marketing and counter-terrorism. As a cascade can be considered as compound of the social network and the time series. However, in related literature where methods for solving the cascade prediction problem were proposed, the experimental settings were often limited to only a single metric for a specific problem formulation. Moreover, little attention was paid to the run time of those methods. In this paper, we first formulate the cascade prediction problem as both classification and regression. Then we compare three categories of cascade prediction methods: centrality based, feature based and point process based. We carry out the comparison through evaluation of the methods by both accuracy metrics and run time. The results show that feature based methods can outperform others in terms of prediction accuracy but suffer from heavy overhead especially for large datasets. While point process based methods can also run into issue of long run time when the model can not well adapt to the data. This paper seeks to address issues in order to allow developers of systems for social network analysis to select the most appropriate method for predicting viral information cascades.
Modelling Requirements for Content Recommendation Systems
Venue: arXiv cs.SE 2016
Year: 2016

This paper addresses the modelling of requirements for a content Recommendation System (RS) for Online Social Networks (OSNs). On OSNs, a user switches roles constantly between content generator and content receiver. The goals and softgoals are different when the user is generating a post, as opposed as replying to a post. In other words, the user is generating instances of different entities, depending on the role she has: a generator generates instances of a "post", while the receiver generates instances of a "reply". Therefore, we believe that when addressing Requirements Engineering (RE) for RS, it is necessary to distinguish these roles clearly. We aim to model an essential dynamic on OSN, namely that when a user creates (posts) content, other users can ignore that content, or themselves start generating new content in reply, or react to the initial posting. This dynamic is key to designing OSNs, because it influences how active users are, and how attractive the OSN is for existing, and to new users. We apply a well-known Goal Oriented RE (GORE) technique, namely i-star, and show that this language fails to capture this dynamic, and thus cannot be used alone to model the problem domain. Hence, in order to represent this dynamic, its relationships to other OSNs' requirements, and to capture all relevant information, we suggest using another modelling language, namely Petri Nets, on top of i-star for the modelling of the problem domain. We use Petri Nets because it is a tool that is used to simulate the dynamic and concurrent activities of a system and can be used by both practitioners and theoreticians.
Identifying the Academic Rising Stars
Venue: arXiv cs.DL 2016
Year: 2016

Predicting the fast-rising young researchers (Academic Rising Stars) in the future provides useful guidance to the research community, e.g., offering competitive candidates to university for young faculty hiring as they are expected to have success academic careers. In this work, given a set of young researchers who have published the first first-author paper recently, we solve the problem of how to effectively predict the top k% researchers who achieve the highest citation increment in Δt years. We explore a series of factors that can drive an author to be fast-rising and design a novel impact increment ranking learning (IIRL) algorithm that leverages those factors to predict the academic rising stars. Experimental results on the large ArnetMiner dataset with over 1.7 million authors demonstrate the effectiveness of IIRL. Specifically, it outperforms all given benchmark methods, with over 8% average improvement. Further analysis demonstrates that the prediction models for different research topics follow the similar pattern. We also find that temporal features are the best indicators for rising stars prediction, while venue features are less relevant.
On the Message Dimensions of Vector Linearly Solvable Networks
Venue: arXiv cs.IT 2016
Year: 2016

It is known that there exists a network which does not have a scalar linear solution over any finite field but has a vector linear solution when message dimension is $2$ [3]. It is not known whether this result can be generalized for an arbitrary message dimension. In this paper, we show that there exists a network which admits an $m$ dimensional vector linear solution, where $m$ is a positive integer greater than or equal to $2$, but does not have a vector linear solution over any finite field when the message dimension is less than $m$.
Program Execution on Reconfigurable Multicore Architectures
Venue: arXiv cs.PL 2016
Year: 2016

Based on the two observations that diverse applications perform better on different multicore architectures, and that different phases of an application may have vastly different resource requirements, Pal et al. proposed a novel reconfigurable hardware approach for executing multithreaded programs. Instead of mapping a concurrent program to a fixed architecture, the architecture adaptively reconfigures itself to meet the application's concurrency and communication requirements, yielding significant improvements in performance. Based on our earlier abstract operational framework for multicore execution with hierarchical memory structures, we describe execution of multithreaded programs on reconfigurable architectures that support a variety of clustered configurations. Such reconfiguration may not preserve the semantics of programs due to the possible introduction of race conditions arising from concurrent accesses to shared memory by threads running on the different cores. We present an intuitive partial ordering notion on the cluster configurations, and show that the semantics of multithreaded programs is always preserved for reconfigurations "upward" in that ordering, whereas semantics preservation for arbitrary reconfigurations can be guaranteed for well-synchronised programs. We further show that a simple approximate notion of efficiency of execution on the different configurations can be obtained using the notion of amortised bisimulations, and extend it to dynamic reconfiguration.
Extending Nunchaku to Dependent Type Theory
Venue: arXiv cs.LO 2016
Year: 2016

Nunchaku is a new higher-order counterexample generator based on a sequence of transformations from polymorphic higher-order logic to first-order logic. Unlike its predecessor Nitpick for Isabelle, it is designed as a stand-alone tool, with frontends for various proof assistants. In this short paper, we present some ideas to extend Nunchaku with partial support for dependent types and type classes, to make frontends for Coq and other systems based on dependent type theory more useful.
Extending SMTCoq, a Certified Checker for SMT (Extended Abstract)
Venue: arXiv cs.LO 2016
Year: 2016

This extended abstract reports on current progress of SMTCoq, a communication tool between the Coq proof assistant and external SAT and SMT solvers. Based on a checker for generic first-order certificates implemented and proved correct in Coq, SMTCoq offers facilities both to check external SAT and SMT answers and to improve Coq's automation using such solvers, in a safe way. Currently supporting the SAT solver zChaff, and the SMT solver veriT for the combination of the theories of congruence closure and linear integer arithmetic, SMTCoq is meant to be extendable with a reasonable amount of effort: we present work in progress to support the SMT solver CVC4 and the theory of bit vectors.
Perfect Fingerprint Orientation Fields by Locally Adaptive Global Models
Venue: arXiv cs.CV 2016
Year: 2016

Fingerprint recognition is widely used for verification and identification in many commercial, governmental and forensic applications. The orientation field (OF) plays an important role at various processing stages in fingerprint recognition systems. OFs are used for image enhancement, fingerprint alignment, for fingerprint liveness detection, fingerprint alteration detection and fingerprint matching. In this paper, a novel approach is presented to globally model an OF combined with locally adaptive methods. We show that this model adapts perfectly to the 'true OF' in the limit. This perfect OF is described by a small number of parameters with straightforward geometric interpretation. Applications are manifold: Quick expert marking of very poor quality (for instance latent) OFs, high fidelity low parameter OF compression and a direct road to ground truth OFs markings for large databases, say. In this contribution we describe an algorithm to perfectly estimate OF parameters automatically or semi-automatically, depending on image quality, and we establish the main underlying claim of high fidelity low parameter OF compression.
Relative Natural Gradient for Learning Large Complex Models
Venue: arXiv cs.LG 2016
Year: 2016

Fisher information and natural gradient provided deep insights and powerful tools to artificial neural networks. However related analysis becomes more and more difficult as the learner's structure turns large and complex. This paper makes a preliminary step towards a new direction. We extract a local component of a large neuron system, and defines its relative Fisher information metric that describes accurately this small component, and is invariant to the other parts of the system. This concept is important because the geometry structure is much simplified and it can be easily applied to guide the learning of neural networks. We provide an analysis on a list of commonly used components, and demonstrate how to use this concept to further improve optimization.
Desain dan Implementasi Face Recognition dan Live Streaming pada Sistem Digital Assistant untuk Staf Medik Fungsional menggunakan Google Glass
Venue: arXiv cs.CY 2016
Year: 2016

DIANE is a digital assistant system that aims to fasten the doctor access to various informations at the hospital such as health care facility, medical records, and also human resource data. The fasten access could be achieved by implementing face recognition and live streaming as part of the digital assistant system. By using face recognition, DIANE can identify patient's identity. Moreover, DIANE could know patient's biodata and also patient's medical records. Live streaming in DIANE enables doctor to communicate with other doctors in different place. Through the increasing speed of doctor to access the various informations at the hospital, it is expected that doctor can make decisions more quickly. As a result, more and more patients can be treated by the doctor properly. ---- DIANE merupakan sebuah sistem digital assistant yang bertujuan untuk mempercepat akses staf medik fungsional sebagai seorang profesional dengan waktu terbatas terhadap informasi seperti layanan kesehatan, rekam medis, dan personalia pada SIRS tingkat rumah sakit. Percepatan akses terhadap informasi tersebut diwujudkan melalui penggunaan fitur face recognition dan live streaming. Dengan menggunakan face recognition, DIANE dapat mengidentifikasi pasien sehingga dapat memberikan tampilan data berupa biodata dan rekam medis pasien. Sedangkan menggunakan live streaming pada DIANE, seorang staf medik fungsional dapat berkomunikasi dengan staf medik fungsional di tempat lain. Dengan peningkatan kecepatan akses terhadap beragam informasi tersebut diharapkan seorang staf medik fungsional dapat mengambil keputusan dengan lebih cepat. Akibatnya, semakin banyak pasien yang dapat ditangani oleh staf medik fungsional dengan baik.
LSTM-Based Predictions for Proactive Information Retrieval
Venue: arXiv cs.IR 2016
Year: 2016

We describe a method for proactive information retrieval targeted at retrieving relevant information during a writing task. In our method, the current task and the needs of the user are estimated, and the potential next steps are unobtrusively predicted based on the user's past actions. We focus on the task of writing, in which the user is coalescing previously collected information into a text. Our proactive system automatically recommends the user relevant background information. The proposed system incorporates text input prediction using a long short-term memory (LSTM) network. We present simulations, which show that the system is able to reach higher precision values in an exploratory search setting compared to both a baseline and a comparison system.
Understanding Innovation to Drive Sustainable Development
Venue: arXiv cs.CY 2016
Year: 2016

Innovation is among the key factors driving a country's economic and social growth. But what are the factors that make a country innovative? How do they differ across different parts of the world and different stages of development? In this work done in collaboration with the World Economic Forum (WEF), we analyze the scores obtained through executive opinion surveys that constitute the WEF's Global Competitiveness Index in conjunction with other country-level metrics and indicators to identify actionable levers of innovation. The findings can help country leaders and organizations shape the policies to drive developmental activities and increase the capacity of innovation.
Knowledge-Defined Networking
Venue: arXiv cs.NI 2016
Year: 2016

The research community has considered in the past the application of Artificial Intelligence (AI) techniques to control and operate networks. A notable example is the Knowledge Plane proposed by D.Clark et al. However, such techniques have not been extensively prototyped or deployed in the field yet. In this paper, we explore the reasons for the lack of adoption and posit that the rise of two recent paradigms: Software-Defined Networking (SDN) and Network Analytics (NA), will facilitate the adoption of AI techniques in the context of network operation and control. We describe a new paradigm that accommodates and exploits SDN, NA and AI, and provide use cases that illustrate its applicability and benefits. We also present simple experimental results that support its feasibility. We refer to this new paradigm as Knowledge-Defined Networking (KDN).
An Empirical Comparison of Sampling Quality Metrics: A Case Study for Bayesian Nonnegative Matrix Factorization
Venue: arXiv cs.LG 2016
Year: 2016

In this work, we empirically explore the question: how can we assess the quality of samples from some target distribution? We assume that the samples are provided by some valid Monte Carlo procedure, so we are guaranteed that the collection of samples will asymptotically approximate the true distribution. Most current evaluation approaches focus on two questions: (1) Has the chain mixed, that is, is it sampling from the distribution? and (2) How independent are the samples (as MCMC procedures produce correlated samples)? Focusing on the case of Bayesian nonnegative matrix factorization, we empirically evaluate standard metrics of sampler quality as well as propose new metrics to capture aspects that these measures fail to expose. The aspect of sampling that is of particular interest to us is the ability (or inability) of sampling methods to move between multiple optima in NMF problems. As a proxy, we propose and study a number of metrics that might quantify the diversity of a set of NMF factorizations obtained by a sampler through quantifying the coverage of the posterior distribution. We compare the performance of a number of standard sampling methods for NMF in terms of these new metrics.
An analytical framework to nowcast well-being using mobile phone data
Venue: arXiv cs.CY 2016
Year: 2016

An intriguing open question is whether measurements made on Big Data recording human activities can yield us high-fidelity proxies of socio-economic development and well-being. Can we monitor and predict the socio-economic development of a territory just by observing the behavior of its inhabitants through the lens of Big Data? In this paper, we design a data-driven analytical framework that uses mobility measures and social measures extracted from mobile phone data to estimate indicators for socio-economic development and well-being. We discover that the diversity of mobility, defined in terms of entropy of the individual users' trajectories, exhibits (i) significant correlation with two different socio-economic indicators and (ii) the highest importance in predictive models built to predict the socio-economic indicators. Our analytical framework opens an interesting perspective to study human behavior through the lens of Big Data by means of new statistical indicators that quantify and possibly "nowcast" the well-being and the socio-economic development of a territory.
First Class Call Stacks: Exploring Head Reduction
Venue: arXiv cs.PL 2016
Year: 2016

Weak-head normalization is inconsistent with functional extensionality in the call-by-name $λ$-calculus. We explore this problem from a new angle via the conflict between extensionality and effects. Leveraging ideas from work on the $λ$-calculus with control, we derive and justify alternative operational semantics and a sequence of abstract machines for performing head reduction. Head reduction avoids the problems with weak-head reduction and extensionality, while our operational semantics and associated abstract machines show us how to retain weak-head reduction's ease of implementation.
Command injection attacks, continuations, and the Lambek calculus
Venue: arXiv cs.PL 2016
Year: 2016

This paper shows connections between command injection attacks, continuations, and the Lambek calculus: certain command injections, such as the tautology attack on SQL, are shown to be a form of control effect that can be typed using the Lambek calculus, generalizing the double-negation typing of continuations. Lambek's syntactic calculus is a logic with two implicational connectives taking their arguments from the left and right, respectively. These connectives describe how strings interact with their left and right contexts when building up syntactic structures. The calculus is a form of propositional logic without structural rules, and so a forerunner of substructural logics like Linear Logic and Separation Logic.
Efficient 2D and 3D Facade Segmentation using Auto-Context
Venue: arXiv cs.CV 2016
Year: 2016

This paper introduces a fast and efficient segmentation technique for 2D images and 3D point clouds of building facades. Facades of buildings are highly structured and consequently most methods that have been proposed for this problem aim to make use of this strong prior information. Contrary to most prior work, we are describing a system that is almost domain independent and consists of standard segmentation methods. We train a sequence of boosted decision trees using auto-context features. This is learned using stacked generalization. We find that this technique performs better, or comparable with all previous published methods and present empirical results on all available 2D and 3D facade benchmark datasets. The proposed method is simple to implement, easy to extend, and very efficient at test-time inference.
An Area-Efficient FPGA Overlay using DSP Block based Time-multiplexed Functional Units
Venue: arXiv cs.AR 2016
Year: 2016

Coarse grained overlay architectures improve FPGA design productivity by providing fast compilation and software-like programmability. Throughput oriented spatially configurable overlays typically suffer from area overheads due to the requirement of one functional unit for each compute kernel operation. Hence, these overlays have often been of limited size, supporting only relatively small compute kernels while consuming considerable FPGA resources. This paper examines the possibility of sharing the functional units among kernel operations for reducing area overheads. We propose a linear interconnected array of time-multiplexed FUs as an overlay architecture with reduced instruction storage and interconnect resource requirements, which uses a fully-pipelined, architecture-aware FU design supporting a fast context switching time. The results presented show a reduction of up to 85% in FPGA resource requirements compared to existing throughput oriented overlay architectures, with an operating frequency which approaches the theoretical limit for the FPGA device.
Opportunities for Price Manipulation by Aggregators in Electricity Markets
Venue: arXiv cs.GT 2016
Year: 2016

Aggregators are playing an increasingly crucial role in the integration of renewable generation in power systems. However, the intermittent nature of renewable generation makes market interactions of aggregators difficult to monitor and regulate, raising concerns about potential market manipulation by aggregators. In this paper, we study this issue by quantifying the profit an aggregator can obtain through strategic curtailment of generation in an electricity market. We show that, while the problem of maximizing the benefit from curtailment is hard in general, efficient algorithms exist when the topology of the network is radial (acyclic). Further, we highlight that significant increases in profit are possible via strategic curtailment in practical settings.
Order Invariance on Decomposable Structures
Venue: arXiv cs.LO 2016
Year: 2016

Order-invariant formulas access an ordering on a structure's universe, but the model relation is independent of the used ordering. Order invariance is frequently used for logic-based approaches in computer science. Order-invariant formulas capture unordered problems of complexity classes and they model the independence of the answer to a database query from low-level aspects of databases. We study the expressive power of order-invariant monadic second-order (MSO) and first-order (FO) logic on restricted classes of structures that admit certain forms of tree decompositions (not necessarily of bounded width). While order-invariant MSO is more expressive than MSO and, even, CMSO (MSO with modulo-counting predicates), we show that order-invariant MSO and CMSO are equally expressive on graphs of bounded tree width and on planar graphs. This extends an earlier result for trees due to Courcelle. Moreover, we show that all properties definable in order-invariant FO are also definable in MSO on these classes. These results are applications of a theorem that shows how to lift up definability results for order-invariant logics from the bags of a graph's tree decomposition to the graph itself.
Faster Computation of Path-Width
Venue: arXiv cs.DS 2016
Year: 2016

Tree-width and path-width are widely successful concepts. Many NP-hard problems have efficient solutions when restricted to graphs of bounded tree-width. Many efficient algorithms are based on a tree decomposition. Sometimes the more restricted path decomposition is required. The bottleneck for such algorithms is often the computation of the width and a corresponding tree or path decomposition. For graphs with $n$ vertices and tree-width or path-width $k$, the standard linear time algorithm to compute these decompositions dates back to 1996. Its running time is linear in $n$ and exponential in $k^3$ and not usable in practice. Here we present a more efficient algorithm to compute the path-width and provide a path decomposition. Its running time is $2^{O(k^2)} n$. In the classical algorithm of Bodlaender and Kloks, the path decomposition is computed from a tree decomposition. Here, an optimal path decomposition is computed from a path decomposition of about twice the width. The latter is computed from a constant factor smaller graph.