OpenRaiser/Intern-Atlas huggingface dataset:
Twitter Sentiment Analysis: Lexicon Method, Machine Learning Method and Their Combination
Venue: arXiv cs.CL 2015
Year: 2015

This paper covers the two approaches for sentiment analysis: i) lexicon based method; ii) machine learning method. We describe several techniques to implement these approaches and discuss how they can be adopted for sentiment classification of Twitter messages. We present a comparative study of different lexicon combinations and show that enhancing sentiment lexicons with emoticons, abbreviations and social-media slang expressions increases the accuracy of lexicon-based classification for Twitter. We discuss the importance of feature generation and feature selection processes for machine learning sentiment classification. To quantify the performance of the main sentiment analysis methods over Twitter we run these algorithms on a benchmark Twitter dataset from the SemEval-2013 competition, task 2-B. The results show that machine learning method based on SVM and Naive Bayes classifiers outperforms the lexicon method. We present a new ensemble method that uses a lexicon based sentiment score as input feature for the machine learning approach. The combined method proved to produce more precise classifications. We also show that employing a cost-sensitive classifier for highly unbalanced datasets yields an improvement of sentiment classification performance up to 7%.
RETAIN: a Neonatal Resuscitation Trainer Built in an Undergraduate Video-Game Class
Venue: arXiv cs.CY 2015
Year: 2015

Approximately ten percent of newborns require some help with their breathing at birth. About one percent require extensive assistance at birth which needs to be administered by trained personnel. Neonatal resuscitation is taught through a simulation based training program in North America. Such a training methodology is cost and resource intensive which reduces its availability thereby adversely impacting skill acquisition and retention. We implement and present RETAIN (REsuscitation TrAIning for Neonatal residents) -- a video game to complement the existing neonatal training. Being a video game, RETAIN runs on ubiquitous off-the-shelf hardware and can be easily accessed by trainees almost anywhere at their convenience. Thus we expect RETAIN to help trainees retain and retrain their resuscitation skills. We also report on how RETAIN was developed by an interdisciplinary team of six undergraduate students as a three-month term project for a second year university course.
Unfolding-based Partial Order Reduction
Venue: arXiv cs.LO 2015
Year: 2015

Partial order reduction (POR) and net unfoldings are two alternative methods to tackle state-space explosion caused by concurrency. In this paper, we propose the combination of both approaches in an effort to combine their strengths. We first define, for an abstract execution model, unfolding semantics parameterized over an arbitrary independence relation. Based on it, our main contribution is a novel stateless POR algorithm that explores at most one execution per Mazurkiewicz trace, and in general, can explore exponentially fewer, thus achieving a form of super-optimality. Furthermore, our unfolding-based POR copes with non-terminating executions and incorporates state-caching. Over benchmarks with busy-waits, among others, our experiments show a dramatic reduction in the number of executions when compared to a state-of-the-art DPOR.
Ultra Low-Complexity Detection of Spectrum Holes in Compressed Wideband Spectrum Sensing
Venue: arXiv cs.IT 2015
Year: 2015

Wideband spectrum sensing is a significant challenge in cognitive radios (CRs) due to requiring very high-speed analog- to-digital converters (ADCs), operating at or above the Nyquist rate. Here, we propose a very low-complexity zero-block detection scheme that can detect a large fraction of spectrum holes from the sub-Nyquist samples, even when the undersampling ratio is very small. The scheme is based on a block sparse sensing matrix, which is implemented through the design of a novel analog-to- information converter (AIC). The proposed scheme identifies some measurements as being zero and then verifies the sub-channels associated with them as being vacant. Analytical and simulation results are presented that demonstrate the effectiveness of the proposed method in reliable detection of spectrum holes with complexity much lower than existing schemes. This work also introduces a new paradigm in compressed sensing where one is interested in reliable detection of (some of the) zero blocks rather than the recovery of the whole block sparse signal.
Understanding learning within a commercial video game: A case study
Venue: arXiv cs.CY 2015
Year: 2015

