OpenRaiser/Intern-Atlas huggingface dataset:
Stride Length Estimation with Deep Learning
Venue: arXiv cs.LG 2017
Year: 2017

Accurate estimation of spatial gait characteristics is critical to assess motor impairments resulting from neurological or musculoskeletal disease. Currently, however, methodological constraints limit clinical applicability of state-of-the-art double integration approaches to gait patterns with a clear zero-velocity phase. We describe a novel approach to stride length estimation that uses deep convolutional neural networks to map stride-specific inertial sensor data to the resulting stride length. The model is trained on a publicly available and clinically relevant benchmark dataset consisting of 1220 strides from 101 geriatric patients. Evaluation is done in a 10-fold cross validation and for three different stride definitions. Even though best results are achieved with strides defined from mid-stance to mid-stance with average accuracy and precision of 0.01 $\pm$ 5.37 cm, performance does not strongly depend on stride definition. The achieved precision outperforms state-of-the-art methods evaluated on this benchmark dataset by 3.0 cm (36%). Due to the independence of stride definition, the proposed method is not subject to the methodological constrains that limit applicability of state-of-the-art double integration methods. Furthermore, precision on the benchmark dataset could be improved. With more precise mobile stride length estimation, new insights to the progression of neurological disease or early indications might be gained. Due to the independence of stride definition, previously uncharted diseases in terms of mobile gait analysis can now be investigated by re-training and applying the proposed method.
Longest Common Subsequence in at Least $k$ Length Order-Isomorphic Substrings
Venue: arXiv cs.DS 2017
Year: 2017

We consider the longest common subsequence (LCS) problem with the restriction that the common subsequence is required to consist of at least $k$ length substrings. First, we show an $O(mn)$ time algorithm for the problem which gives a better worst-case running time than existing algorithms, where $m$ and $n$ are lengths of the input strings. Furthermore, we mainly consider the LCS in at least $k$ length order-isomorphic substrings problem. We show that the problem can also be solved in $O(mn)$ worst-case time by an easy-to-implement algorithm.
Social Learning over Weakly-Connected Graphs
Venue: arXiv cs.SI 2017
Year: 2017

In this paper, we study diffusion social learning over weakly-connected graphs. We show that the asymmetric flow of information hinders the learning abilities of certain agents regardless of their local observations. Under some circumstances that we clarify in this work, a scenario of total influence (or "mind-control") arises where a set of influential agents ends up shaping the beliefs of non-influential agents. We derive useful closed-form expressions that characterize this influence, and which can be used to motivate design problems to control it. We provide simulation examples to illustrate the results.
Real-time testbed for diversity in powerline and wireless smart grid communications
Venue: arXiv cs.IT 2017
Year: 2017

Two-way communication is a key feature in a smart grid. It is enabled by either powerline communication or wireless communication technologies. Utilizing both technologies can potentially enhance communication reliability, and many diversity combining schemes have been proposed. In this paper, we propose a flexible real-time testbed to evaluate diversity combining schemes over physical channels. The testbed provides essential parts of physical layers on which both powerline and wireless communications operate. The contributions of this paper are 1) design and implementation of a real-time testbed for diversity of simultaneous powerline and wireless communications, 2) release of the setup information and complete source code for the testbed, and 3) performance evaluation of maximal ratio combining (MRC) on the testbed. As initial results, we show that performance of MRC from measurements obtained on the testbed over physical channels is very close to that in simulations in various test cases under a controlled laboratory environment.
"Flow Size Difference" Can Make a Difference: Detecting Malicious TCP Network Flows Based on Benford's Law
Venue: arXiv cs.CR 2017
Year: 2017

