OpenRaiser/Intern-Atlas huggingface dataset:
A comprehensive theory of cascading via-paths and the reciprocal pointer chain method
Venue: arXiv cs.DM 2016
Year: 2016

In this paper, we consolidate and expand upon the current theory and potential applications of the set of $k$ best \emph{cascading via-paths} (CVPs) and the \emph{reciprocal pointer chain} (RPC) method for identifying them. CVPs are a collection of up to $|V|$ paths between a source and a target node in a graph $G = (V,E)$, computed using two shortest path trees, that have distinctive properties relative to other path sets. They have been shown to be particularly useful in geospatial applications, where they are an intuitive and efficient means for identifying a set of spatially diverse alternatives to the single shortest path between the source and target. However, spatial diversity is not intrinsic to paths in a graph, and little theory has been developed outside of application to describe the nature of these paths and the RPC method in general. Here we divorce the RPC method from its typical geospatial applications and develop a comprehensive theory of CVPs from an abstract graph-theoretic perspective. Restricting ourselves to properties of the CVPs and of the entire set of $k$-best CVPs that can be computed in $O(|E| + |V| \log |V|)$, we are able to then propose, among other things, new and efficient approaches to problems such as generating a diverse set of paths and to computing the $k$ shortest loopless paths between two nodes in a graph. We conclude by demonstrating the new theory in practice, first for a typical application of finding alternative routes in road networks and then for a novel application of identifying layer-boundaries in ground-penetrating radar (GPR) data. It is our hope that by generalizing the RPC method, providing a sound theoretical foundation, and demonstrating novel uses, we are able to broaden its perceived applicability and stimulate new research in this area, both applied and theoretical.
LifeJacket: Verifying precise floating-point optimizations in LLVM
Venue: arXiv cs.PL 2016
Year: 2016

Optimizing floating-point arithmetic is vital because it is ubiquitous, costly, and used in compute-heavy workloads. Implementing precise optimizations correctly, however, is difficult, since developers must account for all the esoteric properties of floating-point arithmetic to ensure that their transformations do not alter the output of a program. Manual reasoning is error prone and stifles incorporation of new optimizations. We present an approach to automate reasoning about floating-point optimizations using satisfiability modulo theories (SMT) solvers. We implement the approach in LifeJacket, a system for automatically verifying precise floating-point optimizations for the LLVM assembly language. We have used LifeJacket to verify 43 LLVM optimizations and to discover eight incorrect ones, including three previously unreported problems. LifeJacket is an open source extension of the Alive system for optimization verification.
Partial Face Detection for Continuous Authentication
Venue: arXiv cs.CV 2016
Year: 2016

In this paper, a part-based technique for real time detection of users' faces on mobile devices is proposed. This method is specifically designed for detecting partially cropped and occluded faces captured using a smartphone's front-facing camera for continuous authentication. The key idea is to detect facial segments in the frame and cluster the results to obtain the region which is most likely to contain a face. Extensive experimentation on a mobile dataset of 50 users shows that our method performs better than many state-of-the-art face detection methods in terms of accuracy and processing speed.
Ordinal Conditional Functions for Nearly Counterfactual Revision
Venue: arXiv cs.AI 2016
Year: 2016

We are interested in belief revision involving conditional statements where the antecedent is almost certainly false. To represent such problems, we use Ordinal Conditional Functions that may take infinite values. We model belief change in this context through simple arithmetical operations that allow us to capture the intuition that certain antecedents can not be validated by any number of observations. We frame our approach as a form of finite belief improvement, and we propose a model of conditional belief revision in which only the "right" hypothetical levels of implausibility are revised.
The Open World of Micro-Videos
Venue: arXiv cs.CV 2016
Year: 2016

Micro-videos are six-second videos popular on social media networks with several unique properties. Firstly, because of the authoring process, they contain significantly more diversity and narrative structure than existing collections of video "snippets". Secondly, because they are often captured by hand-held mobile cameras, they contain specialized viewpoints including third-person, egocentric, and self-facing views seldom seen in traditional produced video. Thirdly, due to to their continuous production and publication on social networks, aggregate micro-video content contains interesting open-world dynamics that reflects the temporal evolution of tag topics. These aspects make micro-videos an appealing well of visual data for developing large-scale models for video understanding. We analyze a novel dataset of micro-videos labeled with 58 thousand tags. To analyze this data, we introduce viewpoint-specific and temporally-evolving models for video understanding, defined over state-of-the-art motion and deep visual features. We conclude that our dataset opens up new research opportunities for large-scale video analysis, novel viewpoints, and open-world dynamics.
LSTM based Conversation Models
Venue: arXiv cs.CL 2016
Year: 2016

