OpenRaiser/Intern-Atlas huggingface dataset:
A Novel Approach for Human Action Recognition from Silhouette Images
Venue: arXiv cs.CV 2015
Year: 2015

In this paper, a novel human action recognition technique from video is presented. Any action of human is a combination of several micro action sequences performed by one or more body parts of the human. The proposed approach uses spatio-temporal body parts movement (STBPM) features extracted from foreground silhouette of the human objects. The newly proposed STBPM feature estimates the movements of different body parts for any given time segment to classify actions. We also proposed a rule based logic named rule action classifier (RAC), which uses a series of condition action rules based on prior knowledge and hence does not required training to classify any action. Since we don't require training to classify actions, the proposed approach is view independent. The experimental results on publicly available Wizeman and MuHVAi datasets are compared with that of the related research work in terms of accuracy in the human action detection, and proposed technique outperforms the others.
Algebraic Diagonals and Walks: Algorithms, Bounds, Complexity
Venue: arXiv cs.SC 2015
Year: 2015

The diagonal of a multivariate power series F is the univariate power series Diag(F) generated by the diagonal terms of F. Diagonals form an important class of power series; they occur frequently in number theory, theoretical physics and enumerative combinatorics. We study algorithmic questions related to diagonals in the case where F is the Taylor expansion of a bivariate rational function. It is classical that in this case Diag(F) is an algebraic function. We propose an algorithm that computes an annihilating polynomial for Diag(F). We give a precise bound on the size of this polynomial and show that generically, this polynomial is the minimal polynomial and that its size reaches the bound. The algorithm runs in time quasi-linear in this bound, which grows exponentially with the degree of the input rational function. We then address the related problem of enumerating directed lattice walks. The insight given by our study leads to a new method for expanding the generating power series of bridges, excursions and meanders. We show that their first N terms can be computed in quasi-linear complexity in N, without first computing a very large polynomial equation.
A Brief Survey of Image Processing Algorithms in Electrical Capacitance Tomography
Venue: arXiv cs.CV 2015
Year: 2015

To study the fundamental physics of complex multiphase flow systems using advanced measurement techniques, especially the electrical capacitance tomography (ECT) approach, this article carries out an initial literature review of the ECT method from a point of view of signal processing and algorithm design. After introducing the physical laws governing the ECT system, we will focus on various reconstruction techniques that are capable to recover the image of the internal characteristics of a specified region based on the measuring capacitances of multi-electrode sensors surrounding the region. Each technique has its own advantages and limitations, and many algorithms have been examined by simulations or experiments. Future researches in 3D reconstruction and other potential improvements of the system are discussed in the end.
It Takes a Socio-Technical Ecosystem
Venue: arXiv cs.SE 2015
Year: 2015

There are both technical and social issues regarding the design of sustainable scientific software. Scientists want continuously evolving systems that capture the most recent knowledge while developers and architects want sufficiently stable requirements to ensure correctness and efficiency. A socio-technical ecosystem provides the environment in which these issues can be traded off.
Subtree Isomorphism Revisited
Venue: arXiv cs.CC 2015
Year: 2015

The Subtree Isomorphism problem asks whether a given tree is contained in another given tree. The problem is of fundamental importance and has been studied since the 1960s. For some variants, e.g., ordered trees, near-linear time algorithms are known, but for the general case truly subquadratic algorithms remain elusive. Our first result is a reduction from the Orthogonal Vectors problem to Subtree Isomorphism, showing that a truly subquadratic algorithm for the latter refutes the Strong Exponential Time Hypothesis (SETH). In light of this conditional lower bound, we focus on natural special cases for which no truly subquadratic algorithms are known. We classify these cases against the quadratic barrier, showing in particular that: -- Even for binary, rooted trees, a truly subquadratic algorithm refutes SETH. -- Even for rooted trees of depth $O(\log\log{n})$, where $n$ is the total number of vertices, a truly subquadratic algorithm refutes SETH. -- For every constant $d$, there is a constant $ε_d>0$ and a randomized, truly subquadratic algorithm for degree-$d$ rooted trees of depth at most $(1+ ε_d) \log_{d}{n}$. In particular, there is an $O(\min\{ 2.85^h ,n^2 \})$ algorithm for binary trees of depth $h$. Our reductions utilize new "tree gadgets" that are likely useful for future SETH-based lower bounds for problems on trees. Our upper bounds apply a folklore result from randomized decision tree complexity.
Social Network Enhanced Device-to-Device Communication Underlaying Cellular Networks
Venue: arXiv cs.SI 2015
Year: 2015

