OpenRaiser/Intern-Atlas huggingface dataset:
The Dynamics of Emotions in Online Interaction
Venue: arXiv cs.HC 2016
Year: 2016

We study the changes in emotional states induced by reading and participating in online discussions, empirically testing a computational model of online emotional interaction. Using principles of dynamical systems, we quantify changes in valence and arousal through subjective reports, as recorded in three independent studies including 207 participants (110 female). In the context of online discussions, the dynamics of valence and arousal are composed of two forces: an internal relaxation towards baseline values independent of the emotional charge of the discussion, and a driving force of emotional states that depends on the content of the discussion. The dynamics of valence show the existence of positive and negative tendencies, while arousal increases when reading emotional content regardless of its polarity. The tendency of participants to take part in the discussion increases with positive arousal. When participating in an online discussion, the content of participants' expression depends on their valence, and their arousal significantly decreases afterwards as a regulation mechanism. We illustrate how these results allow the design of agent-based models to reproduce and analyze emotions in online communities. Our work empirically validates the microdynamics of a model of online collective emotions, bridging online data analysis with research in the laboratory.
Variable-length Non-overlapping Codes
Venue: arXiv cs.IT 2016
Year: 2016

We define a variable-length code having the property that no (non-empty) prefix of each its codeword is a suffix of any other one, and vice versa. This kind of code can be seen as an extension of two well-known codes in literature, called respectively fix-free code and non-overlapping code. In this paper, some constructive algorithms for such codes are presented as well as numerical results about their cardinality.
Popular Conjectures as a Barrier for Dynamic Planar Graph Algorithms
Venue: arXiv cs.DS 2016
Year: 2016

