cssi/SciSciGPT-SciSciNet huggingface dataset:
Using an Optimal Set of Features With a Machine Learning-Based Approach to Predict Effector Proteins for Legionella Pneumophila

Type IV secretion systems exist in a number of bacterial pathogens and are used to secrete effector proteins directly into host cells in order to change their environment making the environment hospitable for the bacteria. In recent years, several machine learning algorithms have been developed to predict effector proteins, potentially facilitating experimental verification. However, inconsistencies exist between their results. Previously we analysed the disparate sets of predictive features used in these algorithms to determine an optimal set of 370 features for effector prediction. This study focuses on the best way to use these optimal features by designing three machine learning classifiers, comparing our results with those of others, and obtaining de novo results. We chose the pathogen Legionella pneumophila strain Philadelphia-1, a cause of Legionnaires' disease, because it has many validated effector proteins and others have developed machine learning prediction tools for it. While all of our models give good results indicating that our optimal features are quite robust, Model 1, which uses all 370 features with a support vector machine, has slightly better accuracy. Moreover, Model 1 predicted 472 effector proteins that are deemed highly probable to be effectors and include 94% of known effectors. Although the results of our three models agree well with those of other researchers, their models only predicted 126 and 311 candidate effectors.
A Cell Type‐Specific Expression Signature Predicts Haploinsufficient Autism‐Susceptibility Genes

Recent studies have identified many genes with rare de novo mutations in autism, but a limited number of these have been conclusively established as disease-susceptibility genes due to lack of recurrence and confounding background mutations. Such extreme genetic heterogeneity severely limits recurrence–based statistical power even in studies with a large sample size. Here we use cell-type specific expression profiles to differentiate mutations in autism patients from those in unaffected siblings. We report a gene expression signature in different neuronal cell types shared by genes with likely gene disrupting (LGD) mutations in autism cases. The signature reflects haploinsufficiency of risk genes enriched in transcriptional and post-transcriptional regulators, with the strongest positive associations with specific types of neurons in different brain regions, including cortical neurons, cerebellar granule cells, and striatal medium spiny neurons. When used to prioritize genes with a single LGD mutation in cases, a D-score derived from the signature achieved a precision of 40% as compared to the 15% baseline with a minimal loss in sensitivity. An ensemble model combining D-score with mutation intolerance metrics from Exome Aggregation Consortium further improved the precision to 60%, resulting in 117 high-priority candidates. These prioritized lists can facilitate identification of additional autism-susceptibility genes. This article is protected by copyright. All rights reserved
Shared genetic requirements for ATF5 translation in the vomeronasal organ and main olfactory epithelium

Background: Both olfactory sensory neurons (OSNs) and vomeronasal sensory neurons (VSNs) require the transcription factor Atf5 for maturation and survival. In OSNs, ATF5 translation is controlled by olfactory receptor (OR) expression-mediated activation of the PERK branch of the unfolded protein response. This study evaluated whether OSNs and VSNs share genetic requirements for ATF5 translation. Methods: ATF5 immunoreactivity was assayed in whole vomeronasal organs from a series of genetic mutant animals identified in studies of OR gene choice, OR feedback, and regulation and OSN development. Results: ATF5 expression in VSNs required the histone demethylase Lsd1 , which has been previously reported to be required for OR expression. ATF5 expression also required PERK-mediated phosphorylation of the translation initiation factor eIF2a. Finally, unlike previous observations in OSNs, ATF5 was found to be widespread in the mature VNO and co-expressed with mature VSN markers. Conclusions: These data suggest that the initiation of ATF5 translation in VSNs and OSNs is under similar regulation, and that persistent/prolonged ATF5 translation in VSNs may serve VSN-specific gene regulatory programs. This study firmly establishes the unfolded protein response as a major controller of sensory neuronal maturation and diversification.
The evolutionary advantage of cultural memory on heterogeneous contact networks

Abstract Cultural processes, as well as the selection pressures experienced by individuals in a population over time and space, are fundamentally stochastic. Phenotypic variability, together with imperfect phenotypic transmission between parents and offspring, has been previously shown to play an important role in evolutionary rescue and (epi)genetic adaptation of populations to fluctuating temporal environmental pressures. This type of evolutionary bet-hedging does not confer a direct benefit to a single individual, but can instead increase the adaptability of the whole lineage. Here we develop a population-genetic model to explore cultural response strategies to temporally changing selection, as well as the role of local population structure, as exemplified by heterogeneity in the contact network between individuals, in shaping evolutionary dynamics. We use this model to study the evolutionary advantage of cultural bet-hedging, modeling the evolution of a variable cultural trait starting from one copy in a population of individuals with a fixed cultural strategy. We find that the probability of fixation of a cultural bet-hedger is a non-monotonic function of the probability of cultural memory between generations. Moreover, this probability increases for networks of higher mean degree but decreases with increasing heterogeneity of the contact network, tilting the balance of forces toward drift and against selection. These results shed light on the interplay of temporal and spatial stochasticity in shaping cultural evolutionary dynamics and suggest that partly-heritable cultural phenotypic variability may constitute an important evolutionary bet-hedging strategy in response to changing selection pressures.
Peak p-values and false discovery rate inference in neuroimaging.