Device-to-device (D2D) communication has seen as a major technology to overcome the imminent wireless capacity crunch and to enable new application services. In this paper, we propose a social-aware approach for optimizing D2D communication by exploiting two layers: the social network and the physical wireless layers. First we formulate the physical layer D2D network according to users' encounter histories. Subsequently, we propose an approach, based on the so-called Indian Buffet Process, so as to model the distribution of contents in users' online social networks. Given the social relations collected by the Evolved Node B (eNB), we jointly optimize the traffic offloading process in D2D communication. In addition, we give the Chernoff bound and approximated cumulative distribution function (CDF) of the offloaded traffic. In the simulation, we proved the effectiveness of the bound and CDF. The numerical results based on real traces show that the proposed approach offload the traffic of eNB's successfully.
Reinforcement Learning Based Transmission Strategy of Cognitive User in IEEE 802.11 based Networks
Venue: arXiv cs.NI 2015
Year: 2015

Traditional concept of cognitive radio is the coexistence of primary and secondary user in multiplexed manner. we consider the opportunistic channel access scheme in IEEE 802.11 based networks subject to the interference mitigation scenario. According to the protocol rule and due to the constraint of message passing, secondary user is unaware of the exact state of the primary user. In this paper, we have proposed an online algorithm for the secondary which assist determining a backoff counter or the decision of being idle for utilizing the time/frequency slot unoccupied by the primary user. Proposed algorithm is based on conventional reinforcement learning technique namely Q-Learning. Simulation has been conducted in order to prove the strength of this algorithm and also results have been compared with our contemporary solution of this problem where secondary user is aware of some states of primary user.
Shape Complexes in Continuous Max-Flow Hierarchical Multi-Labeling Problems
Venue: arXiv cs.CV 2015
Year: 2015

Although topological considerations amongst multiple labels have been previously investigated in the context of continuous max-flow image segmentation, similar investigations have yet to be made about shape considerations in a general and extendable manner. This paper presents shape complexes for segmentation, which capture more complex shapes by combining multiple labels and super-labels constrained by geodesic star convexity. Shape complexes combine geodesic star convexity constraints with hierarchical label organization, which together allow for more complex shapes to be represented. This framework avoids the use of co-ordinate system warping techniques to convert shape constraints into topological constraints, which may be ambiguous or ill-defined for certain segmentation problems.
Density Evolution Analysis of Spatially Coupled LDPC Codes Over BIAWGN Channel
Venue: arXiv cs.IT 2015
Year: 2015

In this paper, we study the density evolution analysis of spatially coupled low-density parity-check (SC-LDPC) codes over binary input additive white Gaussian noise (BIAWGN) channels under the belief propagation (BP) decoding algorithm. Using reciprocal channel approximation and Gaussian approximation, we propose averaging techniques for the density evolution of SC-LDPC codes over BIAWGN channels. We show that the proposed techniques can closely predict the decoding threshold while offering reduced complexity compared to the existing multi-edge-type density evolution.
Insights from Machine-Learned Diet Success Prediction
Venue: arXiv cs.HC 2015
Year: 2015

