OpenRaiser/Intern-Atlas huggingface dataset:
Program Repair for Hyperproperties
Venue: arXiv cs.LO 2021
Year: 2021

We study the repair problem for hyperproperties specified in the temporal logic HyperLTL. Hyperproperties are system properties that relate multiple computation traces. This class of properties includes information flow policies like noninterference and observational determinism. The repair problem is to find, for a given Kripke structure, a substructure that satisfies a given specification. We show that the repair problem is decidable for HyperLTL specifications and finite-state Kripke structures. We provide a detailed complexity analysis for different fragments of HyperLTL and different system types: tree-shaped, acyclic, and general Kripke structures.
The Diagnosis of Asthma using Hilbert-Huang Transform and Deep Learning on Lung Sounds
Venue: arXiv cs.SD 2021
Year: 2021

Lung auscultation is the most effective and indispensable method for diagnosing various respiratory disorders by using the sounds from the airways during inspirium and exhalation using a stethoscope. In this study, the statistical features are calculated from intrinsic mode functions that are extracted by applying the HilbertHuang Transform to the lung sounds from 12 different auscultation regions on the chest and back. The classification of the lung sounds from asthma and healthy subjects is performed using Deep Belief Networks (DBN). The DBN classifier model with two hidden layers has been tested using 5-fold cross validation method. The proposed DBN separated lung sounds from asthmatic and healthy subjects with high classification performance rates of 84.61%, 85.83%, and 77.11% for overall accuracy, sensitivity, and selectivity, respectively using frequencytime analysis.
Dictionary-Sparse Recovery From Heavy-Tailed Measurements
Venue: arXiv cs.IT 2021
Year: 2021

The recovery of signals that are sparse not in a basis, but rather sparse with respect to an over-complete dictionary is one of the most flexible settings in the field of compressed sensing with numerous applications. As in the standard compressed sensing setting, it is possible that the signal can be reconstructed efficiently from few, linear measurements, for example by the so-called $\ell_1$-synthesis method. However, it has been less well-understood which measurement matrices provably work for this setting. Whereas in the standard setting, it has been shown that even certain heavy-tailed measurement matrices can be used in the same sample complexity regime as Gaussian matrices, comparable results are only available for the restrictive class of sub-Gaussian measurement vectors as far as the recovery of dictionary-sparse signals via $\ell_1$-synthesis is concerned. In this work, we fill this gap and establish optimal guarantees for the recovery of vectors that are (approximately) sparse with respect to a dictionary via the $\ell_1$-synthesis method from linear, potentially noisy measurements for a large class of random measurement matrices. In particular, we show that random measurements that fulfill only a small-ball assumption and a weak moment assumption, such as random vectors with i.i.d. Student-$t$ entries with a logarithmic number of degrees of freedom, lead to comparable guarantees as (sub-)Gaussian measurements. As a technical tool, we show a bound on the expectation of the sum of squared order statistics under very general assumptions, which might be of independent interest. As a corollary of our results, we also obtain a slight improvement on the weakest assumption on a measurement matrix with i.i.d. rows sufficient for uniform recovery in standard compressed sensing, improving on results by Lecué and Mendelson and Dirksen, Lecué and Rauhut.
Physical Reservoir Computing with Origami and its Application to Robotic Crawling
Venue: arXiv cs.RO 2021
Year: 2021

A new paradigm called physical reservoir computing has recently emerged, where the nonlinear dynamics of high-dimensional and fixed physical systems are harnessed as a computational resource to achieve complex tasks. Via extensive simulations based on a dynamic truss-frame model, this study shows that an origami structure can perform as a dynamic reservoir with sufficient computing power to emulate high-order nonlinear systems, generate stable limit cycles, and modulate outputs according to dynamic inputs. This study also uncovers the linkages between the origami reservoir's physical designs and its computing power, offering a guideline to optimize the computing performance. Comprehensive parametric studies show that selecting optimal feedback crease distribution and fine-tuning the underlying origami folding designs are the most effective approach to improve computing performance. Furthermore, this study shows how origami's physical reservoir computing power can apply to soft robotic control problems by a case study of earthworm-like peristaltic crawling without traditional controllers. These results can pave the way for origami-based robots with embodied mechanical intelligence.
Finite Model Theory of the Triguarded Fragment and Related Logics
Venue: arXiv cs.LO 2021
Year: 2021