Abstract Peaks are a mainstay of neuroimage analysis for reporting localization results. The current peak detection procedure in SPM12 requires a pre-threshold for approximating p-values and a false discovery rate (FDR) nominal level for inference. However, the pre-threshold is an undesirable feature, while the FDR level is meaningless if the null hypothesis is not properly defined. This article provides: 1) a peak height distribution for smooth Gaussian error fields, which does not require a screening pre-threshold; 2) a signal-plus-noise model where FDR of peaks can be controlled and properly interpreted. Matlab code for calculation of p-values using the exact peak height distribution is available as an SPM extension.
Synthesis and X-ray Crystal Structure of K4PbTe3·2(en)

K4PbTe3·2(en) has been synthesized from the reduction of an alloy, of nominal composition PbTe2, with potassium metal in ethylenediamine (en). The structure was characterized by single-crystal X-ra...
Total synthesis of (+/-) -phenserine via [4+1] cyclization of a bis(alkylthio)carbene and an indole isocyanate.

A total synthesis of acetylcholine blocking agent, phenserine, has been achieved by employing a [4+1] cyclization between an appropriately substituted indole isocyanate and a bis(alkylthio)carbene.
Anatomy of Sudden Yen Appreciations

The yen is an important barometer for the Japanese economy. Depreciations are typically associated with favorable economic developments such as increased corporate profits, rising equity prices, and upward pressure on domestic consumer prices. On the other hand, large and sharp appreciations run the risk of lowering actual and expected inflation, squeezing corporate profits, generating a negative wealth effect through depressed equity prices, and reducing confidence in the Bank of Japan's efforts to reflate the domestic economy and achieve the inflation target. This paper takes a closer look at underlying drivers of rapid yen appreciations, highlighting the key role of carry-trade and the zero lower bound as important amplifiers.
HOLMES: Real-Time APT Detection through Correlation of Suspicious Information Flows

In this paper, we present HOLMES, a system that implements a new approach to the detection of Advanced and Persistent Threats (APTs). HOLMES is inspired by several case studies of real-world APTs that highlight some common goals of APT actors. In a nutshell, HOLMES aims to produce a detection signal that indicates the presence of a coordinated set of activities that are part of an APT campaign. One of the main challenges addressed by our approach involves developing a suite of techniques that make the detection signal robust and reliable. At a high-level, the techniques we develop effectively leverage the correlation between suspicious information flows that arise during an attacker campaign. In addition to its detection capability, HOLMES is also able to generate a high-level graph that summarizes the attacker’s actions in real-time. This graph can be used by an analyst for an effective cyber response. An evaluation of our approach against some real-world APTs indicates that HOLMES can detect APT campaigns with high precision and low false alarm rate. The compact high-level graphs produced by HOLMES effectively summarizes an ongoing attack campaign and can assist real-time cyber-response operations.
Metric Duality Between Positive Definite Kernels and Boundary Processes

We study representations of positive definite kernels K in a general setting, but with view to applications to harmonic analysis, to metric geometry, and to realizations of certain stochastic processes. Our initial results are stated for the most general given positive definite kernel, but are then subsequently specialized to the above mentioned applications. Given a positive definite kernel K on $$S\times S$$ where S is a fixed set, we first study families of factorizations of K. By a factorization (or representation) we mean a probability space $$\left( B,\mu \right) $$ and an associated stochastic process indexed by S which has K as its covariance kernel. For each realization we identify a co-isometric transform from $$L^{2}\left( \mu \right) $$ onto $$\mathscr {H}\left( K\right) $$ , where $$\mathscr {H}\left( K\right) $$ denotes the reproducing kernel Hilbert space of K. In some cases, this entails a certain renormalization of K. Our emphasis is on such realizations which are minimal in a sense we make precise. By minimal we mean roughly that B may be realized as a certain K-boundary of the given set S. We prove existence of minimal realizations in a general setting.
Monodromy Solver: Sequential and Parallel

We describe, study, and experiment with an algorithm for finding all solutions of systems of polynomial equations using homotopy continuation and monodromy. This algorithm follows the framework developed by Duff et al. (2018) and can operate in the presence of a large number of failures of the homotopy continuation subroutine. We give special attention to parallelization and probabilistic analysis of a model adapted to parallelization and failures. Apart from theoretical results, we developed a simulator that allows us to run a large number of experiments without recomputing the outcomes of the continuation subroutine.
GPU Accelerated Discontinuous Galerkin Methods for Shallow Water Equations