In this paper, we present a conversational model that incorporates both context and participant role for two-party conversations. Different architectures are explored for integrating participant role and context information into a Long Short-term Memory (LSTM) language model. The conversational model can function as a language model or a language generation model. Experiments on the Ubuntu Dialog Corpus show that our model can capture multiple turn interaction between participants. The proposed method outperforms a traditional LSTM model as measured by language model perplexity and response ranking. Generated responses show characteristic differences between the two participant roles.
An IBE-based Signcryption Scheme for Group Key Management
Venue: arXiv cs.CR 2016
Year: 2016

This paper presents a new crypto scheme whose title promises it to be so boring that no-one will bother reading past the abstract. Because of this, the remainder of the paper is left blank.
Automorphism groups of Gabidulin-like codes
Venue: arXiv cs.IT 2016
Year: 2016

Let K be a cyclic Galois extension of degree f over k and T a generator of the Galois group. For any v=(v_1,... , v_m)\in K^m such that v is linearly independent over k, and any 0< d < m the Gabidulin-like code C(v, T , d) is a maximum rank distance code in the space of f times m matrices over k of dimension fd. This construction unifies the ones available in the literature. We characterise the K-linear codes that are Gabidulin-like codes and determine their rank-metric automorphism group.
On local structures of cubicity 2 graphs
Venue: arXiv cs.DM 2016
Year: 2016

A 2-stab unit interval graph (2SUIG) is an axes-parallel unit square intersection graph where the unit squares intersect either of the two fixed lines parallel to the $X$-axis, distance $1 + ε$ ($0 < ε< 1$) apart. This family of graphs allow us to study local structures of unit square intersection graphs, that is, graphs with cubicity 2. The complexity of determining whether a tree has cubicity 2 is unknown while the graph recognition problem for unit square intersection graph is known to be NP-hard. We present a polynomial time algorithm for recognizing trees that admit a 2SUIG representation.
SciChallenge: Using Student-Generated Content and Contests to Enhance the Interest for Science Education and Careers
Venue: arXiv cs.CY 2016
Year: 2016

Science education will play a vital role in shaping the present and future of modern societies. Thus, Europe needs all its talents to increase creativity and competitiveness. Young boys and girls especially have to be engaged to pursue careers in Science, Technology, Engineering and Mathematics (STEM). However, statistics still show that enrolment rates in STEM-based degree programs are decreasing. This will lead to a workforce problem in the industrial sector as well as in research and development, especially in many of the new member countries. This paper highlights a recently funded EU-research project SciChallenge (www.scichallenge.eu), which focuses on the development of novel concepts to get young people excited about science education. It uses a contest-based approach towards self-produced digital education materials from young people for young people. In cooperation with partner schools, teachers, and other youth-oriented institutions, the contest participants (individuals or groups) between the ages of 10 and 20 years generate creative digital materials (videos, slides, or infographics). The participants upload their content in social media channels and the submissions are aggregated on the SciChallenge Web Platform. The winners receive prizes funded by science-oriented industry and other stakeholders. Intelligent cross-sectoral positioning of various awareness modules on the SciChallenge Open Information Hub is expected to increase awareness on science careers. Through a strong involvement of related organizations and industries, we expect to open new opportunities for young people in regards to internships or taster days in STEM disciplines. Additionally, aggregated information on science events (such as, slams, nights, festivals) is shared. With this multi-level approach, SciChallenge may boost the attractiveness of science education and careers among young people.
Total Variation Applications in Computer Vision
Venue: arXiv cs.CV 2016
Year: 2016

The objectives of this chapter are: (i) to introduce a concise overview of regularization; (ii) to define and to explain the role of a particular type of regularization called total variation norm (TV-norm) in computer vision tasks; (iii) to set up a brief discussion on the mathematical background of TV methods; and (iv) to establish a relationship between models and a few existing methods to solve problems cast as TV-norm. For the most part, image-processing algorithms blur the edges of the estimated images, however TV regularization preserves the edges with no prior information on the observed and the original images. The regularization scalar parameter λ controls the amount of regularization allowed and it is an essential to obtain a high-quality regularized output. A wide-ranging review of several ways to put into practice TV regularization as well as its advantages and limitations are discussed.
Multi-task Recurrent Model for Speech and Speaker Recognition
Venue: arXiv cs.CL 2016
Year: 2016

Although highly correlated, speech and speaker recognition have been regarded as two independent tasks and studied by two communities. This is certainly not the way that people behave: we decipher both speech content and speaker traits at the same time. This paper presents a unified model to perform speech and speaker recognition simultaneously and altogether. The model is based on a unified neural network where the output of one task is fed to the input of the other, leading to a multi-task recurrent network. Experiments show that the joint model outperforms the task-specific models on both the two tasks.
Conformal higher-order remeshing schemes for implicitly defined interface problems
Venue: arXiv cs.NA 2016
Year: 2016