Statistical characteristics of network traffic have attracted a significant amount of research for automated network intrusion detection, some of which looked at applications of natural statistical laws such as Zipf's law, Benford's law and the Pareto distribution. In this paper, we present the application of Benford's law to a new network flow metric "flow size difference", which have not been studied before by other researchers, to build an unsupervised flow-based intrusion detection system (IDS). The method was inspired by our observation on a large number of TCP flow datasets where normal flows tend to follow Benford's law closely but malicious flows tend to deviate significantly from it. The proposed IDS is unsupervised, so it can be easily deployed without any training. It has two simple operational parameters with a clear semantic meaning, allowing the IDS operator to set and adapt their values intuitively to adjust the overall performance of the IDS. We tested the proposed IDS on two (one closed and one public) datasets, and proved its efficiency in terms of AUC (area under the ROC curve). Our work showed the "flow size difference" has a great potential to improve the performance of any flow-based network IDSs.
Polymorphisms and Circuit Complexity
Venue: arXiv cs.CC 2017
Year: 2017

We present a framework for studying circuit complexity that is inspired by techniques that are used for analyzing the complexity of CSPs. We prove that the circuit complexity of a Boolean function $f$ is characterized by the partial polymorphisms of $f$'s truth table. Moreover, the non-deterministic circuit complexity of $f$ is characterized by the polymorphisms of $f$'s truth table.
Coherence Pursuit: Fast, Simple, and Robust Principal Component Analysis
Venue: arXiv cs.LG 2017
Year: 2017

This paper presents a remarkably simple, yet powerful, algorithm termed Coherence Pursuit (CoP) to robust Principal Component Analysis (PCA). As inliers lie in a low dimensional subspace and are mostly correlated, an inlier is likely to have strong mutual coherence with a large number of data points. By contrast, outliers either do not admit low dimensional structures or form small clusters. In either case, an outlier is unlikely to bear strong resemblance to a large number of data points. Given that, CoP sets an outlier apart from an inlier by comparing their coherence with the rest of the data points. The mutual coherences are computed by forming the Gram matrix of the normalized data points. Subsequently, the sought subspace is recovered from the span of the subset of the data points that exhibit strong coherence with the rest of the data. As CoP only involves one simple matrix multiplication, it is significantly faster than the state-of-the-art robust PCA algorithms. We derive analytical performance guarantees for CoP under different models for the distributions of inliers and outliers in both noise-free and noisy settings. CoP is the first robust PCA algorithm that is simultaneously non-iterative, provably robust to both unstructured and structured outliers, and can tolerate a large number of unstructured outliers.
Grammatical Templates: Improving Text Difficulty Evaluation for Language Learners
Venue: arXiv cs.CL 2017
Year: 2017

Language students are most engaged while reading texts at an appropriate difficulty level. However, existing methods of evaluating text difficulty focus mainly on vocabulary and do not prioritize grammatical features, hence they do not work well for language learners with limited knowledge of grammar. In this paper, we introduce grammatical templates, the expert-identified units of grammar that students learn from class, as an important feature of text difficulty evaluation. Experimental classification results show that grammatical template features significantly improve text difficulty prediction accuracy over baseline readability features by 7.4%. Moreover, we build a simple and human-understandable text difficulty evaluation approach with 87.7% accuracy, using only 5 grammatical template features.
Mobile Edge Computing via a UAV-Mounted Cloudlet: Optimization of Bit Allocation and Path Planning
Venue: arXiv cs.NI 2017
Year: 2017

Unmanned Aerial Vehicles (UAVs) have been recently considered as means to provide enhanced coverage or relaying services to mobile users (MUs) in wireless systems with limited or no infrastructure. In this paper, a UAV-based mobile cloud computing system is studied in which a moving UAV is endowed with computing capabilities to offer computation offloading opportunities to MUs with limited local processing capabilities. The system aims at minimizing the total mobile energy consumption while satisfying quality of service requirements of the offloaded mobile application. Offloading is enabled by uplink and downlink communications between the mobile devices and the UAV that take place by means of frequency division duplex (FDD) via orthogonal or non-orthogonal multiple access (NOMA) schemes. The problem of jointly optimizing the bit allocation for uplink and downlink communication as well as for computing at the UAV, along with the cloudlet's trajectory under latency and UAV's energy budget constraints is formulated and addressed by leveraging successive convex approximation (SCA) strategies. Numerical results demonstrate the significant energy savings that can be accrued by means of the proposed joint optimization of bit allocation and cloudlet's trajectory as compared to local mobile execution as well as to partial optimization approaches that design only the bit allocation or the cloudlet's trajectory.
Spatiotemporal Stochastic Modeling of IoT Enabled Cellular Networks: Scalability and Stability Analysis
Venue: arXiv cs.IT 2017
Year: 2017