The Triguarded Fragment (TGF) is among the most expressive decidable fragments of first-order logic, subsuming both its two-variable and guarded fragments without equality. We show that the TGF has the finite model property (providing a tight doubly exponential bound on the model size) and hence finite satisfiability coincides with satisfiability known to be N2ExpTime-complete. Using similar constructions, we also establish 2ExpTime-completeness for finite satisfiability of the constant-free (tri)guarded fragment with transitive guards.
Distilling Interpretable Models into Human-Readable Code
Venue: arXiv cs.LG 2021
Year: 2021

The goal of model distillation is to faithfully transfer teacher model knowledge to a model which is faster, more generalizable, more interpretable, or possesses other desirable characteristics. Human-readability is an important and desirable standard for machine-learned model interpretability. Readable models are transparent and can be reviewed, manipulated, and deployed like traditional source code. As a result, such models can be improved outside the context of machine learning and manually edited if desired. Given that directly training such models is difficult, we propose to train interpretable models using conventional methods, and then distill them into concise, human-readable code. The proposed distillation methodology approximates a model's univariate numerical functions with piecewise-linear curves in a localized manner. The resulting curve model representations are accurate, concise, human-readable, and well-regularized by construction. We describe a piecewise-linear curve-fitting algorithm that produces high-quality results efficiently and reliably across a broad range of use cases. We demonstrate the effectiveness of the overall distillation technique and our curve-fitting algorithm using four datasets across the tasks of classification, regression, and ranking.
Finger Vein Recognition by Generating Code
Venue: arXiv cs.CV 2021
Year: 2021

Finger vein recognition has drawn increasing attention as one of the most popular and promising biometrics due to its high distinguishes ability, security and non-invasive procedure. The main idea of traditional schemes is to directly extract features from finger vein images or patterns and then compare features to find the best match. However, the features extracted from images contain much redundant data, while the features extracted from patterns are greatly influenced by image segmentation methods. To tack these problems, this paper proposes a new finger vein recognition by generating code. The proposed method does not require an image segmentation algorithm, is simple to calculate and has a small amount of data. Firstly, the finger vein images were divided into blocks to calculate the mean value. Then the centrosymmetric coding is performed by using the generated eigenmatrix. The obtained codewords are concatenated as the feature codewords of the image. The similarity between vein codes is measured by the ratio of minimum Hamming distance to codeword length. Extensive experiments on two public finger vein databases verify the effectiveness of the proposed method. The results indicate that our method outperforms the state-of-theart methods and has competitive potential in performing the matching task.
Video Summarization: Study of various techniques
Venue: arXiv cs.CV 2021
Year: 2021

A comparative study of various techniques which can be used for summarization of Videos i.e. Video to Video conversion is presented along with respective architecture, results, strengths and shortcomings. In all approaches, a lengthy video is converted into a shorter video which aims to capture all important events that are present in the original video. The definition of 'important event' may vary according to the context, such as a sports video and a documentary may have different events which are classified as important.
Effect of Deep Learning Feature Inference Techniques on Respiratory Sounds
Venue: arXiv cs.SD 2021
Year: 2021