We discuss the development, verification, and performance of a GPU accelerated discontinuous Galerkin method for the solutions of two dimensional nonlinear shallow water equations. The shallow water equations are hyperbolic partial differential equations and are widely used in the simulation of tsunami wave propagations. Our algorithms are tailored to take advantage of the single instruction multiple data (SIMD) architecture of graphic processing units. The time integration is accelerated by local time stepping based on a multi-rate Adams-Bashforthscheme. A total variational bounded limiter is adopted for nonlinear stability of the numerical scheme. This limiter is coupled with a mass and momentum conserving positivity preserving limiter for the special treatment of a dry or partially wet element in the triangulation. Accuracy, robustness and performance are demonstrated with the aid of test cases. Furthermore, we developed a unified multi-threading model OCCA. The kernels expressed in OCCA model can be cross-compiled with multi-threading models OpenCL, CUDA, and OpenMP. We compare the performance of the OCCA kernels when cross-compiled with these models.
Convergence of Discrete Green Functions with Neumann Boundary Conditions

In this article we prove convergence of Green functions with Neumann boundary conditions for the random walk to their continuous counterparts. Our methods rely on local central limit theorems for convergence of random walks on discretizations of smooth domains to Reflected Brownian motion.
Weak amenability for subfactors

We define the notions of weak amenability and the Cowling–Haagerup constant for extremal finite index subfactors s of type II1. We prove that the Cowling–Haagerup constant only depends on the standard invariant of the subfactor. Hence, we define the Cowling–Haagerup constant for standard invariants. We explicitly compute the constant for Bisch–Haagerup subfactors and prove that it is equal to the constant of the group involved in the construction. Given a finite family of amenable standard invariants, we prove that their free product in the sense of Bisch–Jones is weakly amenable with constant 1. We show that the Cowling–Haagerup of the tensor product of a finite family of standard invariants is equal to the product of their Cowling–Haagerup constants.
Sub-Riemannian balls in CR Sasakian manifolds

We prove global estimates for the sub-Riemannian distance of CR Sasakian manifolds with non negative horizontal Webster-Tanaka Ricci curvature. In particular, in this setting, large sub-Riemannian balls are comparable to Riemannian balls.
Proof of the Gorenstein Interval Conjecture in low socle degree

Abstract Roughly ten years ago, the following “Gorenstein Interval Conjecture” (GIC) was proposed: Whenever ( 1 , h 1 , … , h i , … , h e − i , … , h e − 1 , 1 ) and ( 1 , h 1 , … , h i + α , … , h e − i + α , … , h e − 1 , 1 ) are both Gorenstein Hilbert functions for some α ≥ 2 , then ( 1 , h 1 , … , h i + β , … , h e − i + β , … , h e − 1 , 1 ) is also Gorenstein, for all β = 1 , 2 , … , α − 1 . Since an explicit characterization of which Hilbert functions are Gorenstein is widely believed to be hopeless, the GIC, if true, would at least provide the existence of a strong, and very natural, structural property for such basic functions in commutative algebra. Before now, very little progress was made on the GIC. The main goal of this note is to prove the case e ≤ 5 , in arbitrary codimension. Our arguments will be in part constructive, and will combine several different tools of commutative algebra and classical algebraic geometry.
DFT-Spread OFDM with Frequency Domain Reference Symbols

The fifth generation (5G) wireless standard will support several new use cases and 10 to 100 times the performance of fourth generation (4G) systems. Because of the diverse applications for 5G, flexible solutions which can address conflicting requirements will be needed. In this paper, we propose a solution which enables the use of discrete Fourier transform spread orthogonal frequency division multiplexing (DFT-s-OFDM) and OFDM, which address different requirements, using a common low-complexity reference symbol (RS) design. In this solution, the DFT-s-OFDM symbol contains RSs in the frequency domain that may be shared by a subsequent OFDM symbol. The proposed scheme is generated by puncturing the output of a DFT-spread block and replacing the punctured samples with RSs in frequency. We prove that puncturing the interleaved samples at the output of the DFT-spread operation equivalently introduces a periodic interference to the data symbols at the input of the DFT-spread operation. We show that the interference due to the puncturing can be removed with a low-complexity receiver by exploiting the zeros inserted to certain locations before the DFT-spread block at the transmitter. Simulation results support that the proposed scheme removes the error floor caused by the puncturing and achieves lower peak-to- average-power ratio than OFDM.
On the Approximation of Toeplitz Operators for Nonparametric $\mathcal{H}_{\infty}$ -norm Estimation

Given a stable SISO LTI system $G$ , we investigate the problem of estimating the $\mathcal{H}_{\infty}$ -norm of $G$ , denoted $\Vert G\Vert_{\infty}$ , when $G$ is only accessible via noisy observations. Wahlberg et al. [1] recently proposed a nonparametric algorithm based on the power method for estimating the top eigenvalue of a matrix. In particular, by applying a clever time-reversal trick, Wahlberg et al. implement the power method on the top left $n\times n$ corner $T_{n}$ of the Toeplitz (convolution) operator associated to $G$ . In this paper, we prove sharp non-asymptotic bounds on the necessary length $n$ needed so that $\Vert T_{n}\Vert$ is an $\varepsilon$ -additive approximation of $\Vert G\Vert_{\infty}$ . Furthermore, in the process of demonstrating the sharpness of our bounds, we construct a simple family of finite impulse response (FIR) filters where the number of timesteps needed for the power method is arbitrarily worse than the number of timesteps needed for parametric FIR identification via least-squares to achieve the same $\varepsilon$ -additive approximation.
Adaptive Polling in Hierarchical Social Networks Using Blackwell Dominance