To support people trying to lose weight and stay healthy, more and more fitness apps have sprung up including the ability to track both calories intake and expenditure. Users of such apps are part of a wider ``quantified self'' movement and many opt-in to publicly share their logged data. In this paper, we use public food diaries of more than 4,000 long-term active MyFitnessPal users to study the characteristics of a (un-)successful diet. Concretely, we train a machine learning model to predict repeatedly being over or under self-set daily calories goals and then look at which features contribute to the model's prediction. Our findings include both expected results, such as the token ``mcdonalds'' or the category ``dessert'' being indicative for being over the calories goal, but also less obvious ones such as the difference between pork and poultry concerning dieting success, or the use of the ``quick added calories'' functionality being indicative of over-shooting calorie-wise. This study also hints at the feasibility of using such data for more in-depth data mining, e.g., looking at the interaction between consumed foods such as mixing protein- and carbohydrate-rich foods. To the best of our knowledge, this is the first systematic study of public food diaries.
Identifying spatial invasion of pandemics on metapopulation networks via anatomizing arrival history
Venue: arXiv cs.SI 2015
Year: 2015

Spatial spread of infectious diseases among populations via the mobility of humans is highly stochastic and heterogeneous. Accurate forecast/mining of the spread process is often hard to be achieved by using statistical or mechanical models. Here we propose a new reverse problem, which aims to identify the stochastically spatial spread process itself from observable information regarding the arrival history of infectious cases in each subpopulation. We solved the problem by developing an efficient optimization algorithm based on dynamical programming, which comprises three procedures: i, anatomizing the whole spread process among all subpopulations into disjoint componential patches; ii, inferring the most probable invasion pathways underlying each patch via maximum likelihood estimation; iii, recovering the whole process by assembling the invasion pathways in each patch iteratively, without burdens in parameter calibrations and computer simulations. Based on the entropy theory, we introduced an identifiability measure to assess the difficulty level that an invasion pathway can be identified. Results on both artificial and empirical metapopulation networks show the robust performance in identifying actual invasion pathways driving pandemic spread.
An Extension to Hough Transform Based on Gradient Orientation
Venue: arXiv cs.CV 2015
Year: 2015

The Hough transform is one of the most common methods for line detection. In this paper we propose a novel extension of the regular Hough transform. The proposed extension combines the extension of the accumulator space and the local gradient orientation resulting in clutter reduction and yielding more prominent peaks, thus enabling better line identification. We demonstrate benefits in applications such as visual quality inspection and rectangle detection.
Translating Hierarchical Block Diagrams into Composite Predicate Transformers
Venue: arXiv cs.SE 2015
Year: 2015

Simulink is the de facto industrial standard for designing embedded control systems. When dealing with the formal verification of Simulink models, we face the problem of translating the graphical language of Simulink, namely, hierarchical block diagrams (HBDs), into a formalism suitable for verification. In this paper, we study the translation of HBDs into the compositional refinement calculus framework for reactive systems. Specifically, we consider as target language an algebra of atomic predicate transformers to capture basic Simulink blocks (both stateless and stateful), composed in series, in parallel, and in feedback. For a given HBD, there are many possible ways to translate it into a term in this algebra, with different tradeoffs. We explore these tradeoffs, and present three translation algorithms. We report on a prototype implementation of these algorithms in a tool that translates Simulink models into algebra terms implemented in the Isabelle theorem prover. We test our tool on several case studies including a benchmark Simulink model by Toyota. We compare the three translation algorithms, with respect to size and readability of generated terms, simplifiability of the corresponding formulas, and other metrics.
Harmonic and Timbre Analysis of Tabla Strokes
Venue: arXiv cs.SD 2015
Year: 2015