Analysis of respiratory sounds increases its importance every day. Many different methods are available in the analysis, and new techniques are continuing to be developed to further improve these methods. Features are extracted from audio signals and trained using different machine learning techniques. The use of deep learning, which is a different method and has increased in recent years, also shows its influence in this field. Deep learning techniques applied to the image of audio signals give good results and continue to be developed. In this study, image filters were applied to the values obtained from audio signals and the results of the features formed from this were examined in machine learning and deep learning techniques. Their results were compared with the results of methods that had previously achieved good results.
Turkish Voice Commands based Chess Game using Gammatone Cepstral Coefficients
Venue: arXiv cs.SD 2021
Year: 2021

This study was carried out to enable individuals with limited mobility skills to play chess in real time and to play games with the individuals around them without being under any social distress or stress. Voice recordings were taken from 50 people (23 men and 27 women). While recording the sound, 29 words from each person were used which are determined as necessary for playing the game. Mel Frequency Coefficients (MFCC) and Gammatone Cepstral Coefficients (GTCC) qualification methods were used. In addition, k-NN, Naive Bayes and Neural Network classification methods were used for classification. Two different classification procedures were applied, namely, person-based and general. While the performance rate in person-based classification ranged from 75% to 98%, a performance over 84% was achieved in general classification.
Factors that Affect Software Systems Development Project Outcomes: A Survey of Research
Venue: arXiv cs.SE 2021
Year: 2021

Determining the factors that have an influence on software systems development and deployment project outcomes has been the focus of extensive and ongoing research for more than 30 years. We provide here a survey of the research literature that has addressed this topic in the period 1996-2006, with a particular focus on empirical analyses. On the basis of this survey we present a new classification framework that represents an abstracted and synthesized view of the types of factors that have been asserted as influencing project outcomes.
Qualitative Research on Software Development: A Longitudinal Case Study Methodology
Venue: arXiv cs.SE 2021
Year: 2021

This paper reports the use of a qualitative methodology for conducting longitudinal case study research on software development. We provide a detailed description and explanation of appropriate methods of qualitative data collection and analysis that can be utilized by other researchers in the software engineering field. Our aim is to illustrate the utility of longitudinal case study research, as a complement to existing methodologies for studying software development, so as to enable the community to develop a fuller and richer understanding of this complex, multi-dimensional phenomenon. We discuss the insights gained and lessons learned from applying a longitudinal qualitative approach to an empirical case study of a software development project in a large multi-national organization. We evaluate the methodology used to emphasize its strengths and to address the criticisms traditionally made of qualitative research.
COLLIDE-PRED: Prediction of On-Road Collision From Surveillance Videos
Venue: arXiv cs.CV 2021
Year: 2021

Predicting on-road abnormalities such as road accidents or traffic violations is a challenging task in traffic surveillance. If such predictions can be done in advance, many damages can be controlled. Here in our wok, we tried to formulate a solution for automated collision prediction in traffic surveillance videos with computer vision and deep networks. It involves object detection, tracking, trajectory estimation, and collision prediction. We propose an end-to-end collision prediction system, named as COLLIDE-PRED, that intelligently integrates the information of past and future trajectories of moving objects to predict collisions in videos. It is a pipeline that starts with object detection, which is used for object tracking, and then trajectory prediction is performed which concludes by collision detection. The probable place of collision, and the objects those may cause the collision, both can be identified correctly with COLLIDE-PRED. The proposed method is experimentally validated with a number of different videos and proves to be effective in identifying accident in advance.
Unifying Cardiovascular Modelling with Deep Reinforcement Learning for Uncertainty Aware Control of Sepsis Treatment
Venue: arXiv cs.LG 2021
Year: 2021

Sepsis is a potentially life threatening inflammatory response to infection or severe tissue damage. It has a highly variable clinical course, requiring constant monitoring of the patient's state to guide the management of intravenous fluids and vasopressors, among other interventions. Despite decades of research, there's still debate among experts on optimal treatment. Here, we combine for the first time, distributional deep reinforcement learning with mechanistic physiological models to find personalized sepsis treatment strategies. Our method handles partial observability by leveraging known cardiovascular physiology, introducing a novel physiology-driven recurrent autoencoder, and quantifies the uncertainty of its own results. Moreover, we introduce a framework for uncertainty aware decision support with humans in the loop. We show that our method learns physiologically explainable, robust policies that are consistent with clinical knowledge. Further our method consistently identifies high risk states that lead to death, which could potentially benefit from more frequent vasopressor administration, providing valuable guidance for future research
Out-of-Distribution Generalization Analysis via Influence Function
Venue: arXiv cs.LG 2021
Year: 2021