This paper presents adaptive polling algorithms and their analysis for social networks having a hierarchical influence structure. The adaptive polling problem on the social network is formulated as a partially observed Markov decision process (POMDP). Our main results exploit the structure of the polling problem to determine novel conditions for Blackwell dominance that arise in hierarchical social influence networks. The Blackwell dominance conditions enable the construction of myopic policies that provably upper bound the optimal policy of the POMDP for adaptive polling. Adaptive versions of intent polling and expectation polling are developed using Blackwell dominance, and they are inexpensive to implement. For polling problems not having a Blackwell dominance structure, the Le Cam deficiency is used to determine approximate Blackwell dominance; this is used to develop an adaptive version of the recently proposed Neighbourhood Expectation Polling algorithm. The proposed Blackwell dominance conditions also facilitate the comparison of Renyi divergence and Shannon capacity of more general channel structures that arise in polling hierarchical social influence networks. Numerical examples are provided to illustrate the adaptive polling policies with parameters estimated from YouTube data.
Non-existence of strong regular reflections in self-similar potential flow

Abstract We consider shock reflection which has a well-known local non-uniqueness: the reflected shock can be either of two choices, called weak and strong. We consider cases where existence of a global solution with weak reflected shock has been proven, for compressible potential flow. If there was a global strong-shock solution as well, then potential flow would be ill-posed. However, we prove non-existence of strong-shock analogues in a natural class of candidates.
Distance Metrics for Measuring Joint Dependence with Application to Causal Inference

Many statistical applications require the quantification of joint dependence among more than two random vectors. In this work, we generalize the notion of distance covariance to quantify joint depe...
Finite-Length Construction of High Performance Spatially-Coupled Codes via Optimized Partitioning and Lifting

Spatially-coupled (SC) codes are a family of graph-based codes that have attracted significant attention, thanks to their capacity approaching performance and low decoding latency. An SC code is constructed by partitioning an underlying block code into a number of components and coupling their copies together. In this paper, we first introduce a general approach for the enumeration of detrimental combinatorial objects in the graph of finite-length SC codes. Our approach is general in the sense that it effectively works for SC codes with various partitioning schemes, column weights, and memories. Next, we present a two-stage framework for the construction of high performance binary SC codes optimized for the additive white Gaussian noise channels; we aim at minimizing the number of detrimental combinatorial objects in the error floor region. In the first stage, we deploy a novel partitioning scheme, called the optimal overlap partitioning, to produce the optimal partitioning corresponding to the smallest number of detrimental objects. In the second stage, we apply a new circulant power optimizer to further reduce the number of detrimental objects in the lifted graph. SC codes constructed by our new framework have up to two orders of magnitude error floor performance improvement and up to 0.6 dB SNR gain compared to prior state-of-the-art SC codes.
Evaluating the robustness of rogue waves under perturbations

Abstract Rogue waves, and their periodic counterparts, have been shown to exist in a number of integrable models. However, relatively little is known about the existence of these objects in models where an exact formula is unattainable. In this work, we develop a novel numerical perspective towards identifying such states as localized solutions in space-time. Importantly, we illustrate this methodology for different perturbations of nonlinear Schrodinger models. In particular, in addition to benchmarking known solutions (and confirming their numerical propagation under controllable error) this enables the continuation of such solutions over parametric variations to non-integrable models. As a result, we can answer in the positive the question about the parametric robustness of Peregrine-like waveforms and even of generalizations thereof on a cnoidal wave background.
T-PFC: A Trajectory-Optimized Perturbation Feedback Control Approach

Traditional stochastic optimal control methods that attempt to obtain an optimal feedback policy for nonlinear systems are computationally intractable. In this letter, we derive a decoupling principle between the open-loop plan, and the closed-loop feedback gains, which leads to a deterministic perturbation feedback control based solution to fully observable stochastic optimal control problems, that is near-optimal. Extensive numerical simulations validate the theory, revealing a wide range of applicability, coping with medium levels of noise. The performance is compared against a set of baselines in several difficult robotic planning and control examples that show near identical performance to nonlinear model predictive control while requiring much lesser computational effort.
Describing a knowledge base

We aim to automatically generate natural language descriptions about an input structured knowledge base (KB). We build our generation framework based on a pointer network which can copy facts from the input KB, and add two attention mechanisms: (i) slot-aware attention to capture the association between a slot type and its corresponding slot value; and (ii) a new table position self-attention to capture the inter-dependencies among related slots. For evaluation, besides standard metrics including BLEU, METEOR, and ROUGE, we propose a KB reconstruction based metric by extracting a KB from the generation output and comparing it with the input KB. We also create a new data set which includes 106,216 pairs of structured KBs and their corresponding natural language descriptions for two distinct entity types. Experiments show that our approach significantly outperforms state-of-the-art methods. The reconstructed KB achieves 68.8% - 72.6% F-score.
Type variables in patterns