There has been an increasing interest in the debate on the value and relevance using video games for learning. Some of the interest stems from frustration with current educational methods. However, some of this interest also stems from the observations of large numbers of children that play video games. This paper finds that children can learn basic construction skills from playing a video game called World of Goo. The study also employed novel eye-tracking technology to measure endogenous eye blinks and eye gaze fixations. Measures of both these indicators of cognitive processing further suggested that children in the study learned to play the two video games, World of Goo and Bad Piggies. Overall, the results of the study provide further support of the potential for children to learn by playing commercial video games.
Intention-Oriented Process Model Discovery from Incident Management Event Logs
Venue: arXiv cs.SE 2015
Year: 2015

Intention-oriented process mining is based on the belief that the fundamental nature of processes is mostly intentional (unlike activity-oriented process) and aims at discovering strategy and intentional process models from event-logs recorded during the process enactment. In this paper, we present an application of intention-oriented process mining for the domain of incident management of an Information Technology Infrastructure Library (ITIL) process. We apply the Map Miner Method (MMM) on a large real-world dataset for discovering hidden and unobservable user behavior, strategies and intentions. We first discover user strategies from the given activity sequence data by applying Hidden Markov Model (HMM) based unsupervised learning technique. We then process the emission and transition matrices of the discovered HMM to generate a coarse-grained Map Process Model. We present the first application or study of the new and emerging field of Intention-oriented process mining on an incident management event-log dataset and discuss its applicability, effectiveness and challenges.
Graphulo Implementation of Server-Side Sparse Matrix Multiply in the Accumulo Database
Venue: arXiv cs.DB 2015
Year: 2015

The Apache Accumulo database excels at distributed storage and indexing and is ideally suited for storing graph data. Many big data analytics compute on graph data and persist their results back to the database. These graph calculations are often best performed inside the database server. The GraphBLAS standard provides a compact and efficient basis for a wide range of graph applications through a small number of sparse matrix operations. In this article, we implement GraphBLAS sparse matrix multiplication server-side by leveraging Accumulo's native, high-performance iterators. We compare the mathematics and performance of inner and outer product implementations, and show how an outer product implementation achieves optimal performance near Accumulo's peak write rate. We offer our work as a core component to the Graphulo library that will deliver matrix math primitives for graph analytics within Accumulo.
Minimal Logarithmic Signatures for Sporadic Groups
Venue: arXiv cs.CR 2015
Year: 2015

As a special type of factorization of finite groups, logarithmic signature (LS) is used as the main component of cryptographic keys for secret key cryptosystems such as PGM and public key cryptosystems like MST1, MST2 and MST3. An LS with the shortest length is called a minimal logarithmic signature (MLS) and is even desirable for cryptographic constructions. The MLS conjecture states that every finite simple group has an MLS. Until now, the MLS conjecture has been proved true for some families of simple groups. In this paper, we will prove the existence of minimal logarithmic signatures for some sporadic groups.
Falls as anomalies? An experimental evaluation using smartphone accelerometer data
Venue: arXiv cs.SY 2015
Year: 2015

Life expectancy keeps growing and, among elderly people, accidental falls occur frequently. A system able to promptly detect falls would help in reducing the injuries that a fall could cause. Such a system should meet the needs of the people to which is designed, so that it is actually used. In particular, the system should be minimally invasive and inexpensive. Thanks to the fact that most of the smartphones embed accelerometers and powerful processing unit, they are good candidates both as data acquisition devices and as platforms to host fall detection systems. For this reason, in the last years several fall detection methods have been experimented on smartphone accelerometer data. Most of them have been tuned with simulated falls because, to date, datasets of real-world falls are not available. This article evaluates the effectiveness of methods that detect falls as anomalies. To this end, we compared traditional approaches with anomaly detectors. In particular, we experienced the kNN and the SVM methods using both the one-class and two-classes configurations. The comparison involved three different collections of accelerometer data, and four different data representations. Empirical results demonstrated that, in most of the cases, falls are not required to design an effective fall detector.
Empowering Kids to Create and Share Programmable Media
Venue: arXiv cs.CY 2015
Year: 2015