The mismatch between training and target data is one major challenge for current machine learning systems. When training data is collected from multiple domains and the target domains include all training domains and other new domains, we are facing an Out-of-Distribution (OOD) generalization problem that aims to find a model with the best OOD accuracy. One of the definitions of OOD accuracy is worst-domain accuracy. In general, the set of target domains is unknown, and the worst over target domains may be unseen when the number of observed domains is limited. In this paper, we show that the worst accuracy over the observed domains may dramatically fail to identify the OOD accuracy. To this end, we introduce Influence Function, a classical tool from robust statistics, into the OOD generalization problem and suggest the variance of influence function to monitor the stability of a model on training domains. We show that the accuracy on test domains and the proposed index together can help us discern whether OOD algorithms are needed and whether a model achieves good OOD generalization.
Activity Graph Transformer for Temporal Action Localization
Venue: arXiv cs.CV 2021
Year: 2021

We introduce Activity Graph Transformer, an end-to-end learnable model for temporal action localization, that receives a video as input and directly predicts a set of action instances that appear in the video. Detecting and localizing action instances in untrimmed videos requires reasoning over multiple action instances in a video. The dominant paradigms in the literature process videos temporally to either propose action regions or directly produce frame-level detections. However, sequential processing of videos is problematic when the action instances have non-sequential dependencies and/or non-linear temporal ordering, such as overlapping action instances or re-occurrence of action instances over the course of the video. In this work, we capture this non-linear temporal structure by reasoning over the videos as non-sequential entities in the form of graphs. We evaluate our model on challenging datasets: THUMOS14, Charades, and EPIC-Kitchens-100. Our results show that our proposed model outperforms the state-of-the-art by a considerable margin.
Hierarchical Graph-RNNs for Action Detection of Multiple Activities
Venue: arXiv cs.CV 2021
Year: 2021

In this paper, we propose an approach that spatially localizes the activities in a video frame where each person can perform multiple activities at the same time. Our approach takes the temporal scene context as well as the relations of the actions of detected persons into account. While the temporal context is modeled by a temporal recurrent neural network (RNN), the relations of the actions are modeled by a graph RNN. Both networks are trained together and the proposed approach achieves state of the art results on the AVA dataset.
Crossbreeding in Random Forest
Venue: arXiv cs.LG 2021
Year: 2021

Ensemble learning methods are designed to benefit from multiple learning algorithms for better predictive performance. The tradeoff of this improved performance is slower speed and larger size of ensemble learning systems compared to single learning systems. In this paper, we present a novel approach to deal with this problem in Random Forest (RF) as one of the most powerful ensemble methods. The method is based on crossbreeding of the best tree branches to increase the performance of RF in space and speed while keeping the performance in the classification measures. The proposed approach has been tested on a group of synthetic and real datasets and compared to the standard RF approach. Several evaluations have been conducted to determine the effects of the Crossbred RF (CRF) on the accuracy and the number of trees in a forest. The results show better performance of CRF compared to RF.
Fast Clustering of Short Text Streams Using Efficient Cluster Indexing and Dynamic Similarity Thresholds
Venue: arXiv cs.IR 2021
Year: 2021