The Internet of Things (IoT) is large-scale by nature, which is manifested by the massive number of connected devices as well as their vast spatial existence. Cellular networks, which provide ubiquitous, reliable, and efficient wireless access, are natural candidates to provide the first-mile access for the data tsunami to be generated by the IoT. However, cellular networks may have scalability problems to provide uplink connectivity to massive numbers of connected things. To characterize the scalability of cellular uplink in the context of IoT networks, this paper develops a traffic-aware spatiotemporal mathematical model for IoT devices supported by cellular uplink connectivity. The developed model is based on stochastic geometry and queueing theory to account for the traffic requirement per IoT device, the different transmission strategies, and the mutual interference between the IoT devices. To this end, the developed model is utilized to characterize the extent to which cellular networks can accommodate IoT traffic as well as to assess and compare three different transmission strategies that incorporate a combination of transmission persistency, backoff, and power-ramping. The analysis and the results clearly illustrate the scalability problem imposed by IoT on cellular network and offer insights into effective scenarios for each transmission strategy.
Coverage Analysis of Two-Tier HetNets for Co-Channel, Orthogonal, and Partial Spectrum Sharing under Fractional Load Conditions
Venue: arXiv cs.IT 2017
Year: 2017

In heterogeneous networks, the random deployment of femto access points (FAPs) and macro base stations (MBSs) with uncoordinated channel access impose huge inter-tier interferences. In real-life networks, the process of MBSs deployment exhibits the homogeneity, however the FAPs have the behavioral characteristic of clusters formation like in malls, apartments, offices, etc. Therefore, the composite modeling of the MBSs and the FAPs using Poisson point process and Poisson cluster process is employed for the evaluation of coverage probability. The scenario of the real-time traffic for macro-tier and the best-effort traffic for femto-tier is considered. Cognition is introduced in the clustered FAPs to control the inter-tier interference. Furthermore, the impact of macro-tier load is analyzed by exploiting the inherent coupling between coverage probability and activity factor of an MBS. Further, we study the effect of co-channel, orthogonal, and partial spectrum sharing modes on the coverage for given parameters like load condition, FAPs/MBSs density, etc. We provide simulation validation for the derived expressions of coverage and present an comparative analysis for the mentioned spectrum sharing modes.
The Projected Power Method: An Efficient Algorithm for Joint Alignment from Pairwise Differences
Venue: arXiv cs.IT 2017
Year: 2017

Various applications involve assigning discrete label values to a collection of objects based on some pairwise noisy data. Due to the discrete---and hence nonconvex---structure of the problem, computing the optimal assignment (e.g.~maximum likelihood assignment) becomes intractable at first sight. This paper makes progress towards efficient computation by focusing on a concrete joint alignment problem---that is, the problem of recovering $n$ discrete variables $x_i \in \{1,\cdots, m\}$, $1\leq i\leq n$ given noisy observations of their modulo differences $\{x_i - x_j~\mathsf{mod}~m\}$. We propose a low-complexity and model-free procedure, which operates in a lifted space by representing distinct label values in orthogonal directions, and which attempts to optimize quadratic functions over hypercubes. Starting with a first guess computed via a spectral method, the algorithm successively refines the iterates via projected power iterations. We prove that for a broad class of statistical models, the proposed projected power method makes no error---and hence converges to the maximum likelihood estimate---in a suitable regime. Numerical experiments have been carried out on both synthetic and real data to demonstrate the practicality of our algorithm. We expect this algorithmic framework to be effective for a broad range of discrete assignment problems.
Invariance-like results for Nonautonomous Switched Systems
Venue: arXiv cs.SY 2017
Year: 2017