Indian twin drums mainly bayan and dayan (tabla) are the most important percussion instruments in India popularly used for keeping rhythm. It is a twin percussion/drum instrument of which the right hand drum is called dayan and the left hand drum is called bayan. Tabla strokes are commonly called as `bol', constitutes a series of syllables. In this study we have studied the timbre characteristics of nine strokes from each of five different tablas. Timbre parameters were calculated from LTAS of each stroke signals. Study of timbre characteristics is one of the most important deterministic approach for analyzing tabla and its stroke characteristics. Statistical correlations among timbre parameters were measured and also through factor analysis we get to know about the parameters of timbre analysis which are closely related. Tabla strokes have unique harmonic and timbral characteristics at mid frequency range and have no uniqueness at low frequency ranges.
Linear Context-Free Tree Languages and Inverse Homomorphisms
Venue: arXiv cs.FL 2015
Year: 2015

We prove that the class of linear context-free tree languages is not closed under inverse linear tree homomorphisms. The proof is by contradiction: we encode Dyck words into a context-free tree language and prove that its preimage under a certain linear tree homomorphism cannot be generated by any context-free tree grammar. A positive result can still be obtained: the linear monadic context-free tree languages are closed under inverse linear tree homomorphisms.
Hybridization of Interval CP and Evolutionary Algorithms for Optimizing Difficult Problems
Venue: arXiv cs.AI 2015
Year: 2015

The only rigorous approaches for achieving a numerical proof of optimality in global optimization are interval-based methods that interleave branching of the search-space and pruning of the subdomains that cannot contain an optimal solution. State-of-the-art solvers generally integrate local optimization algorithms to compute a good upper bound of the global minimum over each subspace. In this document, we propose a cooperative framework in which interval methods cooperate with evolutionary algorithms. The latter are stochastic algorithms in which a population of candidate solutions iteratively evolves in the search-space to reach satisfactory solutions. Within our cooperative solver Charibde, the evolutionary algorithm and the interval-based algorithm run in parallel and exchange bounds, solutions and search-space in an advanced manner via message passing. A comparison of Charibde with state-of-the-art interval-based solvers (GlobSol, IBBA, Ibex) and NLP solvers (Couenne, BARON) on a benchmark of difficult COCONUT problems shows that Charibde is highly competitive against non-rigorous solvers and converges faster than rigorous solvers by an order of magnitude.
Bad Universal Priors and Notions of Optimality
Venue: arXiv cs.AI 2015
Year: 2015

A big open question of algorithmic information theory is the choice of the universal Turing machine (UTM). For Kolmogorov complexity and Solomonoff induction we have invariance theorems: the choice of the UTM changes bounds only by a constant. For the universally intelligent agent AIXI (Hutter, 2005) no invariance theorem is known. Our results are entirely negative: we discuss cases in which unlucky or adversarial choices of the UTM cause AIXI to misbehave drastically. We show that Legg-Hutter intelligence and thus balanced Pareto optimality is entirely subjective, and that every policy is Pareto optimal in the class of all computable environments. This undermines all existing optimality properties for AIXI. While it may still serve as a gold standard for AI, our results imply that AIXI is a relative theory, dependent on the choice of the UTM.
New Characterization and Efficient Exhaustive Search Algorithm for Elementary Trapping Sets of Variable-Regular LDPC Codes
Venue: arXiv cs.IT 2015
Year: 2015

In this paper, we propose a new characterization for elementary trapping sets (ETSs) of variable-regular low-density parity-check (LDPC) codes. Recently, Karimi and Banihashemi proposed a characterization of ETSs, which was based on viewing an ETS as a layered superset (LSS) of a short cycle in the code's Tanner graph. A notable advantage of LSS characterization is that it corresponds to a simple LSS-based search algorithm that starts from short cycles of the graph and finds the ETSs with LSS structure efficiently. Compared to the LSS-based characterization of Karimi and Banihashemi, which is based on a single LSS expansion technique, the new characterization involves two additional expansion techniques. The introduction of the new techniques mitigates two problems that LSS-based characterization/search suffers from: (1) exhaustiveness, (2) search efficiency. We prove that using the three expansion techniques, any ETS structure can be obtained starting from a simple cycle, no matter how large the size of the structure $a$ or the number of its unsatisfied check nodes $b$ are. We also demonstrate that for the proposed characterization/search to exhaustively cover all the ETS structures within the $(a,b)$ classes with $a \leq a_{max}, b \leq b_{max}$, for any value of $a_{max}$ and $b_{max}$, the length of the short cycles required to be enumerated is less than that of the LSS-based characterization/search. We also prove that the three expansion techniques, proposed here, are the only expansions needed for characterization of ETS structures starting from simple cycles in the graph, if one requires each and every intermediate sub-structure to be an ETS as well. Extensive simulation results are provided to show that, compared to LSS-based search, significant improvement in search speed and memory requirements can be achieved.
Normalization of Relative and Incomplete Temporal Expressions in Clinical Narratives
Venue: arXiv cs.CL 2015
Year: 2015

We analyze the RI-TIMEXes in temporally annotated corpora and propose two hypotheses regarding the normalization of RI-TIMEXes in the clinical narrative domain: the anchor point hypothesis and the anchor relation hypothesis. We annotate the RI-TIMEXes in three corpora to study the characteristics of RI-TMEXes in different domains. This informed the design of our RI-TIMEX normalization system for the clinical domain, which consists of an anchor point classifier, an anchor relation classifier and a rule-based RI-TIMEX text span parser. We experiment with different feature sets and perform error analysis for each system component. The annotation confirmed the hypotheses that we can simplify the RI-TIMEXes normalization task using two multi-label classifiers. Our system achieves anchor point classification, anchor relation classification and rule-based parsing accuracy of 74.68%, 87.71% and 57.2% (82.09% under relaxed matching criteria) respectively on the held-out test set of the 2012 i2b2 temporal relation challenge. Experiments with feature sets reveals some interesting findings such as the verbal tense feature does not inform the anchor relation classification in clinical narratives as much as the tokens near the RI-TIMEX. Error analysis shows that underrepresented anchor point and anchor relation classes are difficult to detect. We formulate the RI-TIMEX normalization problem as a pair of multi-label classification problems. Considering only the RI-TIMEX extraction and normalization, the system achieves statistically significant improvement over the RI-TIMEX results of the best systems in the 2012 i2b2 challenge.
The Rationale for Second Level Adaptation
Venue: arXiv cs.SY 2015
Year: 2015

Recently, a new approach to the adaptive control of linear time-invariant plants with unknown parameters (referred to as second level adaptation), was introduced by Han and Narendra in [1]. Based on $N (\geq m+1)$ fixed or adaptive models of the plant, where $m$ is the dimension of the unknown parameter vector, an unknown parameter vector $α\in R^{N}$ is estimated in the new approach, and in turn, is used to control the overall system. Simulation studies were presented in [1] to demonstrate that the new method is significantly better than those that are currently in use. In this paper, we undertake a more detailed examination of the theoretical and practical advantages claimed for the new method. In particular, the need for many models, the proof of stability, and the improvement in performance and robustness are explored in depth both theoretically and experimentally.
BLASX: A High Performance Level-3 BLAS Library for Heterogeneous Multi-GPU Computing
Venue: arXiv cs.DC 2015
Year: 2015

Basic Linear Algebra Subprograms (BLAS) are a set of low level linear algebra kernels widely adopted by applications involved with the deep learning and scientific computing. The massive and economic computing power brought forth by the emerging GPU architectures drives interest in implementation of compute-intensive level 3 BLAS on multi-GPU systems. In this paper, we investigate existing multi-GPU level 3 BLAS and present that 1) issues, such as the improper load balancing, inefficient communication, insufficient GPU stream level concurrency and data caching, impede current implementations from fully harnessing heterogeneous computing resources; 2) and the inter-GPU Peer-to-Peer(P2P) communication remains unexplored. We then present BLASX: a highly optimized multi-GPU level-3 BLAS. We adopt the concepts of algorithms-by-tiles treating a matrix tile as the basic data unit and operations on tiles as the basic task. Tasks are guided with a dynamic asynchronous runtime, which is cache and locality aware. The communication cost under BLASX becomes trivial as it perfectly overlaps communication and computation across multiple streams during asynchronous task progression. It also takes the current tile cache scheme one step further by proposing an innovative 2-level hierarchical tile cache, taking advantage of inter-GPU P2P communication. As a result, linear speedup is observable with BLASX under multi-GPU configurations; and the extensive benchmarks demonstrate that BLASX consistently outperforms the related leading industrial and academic projects such as cuBLAS-XT, SuperMatrix, MAGMA and PaRSEC.