OpenRaiser/Intern-Atlas huggingface dataset:
People on Media: Jointly Identifying Credible News and Trustworthy Citizen Journalists in Online Communities
Venue: arXiv cs.AI 2017
Year: 2017

Media seems to have become more partisan, often providing a biased coverage of news catering to the interest of specific groups. It is therefore essential to identify credible information content that provides an objective narrative of an event. News communities such as digg, reddit, or newstrust offer recommendations, reviews, quality ratings, and further insights on journalistic works. However, there is a complex interaction between different factors in such online communities: fairness and style of reporting, language clarity and objectivity, topical perspectives (like political viewpoint), expertise and bias of community members, and more. This paper presents a model to systematically analyze the different interactions in a news community between users, news, and sources. We develop a probabilistic graphical model that leverages this joint interaction to identify 1) highly credible news articles, 2) trustworthy news sources, and 3) expert users who perform the role of "citizen journalists" in the community. Our method extends CRF models to incorporate real-valued ratings, as some communities have very fine-grained scales that cannot be easily discretized without losing information. To the best of our knowledge, this paper is the first full-fledged analysis of credibility, trust, and expertise in news communities.
On the optimality of some group testing algorithms
Venue: arXiv cs.IT 2017
Year: 2017

We consider Bernoulli nonadaptive group testing with $k = Θ(n^θ)$ defectives, for $θ\in (0,1)$. The practical definite defectives (DD) detection algorithm is known to be optimal for $θ\geq 1/2$. We give a new upper bound on the rate of DD, showing that DD is strictly suboptimal for $θ< 0.41$. We also show that the SCOMP algorithm and algorithms based on linear programming achieve a rate at least as high as DD, so in particular are also optimal for $θ\geq 1/2$.
Tiered cloud storage via two-stage, latency-aware bidding
Venue: arXiv cs.NI 2017
Year: 2017

In cloud storage, the digital data is stored in logical storage pools, backed by heterogeneous physical storage media and computing infrastructure that are managed by a Cloud Service Provider (CSP). To balance the tradeoff between service performance and cost, CSPs often employ different storage tiers, for instance, cold storage and hot storage. Storing data in hot storage incurs high storage cost yet delivers low access latency, whereas cold storage is able to inexpensively store massive amounts of data and thus provides lower cost with higher latency. In this paper, we address a major challenge confronting the CSPs utilizing such tiered storage architecture - how to maximize their overall profit over a variety of storage tiers that offer distinct characteristics, as well as file placement and access request scheduling policies. To this end, we propose a scheme where the CSP offers a two-stage auction process for (a) requesting storage capacity, and (b) requesting accesses with latency requirements. Our two-stage bidding scheme provides a hybrid storage and access optimization framework with the objective of maximizing the CSP's total net profit over four dimensions: file acceptance decision, placement of accepted files, file access decision and access request scheduling policy. The proposed optimization is a mixed-integer nonlinear program that is hard to solve. We propose an efficient heuristic to relax the integer optimization and to solve the resulting nonlinear stochastic programs. The algorithm is evaluated under different scenarios and with different storage system parameters, and insightful numerical results are reported by comparing the proposed approach with other profit-maximization models. We see a profit increase of over 60% of our proposed method compared to other schemes in certain simulation scenarios.
Rank Vertex Cover as a Natural Problem for Algebraic Compression
Venue: arXiv cs.DS 2017
Year: 2017

The question of the existence of a polynomial kernelization of the Vertex Cover Above LP problem has been a longstanding, notorious open problem in Parameterized Complexity. Five years ago, the breakthrough work by Kratsch and Wahlstrom on representative sets has finally answered this question in the affirmative [FOCS 2012]. In this paper, we present an alternative, algebraic compression of the Vertex Cover Above LP problem into the Rank Vertex Cover problem. Here, the input consists of a graph G, a parameter k, and a bijection between V (G) and the set of columns of a representation of a matriod M, and the objective is to find a vertex cover whose rank is upper bounded by k.
Geometric Properties of Isostables and Basins of Attraction of Monotone Systems
Venue: arXiv cs.SY 2017
Year: 2017

In this paper, we study geometric properties of basins of attraction of monotone systems. Our results are based on a combination of monotone systems theory and spectral operator theory. We exploit the framework of the Koopman operator, which provides a linear infinite-dimensional description of nonlinear dynamical systems and spectral operator-theoretic notions such as eigenvalues and eigenfunctions. The sublevel sets of the dominant eigenfunction form a family of nested forward-invariant sets and the basin of attraction is the largest of these sets. The boundaries of these sets, called isostables, allow studying temporal properties of the system. Our first observation is that the dominant eigenfunction is increasing in every variable in the case of monotone systems. This is a strong geometric property which simplifies the computation of isostables. We also show how variations in basins of attraction can be bounded under parametric uncertainty in the vector field of monotone systems. Finally, we study the properties of the parameter set for which a monotone system is multistable. Our results are illustrated on several systems of two to four dimensions.
Automated Generation of Non-Linear Loop Invariants Utilizing Hypergeometric Sequences
Venue: arXiv cs.SC 2017
Year: 2017