The dynamic shortest paths problem on planar graphs asks us to preprocess a planar graph $G$ such that we may support insertions and deletions of edges in $G$ as well as distance queries between any two nodes $u,v$ subject to the constraint that the graph remains planar at all times. This problem has been extensively studied in both the theory and experimental communities over the past decades and gets solved millions of times every day by companies like Google, Microsoft, and Uber. The best known algorithm performs queries and updates in $\tilde{O}(n^{2/3})$ time, based on ideas of a seminal paper by Fakcharoenphol and Rao [FOCS'01]. A $(1+\varepsilon)$-approximation algorithm of Abraham et al. [STOC'12] performs updates and queries in $\tilde{O}(\sqrt{n})$ time. An algorithm with $O(polylog(n))$ runtime would be a major breakthrough. However, such runtimes are only known for a $(1+\varepsilon)$-approximation in a model where only restricted weight updates are allowed due to Abraham et al. [SODA'16], or for easier problems like connectivity. In this paper, we follow a recent and very active line of work on showing lower bounds for polynomial time problems based on popular conjectures, obtaining the first such results for natural problems in planar graphs. Such results were previously out of reach due to the highly non-planar nature of known reductions and the impossibility of "planarizing gadgets". We introduce a new framework which is inspired by techniques from the literatures on distance labelling schemes and on parameterized complexity. Using our framework, we show that no algorithm for dynamic shortest paths or maximum weight bipartite matching in planar graphs can support both updates and queries in amortized $O(n^{\frac{1}{2}-\varepsilon})$ time, for $\varepsilon>0$, unless the classical APSP problem can be solved in truly subcubic time, [...]
Decidability Results for Multi-objective Stochastic Games
Venue: arXiv cs.GT 2016
Year: 2016

We study stochastic two-player turn-based games in which the objective of one player is to ensure several infinite-horizon total reward objectives, while the other player attempts to spoil at least one of the objectives. The games have previously been shown not to be determined, and an approximation algorithm for computing a Pareto curve has been given. The major drawback of the existing algorithm is that it needs to compute Pareto curves for finite horizon objectives (for increasing length of the horizon), and the size of these Pareto curves can grow unboundedly, even when the infinite-horizon Pareto curve is small. By adapting existing results, we first give an algorithm that computes the Pareto curve for determined games. Then, as the main result of the paper, we show that for the natural class of stopping games and when there are two reward objectives, the problem of deciding whether a player can ensure satisfaction of the objectives with given thresholds is decidable. The result relies on intricate and novel proof which shows that the Pareto curves contain only finitely many points. As a consequence, we get that the two-objective discounted-reward problem for unrestricted class of stochastic games is decidable.
Walrasian's Characterization and a Universal Ascending Auction
Venue: arXiv cs.GT 2016
Year: 2016

We introduce a novel characterization of all Walrasian price vectors in terms of forbidden over- and under demanded sets for monotone gross substitute combinatorial auctions. For ascending and descending auctions we suggest a universal framework for finding the minimum or maximum Walrasian price vectors for monotone gross substitute combinatorial auctions. An ascending (descending) auction is guaranteed to find the minimum (maximum) Walrasian if and only if it follows the suggested framework.
Information encryption in the expert management of strategic uncertainty
Venue: arXiv cs.GT 2016
Year: 2016

Strategic agents in incomplete-information environments have a conflicted relationship with uncertainty: it can keep them unpredictable to their opponents, but it must also be overcome to predict the actions of those opponents. We use a multivariate generalization of information theory to characterize the information processing behavior of strategic reasoning experts. We compare expert and novice poker players --- "sharks" and "fish" --- over 1.75 million hands of online two-player No-Limit Texas Hold'em (NLHE). Comparing the effects of privately known and publicly signaled information on wagering behavior, we find that the behavior of sharks coheres with information that emerges only from the interaction of public and private sources --- "synergistic" information that does not exist in either source alone. This implies that the effect of public information on shark behavior is better encrypted: it cannot be reconstructed without access to the hidden state of private cards. Integrative information processing affects not only one's own strategic behavior, but the ability of others to predict it. By characterizing the informational structure of complex strategic interactions, we offer a detailed account of how experts extract, process, and conceal valuable information in high-uncertainty, high-stakes competitive environments.
Support Vector Algorithms for Optimizing the Partial Area Under the ROC Curve
Venue: arXiv cs.LG 2016
Year: 2016

The area under the ROC curve (AUC) is a widely used performance measure in machine learning. Increasingly, however, in several applications, ranging from ranking to biometric screening to medicine, performance is measured not in terms of the full area under the ROC curve, but in terms of the \emph{partial} area under the ROC curve between two false positive rates. In this paper, we develop support vector algorithms for directly optimizing the partial AUC between any two false positive rates. Our methods are based on minimizing a suitable proxy or surrogate objective for the partial AUC error. In the case of the full AUC, one can readily construct and optimize convex surrogates by expressing the performance measure as a summation of pairwise terms. The partial AUC, on the other hand, does not admit such a simple decomposable structure, making it more challenging to design and optimize (tight) convex surrogates for this measure. Our approach builds on the structural SVM framework of Joachims (2005) to design convex surrogates for partial AUC, and solves the resulting optimization problem using a cutting plane solver. Unlike the full AUC, where the combinatorial optimization needed in each iteration of the cutting plane solver can be decomposed and solved efficiently, the corresponding problem for the partial AUC is harder to decompose. One of our main contributions is a polynomial time algorithm for solving the combinatorial optimization problem associated with partial AUC. We also develop an approach for optimizing a tighter non-convex hinge loss based surrogate for the partial AUC using difference-of-convex programming. Our experiments on a variety of real-world and benchmark tasks confirm the efficacy of the proposed methods.
A Relatively Small Turing Machine Whose Behavior Is Independent of Set Theory
Venue: arXiv cs.FL 2016
Year: 2016

Since the definition of the Busy Beaver function by Rado in 1962, an interesting open question has been the smallest value of n for which BB(n) is independent of ZFC set theory. Is this n approximately 10, or closer to 1,000,000, or is it even larger? In this paper, we show that it is at most 7,910 by presenting an explicit description of a 7,910-state Turing machine Z with 1 tape and a 2-symbol alphabet that cannot be proved to run forever in ZFC (even though it presumably does), assuming ZFC is consistent. The machine is based on the work of Harvey Friedman on independent statements involving order-invariant graphs. In doing so, we give the first known upper bound on the highest provable Busy Beaver number in ZFC. To create Z, we develop and use a higher-level language, Laconic, which is much more convenient than direct state manipulation. We also use Laconic to design two Turing machines, G and R, that halt if and only if there are counterexamples to Goldbach's Conjecture and the Riemann Hypothesis, respectively.
An Efficient Synthesis Algorithm for Parametric Markov Chains Against Linear Time Properties
Venue: arXiv cs.LO 2016
Year: 2016

In this paper, we propose an efficient algorithm for the parameter synthesis of PLTL formulas with respect to parametric Markov chains. The PLTL formula is translated to an almost fully partitioned Büchi automaton which is then composed with the parametric Markov chain. We then reduce the problem to solving an optimisation problem, allowing to decide the satisfaction of the formula using an SMT solver. The algorithm works also for interval Markov chains. The complexity is linear in the size of the Markov chain, and exponential in the size of the formula. We provide a prototype and show the efficiency of our approach on a number of benchmarks.
RLZAP: Relative Lempel-Ziv with Adaptive Pointers
Venue: arXiv cs.DS 2016
Year: 2016

Relative Lempel-Ziv (RLZ) is a popular algorithm for compressing databases of genomes from individuals of the same species when fast random access is desired. With Kuruppu et al.'s (SPIRE 2010) original implementation, a reference genome is selected and then the other genomes are greedily parsed into phrases exactly matching substrings of the reference. Deorowicz and Grabowski (Bioinformatics, 2011) pointed out that letting each phrase end with a mismatch character usually gives better compression because many of the differences between individuals' genomes are single-nucleotide substitutions. Ferrada et al. (SPIRE 2014) then pointed out that also using relative pointers and run-length compressing them usually gives even better compression. In this paper we generalize Ferrada et al.'s idea to handle well also short insertions, deletions and multi-character substitutions. We show experimentally that our generalization achieves better compression than Ferrada et al.'s implementation with comparable random-access times.
Large-scale Analysis of Counseling Conversations: An Application of Natural Language Processing to Mental Health
Venue: arXiv cs.CL 2016
Year: 2016

Mental illness is one of the most pressing public health issues of our time. While counseling and psychotherapy can be effective treatments, our knowledge about how to conduct successful counseling conversations has been limited due to lack of large-scale data with labeled outcomes of the conversations. In this paper, we present a large-scale, quantitative study on the discourse of text-message-based counseling conversations. We develop a set of novel computational discourse analysis methods to measure how various linguistic aspects of conversations are correlated with conversation outcomes. Applying techniques such as sequence-based conversation models, language model comparisons, message clustering, and psycholinguistics-inspired word frequency analyses, we discover actionable conversation strategies that are associated with better conversation outcomes.
Gabor Barcodes for Medical Image Retrieval
Venue: arXiv cs.CV 2016
Year: 2016

In recent years, advances in medical imaging have led to the emergence of massive databases, containing images from a diverse range of modalities. This has significantly heightened the need for automated annotation of the images on one side, and fast and memory-efficient content-based image retrieval systems on the other side. Binary descriptors have recently gained more attention as a potential vehicle to achieve these goals. One of the recently introduced binary descriptors for tagging of medical images are Radon barcodes (RBCs) that are driven from Radon transform via local thresholding. Gabor transform is also a powerful transform to extract texture-based information. Gabor features have exhibited robustness against rotation, scale, and also photometric disturbances, such as illumination changes and image noise in many applications. This paper introduces Gabor Barcodes (GBCs), as a novel framework for the image annotation. To find the most discriminative GBC for a given query image, the effects of employing Gabor filters with different parameters, i.e., different sets of scales and orientations, are investigated, resulting in different barcode lengths and retrieval performances. The proposed method has been evaluated on the IRMA dataset with 193 classes comprising of 12,677 x-ray images for indexing, and 1,733 x-rays images for testing. A total error score as low as $351$ ($\approx 80\%$ accuracy for the first hit) was achieved.
A Proposal for Linguistic Similarity Datasets Based on Commonality Lists
Venue: arXiv cs.CL 2016
Year: 2016

Similarity is a core notion that is used in psychology and two branches of linguistics: theoretical and computational. The similarity datasets that come from the two fields differ in design: psychological datasets are focused around a certain topic such as fruit names, while linguistic datasets contain words from various categories. The later makes humans assign low similarity scores to the words that have nothing in common and to the words that have contrast in meaning, making similarity scores ambiguous. In this work we discuss the similarity collection procedure for a multi-category dataset that avoids score ambiguity and suggest changes to the evaluation procedure to reflect the insights of psychological literature for word, phrase and sentence similarity. We suggest to ask humans to provide a list of commonalities and differences instead of numerical similarity scores and employ the structure of human judgements beyond pairwise similarity for model evaluation. We believe that the proposed approach will give rise to datasets that test meaning representation models more thoroughly with respect to the human treatment of similarity.
Fast and Accurate Performance Analysis of LTE Radio Access Networks
Venue: arXiv cs.DC 2016
Year: 2016

An increasing amount of analytics is performed on data that is procured in a real-time fashion to make real-time decisions. Such tasks include simple reporting on streams to sophisticated model building. However, the practicality of such analyses are impeded in several domains because they are faced with a fundamental trade-off between data collection latency and analysis accuracy. In this paper, we study this trade-off in the context of a specific domain, Cellular Radio Access Networks (RAN). Our choice of this domain is influenced by its commonalities with several other domains that produce real-time data, our access to a large live dataset, and their real-time nature and dimensionality which makes it a natural fit for a popular analysis technique, machine learning (ML). We find that the latency accuracy trade-off can be resolved using two broad, general techniques: intelligent data grouping and task formulations that leverage domain characteristics. Based on this, we present CellScope, a system that addresses this challenge by applying a domain specific formulation and application of Multi-task Learning (MTL) to RAN performance analysis. It achieves this goal using three techniques: feature engineering to transform raw data into effective features, a PCA inspired similarity metric to group data from geographically nearby base stations sharing performance commonalities, and a hybrid online-offline model for efficient model updates. Our evaluation of CellScope shows that its accuracy improvements over direct application of ML range from 2.5x to 4.4x while reducing the model update overhead by up to 4.8x. We have also used CellScope to analyze a live LTE consisting of over 2 million subscribers for a period of over 10 months, where it uncovered several problems and insights, some of them previously unknown.
High-Performance Computing for Scheduling Decision Support: A Parallel Depth-First Search Heuristic
Venue: arXiv cs.DC 2016
Year: 2016

Many academic disciplines - including information systems, computer science, and operations management - face scheduling problems as important decision making tasks. Since many scheduling problems are NP-hard in the strong sense, there is a need for developing solution heuristics. For scheduling problems with setup times on unrelated parallel machines, there is limited research on solution methods and to the best of our knowledge, parallel computer architectures have not yet been taken advantage of. We address this gap by proposing and implementing a new solution heuristic and by testing different parallelization strategies. In our computational experiments, we show that our heuristic calculates near-optimal solutions even for large instances and that computing time can be reduced substantially by our parallelization approach.
On Avoidance Learning with Partial Observability
Venue: arXiv cs.AI 2016
Year: 2016

We study a framework where agents have to avoid aversive signals. The agents are given only partial information, in the form of features that are projections of task states. Additionally, the agents have to cope with non-determinism, defined as unpredictability on the way that actions are executed. The goal of each agent is to define its behavior based on feature-action pairs that reliably avoid aversive signals. We study a learning algorithm, called A-learning, that exhibits fixpoint convergence, where the belief of the allowed feature-action pairs eventually becomes fixed. A-learning is parameter-free and easy to implement.
A Design Science Method for Emerging Decision Support Environments
Venue: arXiv cs.CY 2016
Year: 2016

Emerging technologies and business models require organisations to continuously deal with complex, dynamic and unstructured issues, leading to the need for newer forms of decision support systems (DSS). However, in emerging environments the existing knowledge base can be scattered, unstructured, and sometimes conflicting, which challenges any efforts in designing DSS. This paper highlights the role of design science methods in developing these emerging areas, and suggests a design science method that focuses on consolidating the knowledge base by ontologically grounding experience and expertise. The proposed method is illustrated in the context of a published case, and validated by practically applying it to develop a crowdsourcing decision tool. The study contributes with recommendations on how to consolidate the knowledge base and design DSS artefacts.
CNN based texture synthesize with Semantic segment
Venue: arXiv cs.CV 2016
Year: 2016

Deep learning algorithm display powerful ability in Computer Vision area, in recent year, the CNN has been applied to solve problems in the subarea of Image-generating, which has been widely applied in areas such as photo editing, image design, computer animation, real-time rendering for large scale of scenes and for visual effects in movies. However in the texture synthesize procedure. The state-of-art CNN can not capture the spatial location of texture in image, lead to significant distortion after texture synthesize, we propose a new way to generating-image by adding the semantic segment step with deep learning algorithm as Pre-Processing and analyze the outcome.
Simulation of the Internet of Things
Venue: arXiv cs.NI 2016
Year: 2016

This paper presents main concepts and issues concerned with the simulation of Internet of Things (IoT). The heterogeneity of possible scenarios, arising from the massive deployment of an enormous amount of sensors and devices, imposes the use of sophisticated modeling and simulation techniques. In fact, the simulation of IoT introduces several issues from both quantitative and qualitative aspects. We discuss novel simulation techniques to enhance scalability and to permit the real-time execution of massively populated IoT environments (e.g., large-scale smart cities). In particular, we claim that agent-based, adaptive Parallel and Distributed Simulation (PADS) approaches are needed, together with multi-level simulation, which provide means to perform highly detailed simulations, on demand. We present a use case concerned with the simulation of smart territories.
Multi-Parametric Statistical Method for Estimation of Accumulated Fatigue by Sensors in Ordinary Gadgets
Venue: arXiv cs.CE 2016
Year: 2016

The new method is proposed to monitor the level of currently accumulated fatigue and estimate it by the several statistical methods. The experimental software application was developed and used to get data from sensors (accelerometer, GPS, gyroscope, magnetometer, and camera), conducted experiments, collected data, calculated parameters of their distributions (mean, standard deviation, skewness, kurtosis), and analyzed them by statistical methods (moment analysis, cluster analysis, bootstrapping, periodogram and spectrogram analyses). The hypothesis 1 (physical activity can be estimated and classified by moment and cluster analysis) and hypothesis 2 (fatigue can be estimated by moment analysis, bootstrapping analysis, periodogram, and spectrogram) were proposed and proved. Several "fatigue metrics" were proposed: location, size, shape of clouds of points on bootstrapping plot. The most promising fatigue metrics is the distance from the "rest" state point to the "fatigue" state point (sum of 3 squared non-normal distribution of non-correlated acceleration values) on the skewness-kurtosis plot. These hypotheses were verified on several persons of various age, gender, fitness level and improved standard statistical methods in similar researches. The method can be used in practice for ordinary people in everyday situations (to estimate their fatigue, give tips about it and advice on context-related information).