A new higher-order accurate method is proposed that combines the advantages of the classical $p$-version of the FEM on body-fitted meshes with embedded domain methods. A background mesh composed by higher-order Lagrange elements is used. Boundaries and interfaces are described implicitly by the level set method and are within elements. In the elements cut by the boundaries or interfaces, an automatic decomposition into higher-order accurate sub-elements is realized. Therefore, the zero level sets are detected and meshed in a first step which is called reconstruction. Then, based on the topological situation in the cut element, higher-order sub-elements are mapped to the two sides of the boundary or interface. The quality of the reconstruction and the mapping largely determines the properties of the resulting, automatically generated conforming mesh. It is found that optimal convergence rates are possible although the resulting sub-elements are not always well-shaped.
Towards co-designed optimizations in parallel frameworks: A MapReduce case study
Venue: arXiv cs.DC 2016
Year: 2016

The explosion of Big Data was followed by the proliferation of numerous complex parallel software stacks whose aim is to tackle the challenges of data deluge. A drawback of a such multi-layered hierarchical deployment is the inability to maintain and delegate vital semantic information between layers in the stack. Software abstractions increase the semantic distance between an application and its generated code. However, parallel software frameworks contain inherent semantic information that general purpose compilers are not designed to exploit. This paper presents a case study demonstrating how the specific semantic information of the MapReduce paradigm can be exploited on multicore architectures. MR4J has been implemented in Java and evaluated against hand-optimized C and C++ equivalents. The initial observed results led to the design of a semantically aware optimizer that runs automatically without requiring modification to application code. The optimizer is able to speedup the execution time of MR4J by up to 2.0x. The introduced optimization not only improves the performance of the generated code, during the map phase, but also reduces the pressure on the garbage collector. This demonstrates how semantic information can be harnessed without sacrificing sound software engineering practices when using parallel software frameworks.
Modeling Visual Compatibility through Hierarchical Mid-level Elements
Venue: arXiv cs.CV 2016
Year: 2016

In this paper we present a hierarchical method to discover mid-level elements with the objective of modeling visual compatibility between objects. At the base-level, our method identifies patterns of CNN activations with the aim of modeling different variations/styles in which objects of the classes of interest may occur. At the top-level, the proposed method discovers patterns of co-occurring activations of base-level elements that define visual compatibility between pairs of object classes. Experiments on the massive Amazon dataset show the strength of our method at describing object classes and the characteristics that drive the compatibility between them.
The Power of Local Information in PageRank
Venue: arXiv cs.DM 2016
Year: 2016

How large a fraction of a graph must one explore to rank a small set of nodes according to their PageRank scores? We show that the answer is quite nuanced, and depends crucially on the interplay between the correctness guarantees one requires and the way one can access the graph. On the one hand, assuming the graph can be accessed only via "natural" exploration queries that reveal small pieces of its topology, we prove that deterministic and Las Vegas algorithms must in the worst case perform $n - o(n)$ queries and explore essentially the entire graph, independently of the specific types of query employed. On the other hand we show that, depending on the types of query available, Monte Carlo algorithms can perform asymptotically better: if allowed to both explore the local topology around single nodes and access nodes at random in the graph they need $Ω(n^{2/3})$ queries in the worst case, otherwise they still need $Ω(n)$ queries similarly to Las Vegas algorithms. All our bounds generalize and tighten those already known, cover the different types of graph exploration queries appearing in the literature, and immediately apply also to the problem of approximating the PageRank score of single nodes.
Tensor Representations via Kernel Linearization for Action Recognition from 3D Skeletons (Extended Version)
Venue: arXiv cs.CV 2016
Year: 2016

In this paper, we explore tensor representations that can compactly capture higher-order relationships between skeleton joints for 3D action recognition. We first define RBF kernels on 3D joint sequences, which are then linearized to form kernel descriptors. The higher-order outer-products of these kernel descriptors form our tensor representations. We present two different kernels for action recognition, namely (i) a sequence compatibility kernel that captures the spatio-temporal compatibility of joints in one sequence against those in the other, and (ii) a dynamics compatibility kernel that explicitly models the action dynamics of a sequence. Tensors formed from these kernels are then used to train an SVM. We present experiments on several benchmark datasets and demonstrate state of the art results, substantiating the effectiveness of our representations.
The Algorithm of Islamic Jurisprudence (Fiqh) with Validation of an Entscheidungsproblem
Venue: arXiv cs.AI 2016
Year: 2016