This paper generalizes the Lasalle-Yoshizawa Theorem to switched nonsmooth systems. Filippov and Krasovskii regularizations of a switched system are shown to be contained within the convex hull of the Filippov and Krasovskii regularizations of the subsystems, respectively. A candidate common Lyapunov function that has a negative semidefinite derivative along the trajectories of the subsystems is shown to be sufficient to establish LaSalle-Yoshizawa results for the switched system. Results for regular and non-regular candidate Lyapunov functions are presented using an appropriate generalization of the time derivative. The developed generalization is motivated by adaptive control of switched systems where the derivative of the candidate Lyapunov function is typically negative semidefinite.
List approximation for increasing Kolmogorov complexity
Venue: arXiv cs.CC 2017
Year: 2017

It is impossible to effectively modify a string in order to increase its Kolmogorov complexity. But is it possible to construct a few strings, not longer than the input string, so that most of them have larger complexity? We show that the answer is yes. We present an algorithm that on input a string $x$ of length $n$ returns a list with $O(n^2)$ many strings, all of length $n$, such that 99\% of them are more complex than $x$, provided the complexity of $x$ is less than $n - \log \log n - O(1)$. We obtain similar results for other parameters, including a polynomial-time construction.
FPGA implementation of the procedures for video quality assessment
Venue: arXiv cs.MM 2017
Year: 2017

Video resolutions used in variety of media are constantly rising. While manufacturers struggle to perfect their screens it is also important to ensure high quality of displayed image. Overall quality can be measured using Mean Opinion Score (MOS). Video quality can be affected by miscellaneous artifacts, appearing at every stage of video creation and transmission. In this paper, we present a solution to calculate four distinct video quality metrics that can be applied to a real time video quality assessment system. Our assessment module is capable of processing 8K resolution in real time set at the level of 30 frames per second. Throughput of 2.19 GB/s surpasses performance of pure software solutions. To concentrate on architectural optimization, the module was created using high level language.
Self-Stabilizing Robots in Highly Dynamic Environments
Venue: arXiv cs.DC 2017
Year: 2017

This paper deals with the classical problem of exploring a ring by a cohort of synchronous robots. We focus on the perpetual version of this problem in which it is required that each node of the ring is visited by a robot infinitely often. The challenge in this paper is twofold. First, we assume that the robots evolve in a highly dynamic ring, \ie edges may appear and disappear unpredictably without any recurrence, periodicity, nor stability assumption. The only assumption we made (known as temporal connectivity assumption) is that each node is infinitely often reachable from any other node. Second, we aim at providing a self-stabilizing algorithm to the robots, i.e., the algorithm must guarantee an eventual correct behavior regardless of the initial state and positions of the robots.In this harsh environment, our contribution is to fully characterize, for each size of the ring, the necessary and sufficient number of robots to solve deterministically the problem.
Determination of Bond Wire Failure Probabilities in Microelectronic Packages
Venue: arXiv cs.CE 2017
Year: 2017

This work deals with the computation of industry-relevant bond wire failure probabilities in microelectronic packages. Under operating conditions, a package is subject to Joule heating that can lead to electrothermally induced failures. Manufacturing tolerances result, e.g., in uncertain bond wire geometries that often induce very small failure probabilities requiring a high number of Monte Carlo (MC) samples to be computed. Therefore, a hybrid MC sampling scheme that combines the use of an expensive computer model with a cheap surrogate is used. The fraction of surrogate evaluations is maximized using an iterative procedure, yielding accurate results at reduced cost. Moreover, the scheme is non-intrusive, i.e., existing code can be reused. The algorithm is used to compute the failure probability for an example package and the computational savings are assessed by performing a surrogate efficiency study.
Privacy-preserving Average Consensus: Privacy Analysis and Optimal Algorithm Design
Venue: arXiv cs.SY 2017
Year: 2017