Analyzing and reasoning about safety properties of software systems becomes an especially challenging task for programs with complex flow and, in particular, with loops or recursion. For such programs one needs additional information, for example in the form of loop invariants, expressing properties to hold at intermediate program points. In this paper we study program loops with non-trivial arithmetic, implementing addition and multiplication among numeric program variables. We present a new approach for automatically generating all polynomial invariants of a class of such programs. Our approach turns programs into linear ordinary recurrence equations and computes closed form solutions of these equations. These closed forms express the most precise inductive property, and hence invariant. We apply Gröbner basis computation to obtain a basis of the polynomial invariant ideal, yielding thus a finite representation of all polynomial invariants. Our work significantly extends the class of so-called P-solvable loops by handling multiplication with the loop counter variable. We implemented our method in the Mathematica package Aligator and showcase the practical use of our approach.
Temporal Segment Networks for Action Recognition in Videos
Venue: arXiv cs.CV 2017
Year: 2017

Deep convolutional networks have achieved great success for image recognition. However, for action recognition in videos, their advantage over traditional methods is not so evident. We present a general and flexible video-level framework for learning action models in videos. This method, called temporal segment network (TSN), aims to model long-range temporal structures with a new segment-based sampling and aggregation module. This unique design enables our TSN to efficiently learn action models by using the whole action videos. The learned models could be easily adapted for action recognition in both trimmed and untrimmed videos with simple average pooling and multi-scale temporal window integration, respectively. We also study a series of good practices for the instantiation of TSN framework given limited training samples. Our approach obtains the state-the-of-art performance on four challenging action recognition benchmarks: HMDB51 (71.0%), UCF101 (94.9%), THUMOS14 (80.1%), and ActivityNet v1.2 (89.6%). Using the proposed RGB difference for motion models, our method can still achieve competitive accuracy on UCF101 (91.0%) while running at 340 FPS. Furthermore, based on the temporal segment networks, we won the video classification track at the ActivityNet challenge 2016 among 24 teams, which demonstrates the effectiveness of TSN and the proposed good practices.
Completely Automated Equivalence Proofs
Venue: arXiv cs.PL 2017
Year: 2017

Verifying partial (i.e., termination-insensitive) equivalence of programs has significant practical applications in software development and education. Conventional equivalence verifiers typically rely on a combination of given relational summaries and suggested synchronization points; such information can be extremely difficult for programmers without a background in formal methods to provide for pairs of programs with dissimilar logic. In this work, we propose a completely automated verifier for determining partial equivalence, named Pequod. Pequod automatically synthesizes expressive proofs of equivalence conventionally only achievable via careful, manual constructions of product programs To do so, Pequod syntheses relational proofs for selected pairs of program paths and combines the per-path relational proofs to synthesize relational program invariants. To evaluate Pequod, we implemented it as a tool that targets Java Virtual Machine bytecode and applied it to verify the equivalence of hundreds of pairs of solutions submitted by students for problems hosted on popular online coding platforms, most of which could not be verified by existing techniques.
Affinity Scheduling and the Applications on Data Center Scheduling with Data Locality
Venue: arXiv cs.DC 2017
Year: 2017

MapReduce framework is the de facto standard in Hadoop. Considering the data locality in data centers, the load balancing problem of map tasks is a special case of affinity scheduling problem. There is a huge body of work on affinity scheduling, proposing heuristic algorithms which try to increase data locality in data centers like Delay Scheduling and Quincy. However, not enough attention has been put on theoretical guarantees on throughput and delay optimality of such algorithms. In this work, we present and compare different algorithms and discuss their shortcoming and strengths. To the best of our knowledge, most data centers are using static load balancing algorithms which are not efficient in any ways and results in wasting the resources and causing unnecessary delays for users.
Discrete Games in Endogenous Networks: Equilibria and Policy
Venue: arXiv cs.SI 2017
Year: 2017