For many years, GHC has implemented an extension to Haskell that allows type variables to be bound in type signatures and patterns, and to scope over terms. This extension was never properly specified. We rectify that oversight here. With the formal specification in hand, the otherwise-labyrinthine path toward a design for binding type variables in patterns becomes blindingly clear. We thus extend ScopedTypeVariables to bind type variables explicitly, obviating the Proxy workaround to the dustbin of history.
Mock threshold graphs

Abstract Mock threshold graphs are a simple generalization of threshold graphs that, like threshold graphs, are perfect graphs. Our main theorem is a characterization of mock threshold graphs by forbidden induced subgraphs. Other theorems characterize mock threshold graphs that are claw-free and that are line graphs. We also discuss relations with chordality and well-quasi-ordering as well as algorithmic aspects.
Line complexity asymptotics of polynomial cellular automata

Cellular automata are discrete dynamical systems that consist of patterns of symbols on a grid, which change according to a locally determined transition rule. In this paper, we will consider cellular automata that arise from polynomial transition rules, where the symbols are integers modulo some prime p. We consider the asymptotic behavior of the line complexity sequence $$a_T(k)$$ , which counts, for each k, the number of coefficient strings of length k that occur in the automaton. We begin with the modulo 2 case. For a polynomial $$T(x)=c_0+c_1x+\dots +c_nx^n$$ with $$c_0,c_n\ne ~0$$ , we construct odd and even parts of the polynomial from the strings $$0c_1c_3c_5\cdots c_{1+2\lfloor (n-1)/2\rfloor }$$ and $$c_0c_2c_4\cdots c_{2\lfloor n/2\rfloor }$$ , respectively. We prove that $$a_T(k)$$ satisfies recursions of a specific form if the odd and even parts of T are relatively prime. We also define the order of such a recursion and show that the property of “having a recursion of some order” is preserved when the transition rule is raised to a positive integer power. Extending to a more general setting, we consider an abstract generating function $$\phi (z)=\sum _{k=1}^\infty \alpha (k)z^k$$ which satisfies a functional equation relating $$\phi (z)$$ and $$\phi (z^p)$$ . We show that there is a continuous, piecewise quadratic function f on [1 / p, 1] for which $$\lim _{k\rightarrow \infty }(\alpha (k)/k^2-~f(p^{-\langle \log _p k\rangle })) = 0$$ (here $$\langle y\rangle =y-\lfloor y\rfloor $$ ). We use this result to show that for certain positive integer sequences $$s_k(x)\rightarrow \infty $$ with a parameter $$x\in [1/p,1]$$ , the ratio $$\alpha (s_k(x))/s_k(x)^2$$ tends to f(x), and that the limit superior and inferior of $$\alpha (k)/k^2$$ are given by the extremal values of f.
$(q,t)$-Characters of Kirillov-Reshetikhin Modules of Type $A_r$ as Quantum Cluster Variables

Nakajima (2003) introduced a $t$-deformation of $q$-characters, $(q,t)$-characters for short, and their twisted multiplication through the geometry of quiver varieties. The Nakajima $(q,t)$-characters of Kirillov-Reshetikhin modules satisfy a $t$-deformed $T$-system. The $T$-system is a discrete dynamical system that can be interpreted as a mutation relation in a cluster algebra in two different ways, depending on the choice of direction of evolution. In this paper, we show that the Nakajima $t$-deformed $T$-system of type $A_r$ forms a quantum mutation relation in a quantization of exactly one of the cluster algebra structures attached to the $T$-system.
Learning to filter with predictive state inference machines

Latent state space models are a fundamental and widely used tool for modeling dynamical systems. However, they are difficult to learn from data and learned models often lack performance guarantees on inference tasks such as filtering and prediction. In this work, we present the PREDICTIVE STATE INFERENCE MACHINE (PSIM), a data-driven method that considers the inference procedure on a dynamical system as a composition of predictors. The key idea is that rather than first learning a latent state space model, and then using the learned model for inference, PSIM directly learns predictors for inference in predictive state space. We provide theoretical guarantees for inference, in both realizable and agnostic settings, and showcase practical performance on a variety of simulated and real world robotics benchmarks.
Attractors of sequences of iterated function systems

If F and G are iterated function systems, then any infinite word W in the symbols F and G induces a limit set. It is natural to ask whether this Cantor set can also be realized as the limit set of ...
Stochastic Neural Networks for Hierarchical Reinforcement Learning