This article reflects on the first eight months of existence of the Scratch Online Community by discussing the design rationale and learning theories underlying Scratch and its website.
Narcotweets: Social Media in Wartime
Venue: arXiv cs.CY 2015
Year: 2015

This paper describes how people living in armed conflict environments use social media as a participatory news platform, in lieu of damaged state and media apparatuses. We investigate this by analyzing the microblogging practices of Mexican citizens whose everyday life is affected by the Drug War. We provide a descriptive analysis of the phenomenon, combining content and quantitative Twitter data analyses. We focus on three interrelated phenomena: general participation patterns of ordinary citizens, the emergence and role of information curators, and the tension between governmental regulation and drug cartel intimidation. This study reveals the complex tensions among citizens, media actors, and the government in light of large scale organized crime.
ScratchR: Sharing User-generated Programmable Media
Venue: arXiv cs.HC 2015
Year: 2015

In this paper, I describe a platform for sharing programmable media on the web called ScratchR. As the backbone of an on-line community of creative learners, ScratchR will give members access to an audience and inspirational ideas from each other. ScratchR seeks to support different states of participation: from passive consumption to active creation. This platform is being evaluated with a group of middle-school students and a larger community of beta testers.
NewsPad: Designing for Collaborative Storytelling in Neighborhoods
Venue: arXiv cs.HC 2015
Year: 2015

This paper introduces design explorations in neighborhood collaborative storytelling. We focus on blogs and citizen journalism, which have been celebrated as a means to meet the reporting needs of small local communities. These bloggers have limited capacity and social media feeds seldom have the context or readability of news stories. We present NewsPad, a content editor that helps communities create structured stories, collaborate in real time, recruit contributors, and syndicate the editing process. We evaluate NewsPad in four pilot deployments and find that the design elicits collaborative story creation.
Approximating (Unweighted) Tree Augmentation via Lift-and-Project, Part II
Venue: arXiv cs.DS 2015
Year: 2015

In Part II, we study the unweighted Tree Augmentation Problem (TAP) via the Lasserre (Sum~of~Squares) system. We prove that the integrality ratio of an SDP relaxation (the Lasserre tightening of an LP relaxation) is $\leq \frac{3}{2}+ε$, where $ε>0$ can be any small constant. We obtain this result by designing a polynomial-time algorithm for TAP that achieves an approximation guarantee of ($\frac32+ε$) relative to the SDP relaxation. The algorithm is combinatorial and does not solve the SDP relaxation, but our analysis relies on the SDP relaxation. We generalize the combinatorial analysis of integral solutions from the previous literature to fractional solutions by identifying some properties of fractional solutions of the Lasserre system via the decomposition result of Karlin, Mathieu and Nguyen (IPCO 2011).
Mudslide: A Spatially Anchored Census of Student Confusion for Online Lecture Videos
Venue: arXiv cs.CY 2015
Year: 2015

Educators have developed an effective technique to get feedback after in-person lectures, called "muddy card." Students are given time to reflect and write the "muddiest" (least clear) point on an index card, to hand in as they leave class. This practice of assigning end-of-lecture reflection tasks to generate explicit student feedback is well suited for adaptation to the challenge of supporting feedback in online video lectures. We describe the design and evaluation of Mudslide, a prototype system that translates the practice of muddy cards into the realm of online lecture videos. Based on an in-lab study of students and teachers, we find that spatially contextualizing students' muddy point feedback with respect to particular lecture slides is advantageous to both students and teachers. We also reflect on further opportunities for enhancing this feedback method based on teachers' and students' experiences with our prototype.
DiffNodesets: An Efficient Structure for Fast Mining Frequent Itemsets
Venue: arXiv cs.DS 2015
Year: 2015