The historic background of algorithmic processing with regard to etymology and methodology is translated into terms of mathematical logic and Computer Science. A formal logic structure is introduced by exemplaryquestions posed to Fiqh-chapters to define alogic query language. As a foundation, ageneric algorithm for deciding Fiqh-rulings is designed to enable and further leverage rule of law (vs. rule by law) with full transparency and complete algorithmic coverage of Islamic law eventually providing legal security, legal equality, and full legal accountability.This is implemented by disentangling and reinstating classic Fiqh-methodology (usul al-Fiqh) with the expressive power of subsets of First Order Logic (FOL)sustainably substituting ad hoc reasoning with falsifiable rational argumentation. The results are discussed in formal terms of completeness, decidability and complexity of formal Fiqh-systems. AnEntscheidungsproblem for formal Fiqh-Systems is formulated and validated.
Automated Alertness and Emotion Detection for Empathic Feedback During E-Learning
Venue: arXiv cs.CV 2016
Year: 2016

In the context of education technology, empathic interaction with the user and feedback by the learning system using multiple inputs such as video, voice and text inputs is an important area of research. In this paper, a nonintrusive, standalone model for intelligent assessment of alertness and emotional state as well as generation of appropriate feedback has been proposed. Using the non-intrusive visual cues, the system classifies emotion and alertness state of the user, and provides appropriate feedback according to the detected cognitive state using facial expressions, ocular parameters, postures, and gestures. Assessment of alertness level using ocular parameters such as PERCLOS and saccadic parameters, emotional state from facial expression analysis, and detection of both relevant cognitive and emotional states from upper body gestures and postures has been proposed. Integration of such a system in e-learning environment is expected to enhance students performance through interaction, feedback, and positive mood induction.
The Internet of Things: Perspectives on Security from RFID and WSN
Venue: arXiv cs.NI 2016
Year: 2016

A massive current research effort focuses on combining pre-existing 'Intranets' of Things into one Internet of Things. However, this unification is not a panacea; it will expose new attack surfaces and vectors, just as it enables new applications. We therefore urgently need a model of security in the Internet of Things. In this regard, we note that IoT descends directly from pre-existing research (in embedded Internet and pervasive intelligence), so there exist several bodies of related work: security in RFID, sensor networks, cyber-physical systems, and so on. In this paper, we survey the existing literature on RFID and WSN security, as a step to compiling all known attacks and defenses relevant to the Internet of Things.
Revisiting Summarization Evaluation for Scientific Articles
Venue: arXiv cs.CL 2016
Year: 2016

Evaluation of text summarization approaches have been mostly based on metrics that measure similarities of system generated summaries with a set of human written gold-standard summaries. The most widely used metric in summarization evaluation has been the ROUGE family. ROUGE solely relies on lexical overlaps between the terms and phrases in the sentences; therefore, in cases of terminology variations and paraphrasing, ROUGE is not as effective. Scientific article summarization is one such case that is different from general domain summarization (e.g. newswire data). We provide an extensive analysis of ROUGE's effectiveness as an evaluation metric for scientific summarization; we show that, contrary to the common belief, ROUGE is not much reliable in evaluating scientific summaries. We furthermore show how different variants of ROUGE result in very different correlations with the manual Pyramid scores. Finally, we propose an alternative metric for summarization evaluation which is based on the content relevance between a system generated summary and the corresponding human written summaries. We call our metric SERA (Summarization Evaluation by Relevance Analysis). Unlike ROUGE, SERA consistently achieves high correlations with manual scores which shows its effectiveness in evaluation of scientific article summarization.
Discriminative Phrase Embedding for Paraphrase Identification
Venue: arXiv cs.CL 2016
Year: 2016

This work, concerning paraphrase identification task, on one hand contributes to expanding deep learning embeddings to include continuous and discontinuous linguistic phrases. On the other hand, it comes up with a new scheme TF-KLD-KNN to learn the discriminative weights of words and phrases specific to paraphrase task, so that a weighted sum of embeddings can represent sentences more effectively. Based on these two innovations we get competitive state-of-the-art performance on paraphrase identification.
The AGI Containment Problem
Venue: arXiv cs.AI 2016
Year: 2016

There is considerable uncertainty about what properties, capabilities and motivations future AGIs will have. In some plausible scenarios, AGIs may pose security risks arising from accidents and defects. In order to mitigate these risks, prudent early AGI research teams will perform significant testing on their creations before use. Unfortunately, if an AGI has human-level or greater intelligence, testing itself may not be safe; some natural AGI goal systems create emergent incentives for AGIs to tamper with their test environments, make copies of themselves on the internet, or convince developers and operators to do dangerous things. In this paper, we survey the AGI containment problem - the question of how to build a container in which tests can be conducted safely and reliably, even on AGIs with unknown motivations and capabilities that could be dangerous. We identify requirements for AGI containers, available mechanisms, and weaknesses that need to be addressed.