Privacy-preserving average consensus aims to guarantee the privacy of initial states and asymptotic consensus on the exact average of the initial value. In existing work, it is achieved by adding and subtracting variance decaying and zero-sum random noises to the consensus process. However, there is lack of theoretical analysis to quantify the degree of the privacy protection. In this paper, we introduce the maximum disclosure probability that the other nodes can infer one node's initial state within a given small interval to quantify the privacy. We develop a novel privacy definition, named $(ε, δ)$-data-privacy, to depict the relationship between maximum disclosure probability and estimation accuracy. Then, we prove that the general privacy-preserving average consensus (GPAC) provides $(ε, δ)$-data-privacy, and provide the closed-form expression of the relationship between $ε$ and $δ$. Meanwhile, it is shown that the added noise with uniform distribution is optimal in terms of achieving the highest $(ε, δ)$-data-privacy. We also prove that when all information used in the consensus process is available, the privacy will be compromised. Finally, an optimal privacy-preserving average consensus (OPAC) algorithm is proposed to achieve the highest $(ε, δ)$-data-privacy and avoid the privacy compromission. Simulations are conducted to verify the results.
A Logic of Knowing Why
Venue: arXiv cs.AI 2017
Year: 2017

When we say "I know why he was late", we know not only the fact that he was late, but also an explanation of this fact. We propose a logical framework of "knowing why" inspired by the existing formal studies on why-questions, scientific explanation, and justification logic. We introduce the Ky_i operator into the language of epistemic logic to express "agent i knows why phi" and propose a Kripke-style semantics of such expressions in terms of knowing an explanation of phi. We obtain two sound and complete axiomatizations w.r.t. two different model classes depending on different assumptions about introspection.
Deep-Learned Collision Avoidance Policy for Distributed Multi-Agent Navigation
Venue: arXiv cs.AI 2017
Year: 2017

High-speed, low-latency obstacle avoidance that is insensitive to sensor noise is essential for enabling multiple decentralized robots to function reliably in cluttered and dynamic environments. While other distributed multi-agent collision avoidance systems exist, these systems require online geometric optimization where tedious parameter tuning and perfect sensing are necessary. We present a novel end-to-end framework to generate reactive collision avoidance policy for efficient distributed multi-agent navigation. Our method formulates an agent's navigation strategy as a deep neural network mapping from the observed noisy sensor measurements to the agent's steering commands in terms of movement velocity. We train the network on a large number of frames of collision avoidance data collected by repeatedly running a multi-agent simulator with different parameter settings. We validate the learned deep neural network policy in a set of simulated and real scenarios with noisy measurements and demonstrate that our method is able to generate a robust navigation strategy that is insensitive to imperfect sensing and works reliably in all situations. We also show that our method can be well generalized to scenarios that do not appear in our training data, including scenes with static obstacles and agents with different sizes. Videos are available at https://sites.google.com/view/deepmaca.
Obfuscating Keystroke Time Intervals to Avoid Identification and Impersonation
Venue: arXiv cs.CR 2017
Year: 2017

There are numerous opportunities for adversaries to observe user behavior remotely on the web. Additionally, keystroke biometric algorithms have advanced to the point where user identification and soft biometric trait recognition rates are commercially viable. This presents a privacy concern because masking spatial information, such as IP address, is not sufficient as users become more identifiable by their behavior. In this work, the well-known Chaum mix is generalized to a scenario in which users are separated by both space and time with the goal of preventing an observing adversary from identifying or impersonating the user. The criteria of a behavior obfuscation strategy are defined and two strategies are introduced for obfuscating typing behavior. Experimental results are obtained using publicly available keystroke data for three different types of input, including short fixed-text, long fixed-text, and long free-text. Identification accuracy is reduced by 20% with a 25 ms random keystroke delay not noticeable to the user.