Mining frequent itemsets is an essential problem in data mining and plays an important role in many data mining applications. In recent years, some itemset representations based on node sets have been proposed, which have shown to be very efficient for mining frequent itemsets. In this paper, we propose DiffNodeset, a novel and more efficient itemset representation, for mining frequent itemsets. Based on the DiffNodeset structure, we present an efficient algorithm, named dFIN, to mining frequent itemsets. To achieve high efficiency, dFIN finds frequent itemsets using a set-enumeration tree with a hybrid search strategy and directly enumerates frequent itemsets without candidate generation under some case. For evaluating the performance of dFIN, we have conduct extensive experiments to compare it against with existing leading algorithms on a variety of real and synthetic datasets. The experimental results show that dFIN is significantly faster than these leading algorithms.
Intelligent Data in the context of the internet-of-things
Venue: arXiv cs.CY 2015
Year: 2015

Advent of the Internet-of-Things will allow us to optimize equipment and resource usage, enabling increased efficiencies in automation and enabling new and more cost efficient business model. As tremendous growth opportunities emerge, so do the challenges such as diverse devices spanning across multiple networks, the need to manage the exponential growth of sensor generated data and to make sense of the huge influx of data in meaningful ways. The multitude of diversity can best be addressed by fundamentally opening up systems, architecture and applications. To go the next step and truly exploit the value of the sensor data would further require real-time analytics to gain intelligence and respond to events as they happen. Historical analysis can be used to look for trends, analyze collections of sensor data for correlation and formulate hints and suggestions based on usage and patterns. In this paper, we present a framework that overcomes diversity through its ability to flexibly represent sensor data on the internet. Business goals-driven information processing, information derived intelligence and information control as elements of the framework can further enable creation of new and innovative applications that enhance and exploit the value of Internet-of-Things.
Abstract Interpretation of Supermodular Games
Venue: arXiv cs.GT 2015
Year: 2015

Supermodular games find significant applications in a variety of models, especially in operations research and economic applications of noncooperative game theory, and feature pure strategy Nash equilibria characterized as fixed points of multivalued functions on complete lattices. Pure strategy Nash equilibria of supermodular games are here approximated by resorting to the theory of abstract interpretation, a well established and known framework used for designing static analyses of programming languages. This is obtained by extending the theory of abstract interpretation in order to handle approximations of multivalued functions and by providing some methods for abstracting supermodular games, in order to obtain approximate Nash equilibria which are shown to be correct within the abstract interpretation framework.
Sorting Networks: to the End and Back Again
Venue: arXiv cs.DS 2015
Year: 2015

This paper studies new properties of the front and back ends of a sorting network, and illustrates the utility of these in the search for new bounds on optimal sorting networks. Search focuses first on the "outsides" of the network and then on the inner part. All previous works focus only on properties of the front end of networks and on how to apply these to break symmetries in the search. The new, out-side-in, properties help shed understanding on how sorting networks sort, and facilitate the computation of new bounds on optimal sorting networks. We present new parallel sorting networks for 17 to 20 inputs. For 17, 19, and 20 inputs these networks are faster than the previously known best networks. For 17 inputs, the new sorting network is shown optimal in the sense that no sorting network using less layers exists.
Emphatic Temporal-Difference Learning
Venue: arXiv cs.LG 2015
Year: 2015

Emphatic algorithms are temporal-difference learning algorithms that change their effective state distribution by selectively emphasizing and de-emphasizing their updates on different time steps. Recent works by Sutton, Mahmood and White (2015), and Yu (2015) show that by varying the emphasis in a particular way, these algorithms become stable and convergent under off-policy training with linear function approximation. This paper serves as a unified summary of the available results from both works. In addition, we demonstrate the empirical benefits from the flexibility of emphatic algorithms, including state-dependent discounting, state-dependent bootstrapping, and the user-specified allocation of function approximation resources.
Joint Calibration for Semantic Segmentation
Venue: arXiv cs.CV 2015
Year: 2015