Deep reinforcement learning has achieved many impressive results in recent years. However, tasks with sparse rewards or long horizons continue to pose significant challenges. To tackle these important problems, we propose a general framework that first learns useful skills in a pre-training environment, and then leverages the acquired skills for learning faster in downstream tasks. Our approach brings together some of the strengths of intrinsic motivation and hierarchical methods: the learning of useful skill is guided by a single proxy reward, the design of which requires very minimal domain knowledge about the downstream tasks. Then a high-level policy is trained on top of these skills, providing a significant improvement of the exploration and allowing to tackle sparse rewards in the downstream tasks. To efficiently pre-train a large span of skills, we use Stochastic Neural Networks combined with an information-theoretic regularizer. Our experiments show that this combination is effective in learning a wide span of interpretable skills in a sample-efficient way, and can significantly boost the learning performance uniformly across a wide range of downstream tasks.
Probabilistic Rule Realization and Selection

Abstraction and realization are bilateral processes that are key in deriving intelligence and creativity. In many domains, the two processes are approached through \emph{rules}: high-level principles that reveal invariances within similar yet diverse examples. Under a probabilistic setting for discrete input spaces, we focus on the rule realization problem which generates input sample distributions that follow the given rules. More ambitiously, we go beyond a mechanical realization that takes whatever is given, but instead ask for proactively selecting reasonable rules to realize. This goal is demanding in practice, since the initial rule set may not always be consistent and thus intelligent compromises are needed. We formulate both rule realization and selection as two strongly connected components within a single and symmetric bi-convex problem, and derive an efficient algorithm that works at large scale. Taking music compositional rules as the main example throughout the paper, we demonstrate our model's efficiency in not only music realization (composition) but also music interpretation and understanding (analysis).
Sentence Ordering and Coherence Modeling using Recurrent Neural Networks.

Modeling the structure of coherent texts is a key NLP problem. The task of coherently organizing a given set of sentences has been commonly used to build and evaluate models that understand such structure. We propose an end-to-end unsupervised deep learning approach based on the set-to-sequence framework to address this problem. Our model strongly outperforms prior methods in the order discrimination task and a novel task of ordering abstracts from scientific articles. Furthermore, our work shows that useful text representations can be obtained by learning to order sentences. Visualizing the learned sentence representations shows that the model captures high-level logical structure in paragraphs. Our representations perform comparably to state-of-the-art pre-training methods on sentence similarity and paraphrase detection tasks.
High-dimensional estimation with geometric constraints

Author(s): Plan, Yaniv; Vershynin, Roman; Yudovina, Elena | Abstract: Consider measuring an n-dimensional vector x through the inner product with several measurement vectors, a_1, a_2, ..., a_m. It is common in both signal processing and statistics to assume the linear response model y_i = + e_i, where e_i is a noise term. However, in practice the precise relationship between the signal x and the observations y_i may not follow the linear model, and in some cases it may not even be known. To address this challenge, in this paper we propose a general model where it is only assumed that each observation y_i may depend on a_i only through . We do not assume that the dependence is known. This is a form of the semiparametric single index model, and it includes the linear model as well as many forms of the generalized linear model as special cases. We further assume that the signal x has some structure, and we formulate this as a general assumption that x belongs to some known (but arbitrary) feasible set K. We carefully detail the benefit of using the signal structure to improve estimation. The theory is based on the mean width of K, a geometric parameter which can be used to understand its effective dimension in estimation problems. We determine a simple, efficient two-step procedure for estimating the signal based on this model -- a linear estimation followed by metric projection onto K. We give general conditions under which the estimator is minimax optimal up to a constant. This leads to the intriguing conclusion that in the high noise regime, an unknown non-linearity in the observations does not significantly reduce one's ability to determine the signal, even when the non-linearity may be non-invertible. Our results may be specialized to understand the effect of non-linearities in compressed sensing.
Comparing Two Generalized Noncommutative Nevanlinna–Pick Theorems

We explore the relationship between two noncommutative generalizations of the classical Nevanlinna–Pick theorem: one proved by Constantinescu and Johnson in 2003 and the other proved by Muhly and Solel in 2004. To make the comparison, we generalize Constantinescu and Johnson’s theorem to the context of \(W^*\)-correspondences and Hardy algebras. After formulating the so-called displacement equation in this context, we are able to follow Constantinescu and Johnson’s line of reasoning in our proof. Though our result is similar in appearance to Muhly and Solel’s, closer inspection reveals differences. Nevertheless, when the given data lie in the center of the dual correspondence, the theorems are essentially the same.
Time-Series Learning Using Monotonic Logical Properties

Cyber-physical systems of today are generating large volumes of time-series data. As manual inspection of such data is not tractable, the need for learning methods to help discover logical structure in the data has increased. We propose a logic-based framework that allows domain-specific knowledge to be embedded into formulas in a parametric logical specification over time-series data. The key idea is to then map a time series to a surface in the parameter space of the formula. Given this mapping, we identify the Hausdorff distance between surfaces as a natural distance metric between two time-series data under the lens of the parametric specification. This enables embedding non-trivial domain-specific knowledge into the distance metric and then using off-the-shelf machine learning tools to label the data. After labeling the data, we demonstrate how to extract a logical specification for each label. Finally, we showcase our technique on real world traffic data to learn classifiers/monitors for slow-downs and traffic jams.
Spatio-temporal prediction of crimes using network analytic approach