Short text stream clustering is an important but challenging task since massive amount of text is generated from different sources such as micro-blogging, question-answering, and social news aggregation websites. One of the major challenges of clustering such massive amount of text is to cluster them within a reasonable amount of time. The existing state-of-the-art short text stream clustering methods can not cluster such massive amount of text within a reasonable amount of time as they compute similarities between a text and all the existing clusters to assign that text to a cluster. To overcome this challenge, we propose a fast short text stream clustering method (called FastStream) that efficiently index the clusters using inverted index and compute similarity between a text and a selected number of clusters while assigning a text to a cluster. In this way, we not only reduce the running time of our proposed method but also reduce the running time of several state-of-the-art short text stream clustering methods. FastStream assigns a text to a cluster (new or existing) using the dynamically computed similarity thresholds based on statistical measure. Thus our method efficiently deals with the concept drift problem. Experimental results demonstrate that FastStream outperforms the state-of-the-art short text stream clustering methods by a significant margin on several short text datasets. In addition, the running time of FastStream is several orders of magnitude faster than that of the state-of-the-art methods.
On Separation between the Degree of a Boolean Function and the Block Sensitivity
Venue: arXiv cs.CC 2021
Year: 2021

In this paper we study the separation between two complexity measures: the degree of a Boolean function as a polynomial over the reals and its block sensitivity. We show that separation between these two measures can be improved from $ d^2(f) \geq bs(f) $, established by Tal, to $ d^2(f) \geq (\sqrt{10} - 2)bs(f) $. As a corollary, we show that separations between some other complexity measures are not tight as well, for instance, we can improve recent sensitivity conjecture result by Huang to $s^4(f) \geq (\sqrt{10} - 2)bs(f)$. Our techniques are based on paper by Nisan and Szegedy and include more detailed analysis of a symmetrization polynomial. In our next result we show the same type of improvement in the separation between the approximate degree of a Boolean function and its block sensitivity: we show that $deg_{1/3}^2(f) \geq \sqrt{6/101} bs(f)$ and improve the previous result by Nisan and Szegedy $ deg_{1/3}(f) \geq \sqrt{bs(f)/6} $. In addition, we construct an example which shows that gap between constants in the lower bound and in the known upper bound is less than $0.2$. In our last result we study the properties of conjectured fully sensitive function on 10 variables of degree 4, existence of which would lead to improvement of the biggest known gap between these two measures. We prove that there is the only univariate polynomial that can be achieved by symmetrization of this function by using the combination of interpolation and linear programming techniques.
Bounds on the Feedback Capacity of the $(d,\infty)$-RLL Input-Constrained Binary Erasure Channel
Venue: arXiv cs.IT 2021
Year: 2021

The paper considers the input-constrained binary erasure channel (BEC) with causal, noiseless feedback. The channel input sequence respects the $(d,\infty)$-runlength limited (RLL) constraint, i.e., any pair of successive $1$s must be separated by at least $d$ $0$s. We derive upper and lower bounds on the feedback capacity of this channel, for all $d\geq 1$, given by: $\max\limits_{δ\in [0,\frac{1}{d+1}]}R(δ) \leq C^{\text{fb}}_{(d\infty)}(ε) \leq \max\limits_{δ\in [0,\frac{1}{1+dε}]}R(δ)$, where the function $R(δ) = \frac{h_b(δ)}{dδ+ \frac{1}{1-ε}}$, with $ε\in [0,1]$ denoting the channel erasure probability, and $h_b(\cdot)$ being the binary entropy function. We note that our bounds are tight for the case when $d=1$ (see Sabag et al. (2016)), and, in addition, we demonstrate that for the case when $d=2$, the feedback capacity is equal to the capacity with non-causal knowledge of erasures, for $ε\in [0,1-\frac{1}{2\log(3/2)}]$. For $d>1$, our bounds differ from the non-causal capacities (which serve as upper bounds on the feedback capacity) derived in Peled et al. (2019) in only the domains of maximization. The approach in this paper follows Sabag et al. (2017), by deriving single-letter bounds on the feedback capacity, based on output distributions supported on a finite $Q$-graph, which is a directed graph with edges labelled by output symbols.