Semantic segmentation is the task of assigning a class-label to each pixel in an image. We propose a region-based semantic segmentation framework which handles both full and weak supervision, and addresses three common problems: (1) Objects occur at multiple scales and therefore we should use regions at multiple scales. However, these regions are overlapping which creates conflicting class predictions at the pixel-level. (2) Class frequencies are highly imbalanced in realistic datasets. (3) Each pixel can only be assigned to a single class, which creates competition between classes. We address all three problems with a joint calibration method which optimizes a multi-class loss defined over the final pixel-level output labeling, as opposed to simply region classification. Our method outperforms the state-of-the-art on the popular SIFT Flow [18] dataset in both the fully and weakly supervised setting by a considerably margin (+6% and +10%, respectively).
Effect of LOS/NLOS Propagation on Ultra-Dense Networks
Venue: arXiv cs.IT 2015
Year: 2015

This paper aims at investigating the achievable performance and the issues that arise in ultra-dense networks (UDNs), when the signal propagation includes both the Line-of-Sight (LOS) and Non-Line-Of-Sight (NLOS) components. Backed by an analytical stochastic geometry-based model, we study the coverage, the Area Spectral Efficiency (ASE) and the energy efficiency of UDNs with LOS/NLOS propagation. We show that when LOS/NLOS propagation components are accounted for, the network suffers from low coverage and the ASE gain is lower than linear at high base station densities. However, this performance drop can partially be attenuated by means of frequency reuse, which is shown to improve the ASE vs coverage trade-off of cell densification, provided that we have a degree of freedom on the density of cells. In addition, from an energy efficiency standpoint, cell densification is shown to be inefficient when both LOS and NLOS components are taken into account. Overall, based on the findings of our work that assumes a more advanced system model compared to the current state-of-the-art, we claim that highly crowded environments of users represent the worst case scenario for ultra-dense networks. Namely, these are likely to face serious issues in terms of limited coverage.
A Reduction from Valued CSP to Min Cost Homomorphism Problem for Digraphs
Venue: arXiv cs.CC 2015
Year: 2015

In a valued constraint satisfaction problem (VCSP), the goal is to find an assignment of labels to variables that minimizes a given sum of functions. Each function in the sum depends on a subset of variables, takes values which are rational numbers or infinity, and is chosen from a fixed finite set of functions called a constraint language. The case when all functions take only values 0 and infinity is known as the constraint satisfaction problem (CSP). It is known that any CSP with fixed constraint language is polynomial-time equivalent to one where the constraint language contains a single binary relation (i.e. a digraph). A recent proof of this by Bulin et al. gives such a reduction that preserves most of the algebraic properties of the constraint language that are known to characterize the complexity of the corresponding CSP. We adapt this proof to the more general setting of VCSP to show that each VCSP with a fixed finite (valued) constraint language is equivalent to one where the constraint language consists of one $\{0,\infty\}$-valued binary function (i.e. a digraph) and one finite-valued unary function, the latter problem known as the (extended) Minimum Cost Homomorphism Problem for digraphs. We also show that our reduction preserves some important algebraic properties of the (valued) constraint language.
Classify Sina Weibo users into High or Low happiness Groups Using Linguistic and Behavior Features
Venue: arXiv cs.SI 2015
Year: 2015

It's of great importance to measure happiness of social network users, but the existing method based on questionnaires suffers from high costs and low efficiency. This paper aims at identifying social network users' happiness level based on their Web behavior. We recruited 548 participants to fill in the Oxford Happiness Inventory (OHI) and divided them into two groups with high/low OHI score. We downloaded each Weibo user's data by calling API, and extracted 103 linguistic and behavior features. 24 features are identified with significant difference between high and low happiness groups. We trained a Decision Tree on these 24 features to make the prediction of high/low happiness group. The decision tree can be used to identify happiness level of any new social network user based on linguistic and behavior features. The Decision Tree can achieve 67.7% on precision. Although the capability of our Decision Tree is not ideal, classifying happiness via linguistic and behavior features on the Internet is proved to be feasible.