In games of friendship links and behaviors, I propose $k$-player Nash stability---a family of equilibria, indexed by a measure of robustness given by the number of permitted link changes, which is (ordinally and cardinally) ranked in a probabilistic sense. Application of the proposed framework to adolescents' tobacco smoking and friendship decisions suggests that: (a.) friendship networks respond to increases of tobacco prices and this response amplifies the intended policy effect on smoking, (b.) racially desegregating high-schools, via stimulating the social interactions of students with different intrinsic propensity to smoke, decreases the overall smoking prevalence, (c.) adolescents are averse to sharing friends so that there is a rivalry for friendships, (d.) when data on individuals' friendship network is not available, the importance of price centered policy tools is underestimated.
Ad-blocking: A Study on Performance, Privacy and Counter-measures
Venue: arXiv cs.SI 2017
Year: 2017

Many internet ventures rely on advertising for their revenue. However, users feel discontent by the presence of ads on the websites they visit, as the data-size of ads is often comparable to that of the actual content. This has an impact not only on the loading time of webpages, but also on the internet bill of the user in some cases. In absence of a mutually-agreed procedure for opting out of advertisements, many users resort to ad-blocking browser-extensions. In this work, we study the performance of popular ad-blockers on a large set of news websites. Moreover, we investigate the benefits of ad-blockers on user privacy as well as the mechanisms used by websites to counter them. Finally, we explore the traffic overhead due to the ad-blockers themselves.
Detecting Gamification in Breast Cancer Apps: an automatic methodology for screening purposes
Venue: arXiv cs.HC 2017
Year: 2017

Breast cancer is the most common cancer in women both in developed and developing countries. More than half of all cancer mobile application concern breast cancer. Gamification is widely used in mobile software applications created for health-related services. Current prevalence of gamification in breast cancer apps is unknown and detection must be manually performed. The purpose of this study is to describe and produce a tool allowing automatic detection of apps which contain gamification elements and thus empowering researchers to study gamification using large data samples. Predictive logistic regression model was designed on data extracted from breast cancer apps' title and description text available in app stores. Model was validated comparing estimated and benchmark values, observed by gamification specialists. Study's outcome can be applied as a screening tool to efficiently identify gamification presence in breast cancer apps for further research.
A Systematic Review of Hindi Prosody
Venue: arXiv cs.CL 2017
Year: 2017

Prosody describes both form and function of a sentence using the suprasegmental features of speech. Prosody phenomena are explored in the domain of higher phonological constituents such as word, phonological phrase and intonational phrase. The study of prosody at the word level is called word prosody and above word level is called sentence prosody. Word Prosody describes stress pattern by comparing the prosodic features of its constituent syllables. Sentence Prosody involves the study on phrasing pattern and intonatonal pattern of a language. The aim of this study is to summarize the existing works on Hindi prosody carried out in different domain of language and speech processing. The review is presented in a systematic fashion so that it could be a useful resource for one who wants to build on the existing works.
Are You Ready? Towards the Engineering of Forensic-Ready Systems
Venue: arXiv cs.SE 2017
Year: 2017

As security incidents continue to impact organisations, there is a growing demand for systems to be 'forensic ready'- to maximise the potential use of evidence whilst minimising the costs of an investigation. Researchers have supported organisational forensic readiness efforts by proposing the use of policies and processes, aligning systems with forensics objectives and training employees. However, recent work has also proposed an alternative strategy for implementing forensic readiness called forensic-by-design. This is an approach that involves integrating requirements for forensics into relevant phases of the systems development lifecycle with the aim of engineering forensic-ready systems. While this alternative forensic readiness strategy has been discussed in the literature, no previous research has examined the extent to which organisations actually use this approach for implementing forensic readiness. Hence, we investigate the extent to which organisations consider requirements for forensics during systems development. We first assessed existing research to identify the various perspectives of implementing forensic readiness, and then undertook an online survey to investigate the consideration of requirements for forensics during systems development lifecycles. Our findings provide an initial assessment of the extent to which requirements for forensics are considered within organisations. We then use our findings, coupled with the literature, to identify a number of research challenges regarding the engineering of forensic-ready systems.
Diving Performance Assessment by means of Video Processing
Venue: arXiv cs.CV 2017
Year: 2017

The aim of this paper is to present a procedure for video analysis applied in an innovative way to diving performance assessment. Sport performance analysis is a trend that is growing exponentially for all level athletes. The technique here shown is based on two important requirements: flexibility and low cost. These two requirements lead to many problems in the video processing that have been faced and solved in this paper.
Evidence for the size principle in semantic and perceptual domains
Venue: arXiv cs.AI 2017
Year: 2017