It is quite evident that majority of the population lives in urban area today than in any time of the human history. This trend seems to increase in coming years. A study [5] says that nearly 80.7% of total population in USA stays in urban area. By 2030 nearly 60% of the population in the world will live in or move to cities. With the increase in urban population, it is important to keep an eye on criminal activities. By doing so, governments can enforce intelligent policing systems and hence many government agencies and local authorities have made the crime data publicly available. In this paper, we analyze Chicago city crime data fused with other social information sources using network analytic techniques to predict criminal activity for the next year. We observe that as we add more layers of data which represent different aspects of the society, the quality of prediction is improved. Our prediction models not just predict total number of crimes for the whole Chicago city, rather they predict number of crimes for all types of crimes and for different regions in City of Chicago.Reproducibility: our code is available at https://goo.gl/V1yVLk.
Distributed Solution of Large-Scale Linear Systems Via Accelerated Projection-Based Consensus

Solving a large-scale system of linear equations is a key step at the heart of many algorithms in scientific computing, machine learning, and beyond. When the problem dimension is large, computational and/or memory constraints make it desirable, or even necessary, to perform the task in a distributed fashion. In this paper, we consider a common scenario in which a taskmaster intends to solve a large-scale system of linear equations by distributing subsets of the equations among a number of computing machines/cores. We propose a new algorithm called Accelerated Projection-based Consensus (APC) for this problem. The convergence behavior of the proposed algorithm is analyzed in detail and analytically shown to compare favorably with the convergence rate of alternative distributed methods, namely distributed gradient descent, distributed versions of Nesterov's accelerated gradient descent and heavy-ball method, the block Cimmino method, and ADMM. On randomly chosen linear systems, as well as on real-world data sets, the proposed method offers significant speed-up relative to all the aforementioned methods.
Improving compressed counting

Compressed Counting (CC) [22] was recently proposed for estimating the αth frequency moments of data streams, where 0 < α ≤ 2. CC can be used for estimating Shannon entropy, which can be approximated by certain functions of the αth frequency moments as α → 1. Monitoring Shannon entropy for anomaly detection (e.g., DDoS attacks) in large networks is an important task. This paper presents a new algorithm for improving CC. The improvement is most substantial when α → 1--. For example, when α = 0.99, the new algorithm reduces the estimation variance roughly by 100-fold. This new algorithm would make CC considerably more practical for estimating Shannon entropy. Furthermore, the new algorithm is statistically optimal when α = 0.5.
The mechanism of nanoparticle precipitation induced by electron irradiation in transmission electron microscopy.

Ru nanoparticles (NPs) can precipitate in Ru doped SiO2 amorphous thin films, triggered by electron irradiation in (scanning) transmission electron microscope ((S)TEM). A new mechanism was introduced to interpret the formation of metal NPs in (S)TEM. The induced electric field by electron irradiation, which originates from charging due to ionizations and excitations of atom electrons, can reduce the Gibbs free energy barrier for nucleation of metal particles. Furthermore, the directional ion drifting driven by the electric forces may accelerate the kinetic process of metal particle precipitation.
Sequential detection of low-rank changes using extreme eigenvalues

We study the problem of detecting an abrupt change to the signal covariance matrix. In particular, the covariance changes from a “white” identity matrix to an unknown spiked or low-rank matrix. TWo sequential change-point detection procedures are presented, based on the largest and the smallest eigenvalues of the sample covariance matrix. To control false-alarm-rate, we present an accurate theoretical approximation to the average-run-length (ARL) and expected detection delay (EDD) of the detection, leveraging the extreme eigenvalue distributions from random matrix theory and by capturing a non-negligible temporal correlation in the sequence of scan statistics due to the sliding window approach. Real data examples demonstrate the good performance of our method for detecting behavior change of a swarm.
On the deleted squares of lens spaces

Abstract The configuration space F 2 ( M ) of ordered pairs of distinct points in a manifold M, also known as the deleted square of M, is not a homotopy invariant of M: Longoni and Salvatore produced examples of homotopy equivalent lens spaces M and N of dimension three for which F 2 ( M ) and F 2 ( N ) are not homotopy equivalent. They also asked whether two arbitrary 3-dimensional lens spaces M and N must be homeomorphic in order for F 2 ( M ) and F 2 ( N ) to be homotopy equivalent. We give a partial answer to this question using a novel approach with the Cheeger–Simons differential characters.
The Mean-Field Approximation: Information Inequalities, Algorithms, and Complexity