Shepard's Universal Law of Generalization offered a compelling case for the first physics-like law in cognitive science that should hold for all intelligent agents in the universe. Shepard's account is based on a rational Bayesian model of generalization, providing an answer to the question of why such a law should emerge. Extending this account to explain how humans use multiple examples to make better generalizations requires an additional assumption, called the size principle: hypotheses that pick out fewer objects should make a larger contribution to generalization. The degree to which this principle warrants similarly law-like status is far from conclusive. Typically, evaluating this principle has not been straightforward, requiring additional assumptions. We present a new method for evaluating the size principle that is more direct, and apply this method to a diverse array of datasets. Our results provide support for the broad applicability of the size principle.
A Note on the Power of Non-Deterministic Circuits with Gate Restrictions
Venue: arXiv cs.CC 2017
Year: 2017

We investigate the power of non-deterministic circuits over restricted sets of base gates. We note that the power of non-deterministic circuits exhibit a dichotomy, in the following sense: For weak enough bases, non-deterministic circuits are no more powerful than deterministic circuits, and for the remaining bases, non-deterministic circuits are super polynomial more efficient than deterministic circuits (under the assumption that $P/poly \neq NP/poly$). Moreover, we give a precise characterization of the borderline between the two situations.
Betweenness and Diversity in Journal Citation Networks as Measures of Interdisciplinarity -- A Tribute to Eugene Garfield --
Venue: arXiv cs.DL 2017
Year: 2017

Journals were central to Eugene Garfield's research interests. Among other things, journals are considered as units of analysis for bibliographic databases such as the Web of Science (WoS) and Scopus. In addition to disciplinary classifications of journals, journal citation patterns span networks across boundaries to variable extents. Using betweenness centrality (BC) and diversity, we elaborate on the question of how to distinguish and rank journals in terms of interdisciplinarity. Interdisciplinarity, however, is difficult to operationalize in the absence of an operational definition of disciplines, the diversity of a unit of analysis is sample-dependent. BC can be considered as a measure of multi-disciplinarity. Diversity of co-citation in a citing document has been considered as an indicator of knowledge integration, but an author can also generate trans-disciplinary--that is, non-disciplined--variation by citing sources from other disciplines. Diversity in the bibliographic coupling among citing documents can analogously be considered as diffusion of knowledge across disciplines. Because the citation networks in the cited direction reflect both structure and variation, diversity in this direction is perhaps the best available measure of interdisciplinarity at the journal level. Furthermore, diversity is based on a summation and can therefore be decomposed, differences among (sub)sets can be tested for statistical significance. In an appendix, a general-purpose routine for measuring diversity in networks is provided.
The Imprecisions of Precision Measures in Process Mining
Venue: arXiv cs.DB 2017
Year: 2017

In process mining, precision measures are used to quantify how much a process model overapproximates the behavior seen in an event log. Although several measures have been proposed throughout the years, no research has been done to validate whether these measures achieve the intended aim of quantifying over-approximation in a consistent way for all models and logs. This paper fills this gap by postulating a number of axioms for quantifying precision consistently for any log and any model. Further, we show through counter-examples that none of the existing measures consistently quantifies precision.
READ-BAD: A New Dataset and Evaluation Scheme for Baseline Detection in Archival Documents
Venue: arXiv cs.CV 2017
Year: 2017

Text line detection is crucial for any application associated with Automatic Text Recognition or Keyword Spotting. Modern algorithms perform good on well-established datasets since they either comprise clean data or simple/homogeneous page layouts. We have collected and annotated 2036 archival document images from different locations and time periods. The dataset contains varying page layouts and degradations that challenge text line segmentation methods. Well established text line segmentation evaluation schemes such as the Detection Rate or Recognition Accuracy demand for binarized data that is annotated on a pixel level. Producing ground truth by these means is laborious and not needed to determine a method's quality. In this paper we propose a new evaluation scheme that is based on baselines. The proposed scheme has no need for binarization and it can handle skewed as well as rotated text lines. The ICDAR 2017 Competition on Baseline Detection and the ICDAR 2017 Competition on Layout Analysis for Challenging Medieval Manuscripts used this evaluation scheme. Finally, we present results achieved by a recently published text line detection algorithm.
Model Complexity-Accuracy Trade-off for a Convolutional Neural Network
Venue: arXiv cs.CV 2017
Year: 2017

Convolutional Neural Networks(CNN) has had a great success in the recent past, because of the advent of faster GPUs and memory access. CNNs are really powerful as they learn the features from data in layers such that they exhibit the structure of the V-1 features of the human brain. A huge bottleneck, in this case, is that CNNs are very large and have a very high memory footprint, and hence they cannot be employed on devices with limited storage such as mobile phone, IoT etc. In this work, we study the model complexity versus accuracy trade-off on MNSIT dataset, and give a concrete framework for handling such a problem, given the worst case accuracy that a system can tolerate. In our work, we reduce the model complexity by 236 times, and memory footprint by 19.5 times compared to the base model while achieving worst case accuracy threshold.