The mean field approximation to the Ising model is a canonical variational tool that is used for analysis and inference in Ising models. We provide a simple and optimal bound for the KL error of the mean field approximation for Ising models on general graphs, and extend it to higher order Markov random fields. Our bound improves on previous bounds obtained in work in the graph limit literature by Borgs, Chayes, Lovasz, Sos, and Vesztergombi and another recent work by Basak and Mukherjee. Our bound is tight up to lower order terms. Building on the methods used to prove the bound, along with techniques from combinatorics and optimization, we study the algorithmic problem of estimating the (variational) free energy for Ising models and general Markov random fields. For a graph $G$ on $n$ vertices and interaction matrix $J$ with Frobenius norm $\| J \|_F$, we provide algorithms that approximate the free energy within an additive error of $\epsilon n \|J\|_F$ in time $\exp(poly(1/\epsilon))$. We also show that approximation within $(n \|J\|_F)^{1-\delta}$ is NP-hard for every $\delta > 0$. Finally, we provide more efficient approximation algorithms, which find the optimal mean field approximation, for ferromagnetic Ising models and for Ising models satisfying Dobrushin's condition.
Geometry of the 3-user MIMO interference channel

This paper studies vector space interference alignment for the three-user MIMO interference channel with no time or frequency diversity. The main result is a characterization of the feasibility of interference alignment in the symmetric case where all transmitters have M antennas and all receivers have N antennas. If N ≥ M and all users desire d transmit dimensions, then alignment is feasible if and only if (2r + 1)d ≤ max(rN, (r + 1)M) for all nonnegative integers r. The analogous result holds with M and N switched if M ≥ N. It turns out that, just as for the 3-user parallel interference channel [1], the length of alignment paths captures the essence of the problem. In fact, for each feasible value of M and N the maximum alignment path length dictates both the converse and achievability arguments. One of the implications of our feasibility criterion is that simply counting equations and comparing to the number of variables does not predict feasibility. Instead, a more careful investigation of the geometry of the alignment problem is required. The necessary condition obtained by counting equations is implied by our new feasibility criterion.
Matrix coherence and the Nyström method

The Nystrom method is an efficient technique used to speed up large-scale learning applications by generating low-rank approximations. Crucial to the performance of this technique is the assumption that a matrix can be well approximated by working exclusively with a subset of its columns. In this work we relate this assumption to the concept of matrix coherence, connecting coherence to the performance of the Nystrom method. Making use of related work in the compressed sensing and the matrix completion literature, we derive novel coherence-based bounds for the Nystrom method in the low-rank setting. We then present empirical results that corroborate these theoretical bounds. Finally, we present more general empirical results for the full-rank setting that convincingly demonstrate the ability of matrix coherence to measure the degree to which information can be extracted from a subset of columns.
Geometric construction of Hopf cyclic characteristic classes

Abstract In earlier joint work with A. Connes on transverse index theory on foliations, cyclic cohomology adapted to Hopf algebras has emerged as a decisive tool in deciphering the total index class of the hypoelliptic signature operator. We have found a Hopf algebra H n , playing the role of a ‘quantum structure group’ for the ‘space of leaves’ of a codimension n foliation, whose Hopf cyclic cohomology is canonically isomorphic to the Gelfand–Fuks cohomology of the Lie algebra of formal vector fields. However, with a few low-dimensional exceptions, no explicit construction was known for its Hopf cyclic classes. This paper provides an effective method for constructing the Hopf cyclic cohomology classes of H n and of H n relative to O n , in the spirit of the Chern–Weil theory, which completely elucidates their relationship with the characteristic classes of foliations.
The free group does not have the finite cover property

We prove that the first order theory of nonabelian free groups eliminates the ∃∞-quantifier (in eq). Equivalently, since the theory of nonabelian free groups is stable, it does not have the finite cover property.
Fast and Scalable Learning of Sparse Changes in High-Dimensional Gaussian Graphical Model Structure

We focus on the problem of estimating the change in the dependency structures of two $p$-dimensional Gaussian Graphical models (GGMs). Previous studies for sparse change estimation in GGMs involve expensive and difficult non-smooth optimization. We propose a novel method, DIFFEE for estimating DIFFerential networks via an Elementary Estimator under a high-dimensional situation. DIFFEE is solved through a faster and closed form solution that enables it to work in large-scale settings. We conduct a rigorous statistical analysis showing that surprisingly DIFFEE achieves the same asymptotic convergence rates as the state-of-the-art estimators that are much more difficult to compute. Our experimental results on multiple synthetic datasets and one real-world data about brain connectivity show strong performance improvements over baselines, as well as significant computational benefits.
Imaging time-series to improve classification and imputation

Inspired by recent successes of deep learning in computer vision, we propose a novel framework for encoding time series as different types of images, namely, Gramian Angular Summation/ Difference Fields (GASF/GADF) and Markov Transition Fields (MTF). This enables the use of techniques from computer vision for time series classification and imputation. We used Tiled Convolutional Neural Networks (tiled CNNs) on 20 standard datasets to learn high-level features from the individual and compound GASF-GADF-MTF images. Our approaches achieve highly competitive results when compared to nine of the current best time series classification approaches. Inspired by the bijection property of GASF on 0/1 rescaled data, we train Denoised Auto-encoders (DA) on the GASF images of four standard and one synthesized compound dataset. The imputation MSE on test data is reduced by 12.18%-48.02% when compared to using the raw data. An analysis of the features and weights learned via tiled CNNs and DAs explains why the approaches work.