OpenRaiser/Intern-Atlas huggingface dataset:
Temporally Identity-Aware SSD with Attentional LSTM
Venue: arXiv cs.CV 2020
Year: 2020

Temporal object detection has attracted significant attention, but most popular detection methods cannot leverage rich temporal information in videos. Very recently, many algorithms have been developed for video detection task, yet very few approaches can achieve \emph{real-time online} object detection in videos. In this paper, based on attention mechanism and convolutional long short-term memory (ConvLSTM), we propose a temporal single-shot detector (TSSD) for real-world detection. Distinct from previous methods, we take aim at temporally integrating pyramidal feature hierarchy using ConvLSTM, and design a novel structure including a low-level temporal unit as well as a high-level one (LH-TU) for multi-scale feature maps. Moreover, we develop a creative temporal analysis unit, namely, attentional ConvLSTM (AC-LSTM), in which a temporal attention mechanism is specially tailored for background suppression and scale suppression while a ConvLSTM integrates attention-aware features across time. An association loss and a multi-step training are designed for temporal coherence. Besides, an online tubelet analysis (OTA) is exploited for identification. Our framework is evaluated on ImageNet VID dataset and 2DMOT15 dataset. Extensive comparisons on the detection and tracking capability validate the superiority of the proposed approach. Consequently, the developed TSSD-OTA achieves a fast speed and an overall competitive performance in terms of detection and tracking. Finally, a real-world maneuver is conducted for underwater object grasping. The source code is publicly available at https://github.com/SeanChenxy/TSSD-OTA.
Learning-based Dynamic Pinning of Parallelized Applications in Many-Core Systems
Venue: arXiv cs.DC 2020
Year: 2020

Motivated by the need for adaptive, secure and responsive scheduling in a great range of computing applications, including human-centered and time-critical applications, this paper proposes a scheduling framework that seamlessly adds resource-awareness to any parallel application. In particular, we introduce a learning-based framework for dynamic placement of parallel threads to Non-Uniform Memory Access (NUMA) architectures. Decisions are taken independently by each thread in a decentralized fashion that significantly reduces computational complexity. The advantage of the proposed learning scheme is the ability to easily incorporate any multi-objective criterion and easily adapt to performance variations during runtime. Under the multi-objective criterion of maximizing total completed instructions per second (i.e., both computational and memory-access instructions), we provide analytical guarantees with respect to the expected performance of the parallel application. We also compare the performance of the proposed scheme with the Linux operating system scheduler in an extensive set of applications, including both computationally and memory intensive ones. We have observed that performance improvement could be significant especially under limited availability of resources and under irregular memory-access patterns.
New Ideas for Brain Modelling 5
Venue: arXiv cs.AI 2020
Year: 2020

This paper describes a process for combining patterns and features, to guide a search process and make predictions. It is based on the functionality that a human brain might have, which is a highly distributed network of simple neuronal components that can apply some level of matching and cross-referencing over retrieved patterns. The process uses memory in a dynamic way and it is directed through the pattern matching. The paper firstly describes the mechanisms for neuronal search, memory and prediction. The paper then presents a formal language for defining cognitive processes, that is, pattern-based sequences and transitions. The language can define an outer framework for concept sets that are linked to perform the cognitive act. The language also has a mathematical basis, allowing for the rule construction to be consistent. Now, both static memory and dynamic process hierarchies can be built as tree structures. The new information can also be used to further integrate the cognitive model and the ensemble-hierarchy structure becomes an essential part. A theory about linking can suggest that nodes in different regions link together when generally they represent the same thing.
The Preeminence of Ethnic Diversity in Scientific Collaboration
Venue: arXiv cs.DL 2020
Year: 2020

Inspired by the social and economic benefits of diversity, we analyze over 9 million papers and 6 million scientists to study the relationship between research impact and five classes of diversity: ethnicity, discipline, gender, affiliation, and academic age. Using randomized baseline models, we establish the presence of homophily in ethnicity, gender and affiliation. We then study the effect of diversity on scientific impact, as reflected in citations. Remarkably, of the classes considered, ethnic diversity had the strongest correlation with scientific impact. To further isolate the effects of ethnic diversity, we used randomized baseline models and again found a clear link between diversity and impact. To further support these findings, we use coarsened exact matching to compare the scientific impact of ethnically diverse papers and scientists with closely-matched control groups. Here, we find that ethnic diversity resulted in an impact gain of 10.63% for papers, and 47.67% for scientists.
Satisficing in Time-Sensitive Bandit Learning
Venue: arXiv cs.LG 2020
Year: 2020

Much of the recent literature on bandit learning focuses on algorithms that aim to converge on an optimal action. One shortcoming is that this orientation does not account for time sensitivity, which can play a crucial role when learning an optimal action requires much more information than near-optimal ones. Indeed, popular approaches such as upper-confidence-bound methods and Thompson sampling can fare poorly in such situations. We consider instead learning a satisficing action, which is near-optimal while requiring less information, and propose satisficing Thompson sampling, an algorithm that serves this purpose. We establish a general bound on expected discounted regret and study the application of satisficing Thompson sampling to linear and infinite-armed bandits, demonstrating arbitrarily large benefits over Thompson sampling. We also discuss the relation between the notion of satisficing and the theory of rate distortion, which offers guidance on the selection of satisficing actions.
City-wide Analysis of Electronic Health Records Reveals Gender and Age Biases in the Administration of Known Drug-Drug Interactions
Venue: arXiv cs.SI 2020
Year: 2020

The occurrence of drug-drug-interactions (DDI) from multiple drug dispensations is a serious problem, both for individuals and health-care systems, since patients with complications due to DDI are likely to reenter the system at a costlier level. We present a large-scale longitudinal study (18 months) of the DDI phenomenon at the primary- and secondary-care level using electronic health records (EHR) from the city of Blumenau in Southern Brazil (pop. $\approx 340,000$). We found that 181 distinct drug pairs known to interact were dispensed concomitantly to 12\% of the patients in the city's public health-care system. Further, 4\% of the patients were dispensed drug pairs that are likely to result in major adverse drug reactions (ADR)---with costs estimated to be much larger than previously reported in smaller studies. The large-scale analysis reveals that women have a 60\% increased risk of DDI as compared to men; the increase becomes 90\% when considering only DDI known to lead to major ADR. Furthermore, DDI risk increases substantially with age; patients aged 70-79 years have a 34\% risk of DDI when they are dispensed two or more drugs concomitantly. Interestingly, a statistical null model demonstrates that age- and female-specific risks from increased polypharmacy fail by far to explain the observed DDI risks in those populations, suggesting unknown social or biological causes. We also provide a network visualization of drugs and demographic factors that characterize the DDI phenomenon and demonstrate that accurate DDI prediction can be included in healthcare and public-health management, to reduce DDI-related ADR and costs.
Learning with End-Users in Distribution Grids: Topology and Parameter Estimation
Venue: arXiv cs.SY 2020
Year: 2020

Efficient operation of distribution grids in the smart-grid era is hindered by the limited presence of real-time nodal and line meters. In particular, this prevents the easy estimation of grid topology and associated line parameters that are necessary for control and optimization efforts in the grid. This paper studies the problems of topology and parameter estimation in radial balanced distribution grids where measurements are restricted to only the leaf nodes and all intermediate nodes are unobserved/hidden. To this end, we propose two exact learning algorithms that use balanced voltage and injection measured only at the end-users. The first algorithm requires time-stamped voltage samples, statistics of nodal power injections and permissible line impedances to recover the true topology. The second and improved algorithm requires only time-stamped voltage and complex power samples to recover both the true topology and impedances without any additional input (e.g., number of grid nodes, statistics of injections at hidden nodes, permissible line impedances). We prove the correctness of both learning algorithms for grids where unobserved buses/nodes have a degree greater than three and discuss extensions to regimes where that assumption doesn't hold. Further, we present computational and, more importantly, the sample complexity of our proposed algorithm for joint topology and impedance estimation. We illustrate the performance of the designed algorithms through numerical experiments on the IEEE and custom power distribution models.
Lipschitz Constrained GANs via Boundedness and Continuity
Venue: arXiv cs.CV 2020
Year: 2020

One of the challenges in the study of Generative Adversarial Networks (GANs) is the difficulty of its performance control. Lipschitz constraint is essential in guaranteeing training stability for GANs. Although heuristic methods such as weight clipping, gradient penalty and spectral normalization have been proposed to enforce Lipschitz constraint, it is still difficult to achieve a solution that is both practically effective and theoretically provably satisfying a Lipschitz constraint. In this paper, we introduce the boundedness and continuity ($BC$) conditions to enforce the Lipschitz constraint on the discriminator functions of GANs. We prove theoretically that GANs with discriminators meeting the BC conditions satisfy the Lipschitz constraint. We present a practically very effective implementation of a GAN based on a convolutional neural network (CNN) by forcing the CNN to satisfy the $BC$ conditions (BC-GAN). We show that as compared to recent techniques including gradient penalty and spectral normalization, BC-GANs not only have better performances but also lower computational complexity.
Parameterized Complexity of Fair Vertex Evaluation Problems
Venue: arXiv cs.CC 2020
Year: 2020

A prototypical graph problem is centered around a graph-theoretic property for a set of vertices and a solution to it is a set of vertices for which the desired property holds. The task is to decide whether, in the given graph, there exists a solution of a certain quality, where we use size as a quality measure. In this work, we are changing the measure to the fair measure [Lin&Sahni: Fair edge deletion problems. IEEE Trans. Comput. 89]. The measure is k if the number of solution neighbors does not exceed k for any vertex in the graph. One possible way to study graph problems is by defining the property in a certain logic. For a given objective an evaluation problem is to find a set (of vertices) that simultaneously minimizes the assumed measure and satisfies an appropriate formula. In the presented paper we show that there is an FPT algorithm for the MSO Fair Vertex Evaluation problem for formulas with one free variable parameterized by the twin cover number of the input graph. Here, the free variable corresponds to the solution sought. One may define an extended variant of MSO Fair Vertex Evaluation for formulas with l free variables; here we measure a maximum number of neighbors in each of the l sets. However, such variant is W[1]-hard for parameter l even on graphs with twin cover one. Furthermore, we study the Fair Vertex Cover (Fair VC) problem. Fair VC is among the simplest problems with respect to the demanded property (i.e., the rest forms an edgeless graph). On the negative side, Fair VC is W[1]-hard when parameterized by both treedepth and feedback vertex set of the input graph. On the positive side, we provide an FPT algorithm for the parameter modular width.
IntPhys: A Framework and Benchmark for Visual Intuitive Physics Reasoning
Venue: arXiv cs.AI 2020
Year: 2020

In order to reach human performance on complexvisual tasks, artificial systems need to incorporate a sig-nificant amount of understanding of the world in termsof macroscopic objects, movements, forces, etc. Inspiredby work on intuitive physics in infants, we propose anevaluation benchmark which diagnoses how much a givensystem understands about physics by testing whether itcan tell apart well matched videos of possible versusimpossible events constructed with a game engine. Thetest requires systems to compute a physical plausibilityscore over an entire video. It is free of bias and cantest a range of basic physical reasoning concepts. Wethen describe two Deep Neural Networks systems aimedat learning intuitive physics in an unsupervised way,using only physically possible videos. The systems aretrained with a future semantic mask prediction objectiveand tested on the possible versus impossible discrimi-nation task. The analysis of their results compared tohuman data gives novel insights in the potentials andlimitations of next frame prediction architectures.
Asynchronous Gradient-Push
Venue: arXiv cs.MA 2020
Year: 2020

We consider a multi-agent framework for distributed optimization where each agent has access to a local smooth strongly convex function, and the collective goal is to achieve consensus on the parameters that minimize the sum of the agents' local functions. We propose an algorithm wherein each agent operates asynchronously and independently of the other agents. When the local functions are strongly-convex with Lipschitz-continuous gradients, we show that the iterates at each agent converge to a neighborhood of the global minimum, where the neighborhood size depends on the degree of asynchrony in the multi-agent network. When the agents work at the same rate, convergence to the global minimizer is achieved. Numerical experiments demonstrate that Asynchronous Gradient-Push can minimize the global objective faster than state-of-the-art synchronous first-order methods, is more robust to failing or stalling agents, and scales better with the network size.
A 3/2-approximation algorithm for the Student-Project Allocation problem
Venue: arXiv cs.DS 2020
Year: 2020

The Student-Project Allocation problem with lecturer preferences over Students (SPA-S) comprises three sets of agents, namely students, projects and lecturers, where students have preferences over projects and lecturers have preferences over students. In this scenario we seek a stable matching, that is, an assignment of students to projects such that there is no student and lecturer who have an incentive to deviate from their assignee/s. We study SPA-ST, the extension of SPA-S in which the preference lists of students and lecturers need not be strictly ordered, and may contain ties. In this scenario, stable matchings may be of different sizes, and it is known that MAX SPA-ST, the problem of finding a maximum stable matching in SPA-ST, is NP-hard. We present a linear-time 3/2-approximation algorithm for MAX SPA-ST and an Integer Programming (IP) model to solve MAX SPA-ST optimally. We compare the approximation algorithm with the IP model experimentally using randomly-generated data. We find that the performance of the approximation algorithm easily surpassed the 3/2 bound, constructing a stable matching within 92% of optimal in all cases, with the percentage being far higher for many instances.
Walk-Steered Convolution for Graph Classification
Venue: arXiv cs.SI 2020
Year: 2020

Graph classification is a fundamental but challenging issue for numerous real-world applications. Despite recent great progress in image/video classification, convolutional neural networks (CNNs) cannot yet cater to graphs well because of graphical non-Euclidean topology. In this work, we propose a walk-steered convolutional (WSC) network to assemble the essential success of standard convolutional neural networks as well as the powerful representation ability of random walk. Instead of deterministic neighbor searching used in previous graphical CNNs, we construct multi-scale walk fields (a.k.a. local receptive fields) with random walk paths to depict subgraph structures and advocate graph scalability. To express the internal variations of a walk field, Gaussian mixture models are introduced to encode principal components of walk paths therein. As an analogy to a standard convolution kernel on image, Gaussian models implicitly coordinate those unordered vertices/nodes and edges in a local receptive field after projecting to the gradient space of Gaussian parameters. We further stack graph coarsening upon Gaussian encoding by using dynamic clustering, such that high-level semantics of graph can be well learned like the conventional pooling on image. The experimental results on several public datasets demonstrate the superiority of our proposed WSC method over many state-of-the-arts for graph classification.
Understanding Convolutional Neural Networks with Information Theory: An Initial Exploration
Venue: arXiv cs.LG 2020
Year: 2020

The matrix-based Renyi's α-entropy functional and its multivariate extension were recently developed in terms of the normalized eigenspectrum of a Hermitian matrix of the projected data in a reproducing kernel Hilbert space (RKHS). However, the utility and possible applications of these new estimators are rather new and mostly unknown to practitioners. In this paper, we first show that our estimators enable straightforward measurement of information flow in realistic convolutional neural networks (CNN) without any approximation. Then, we introduce the partial information decomposition (PID) framework and develop three quantities to analyze the synergy and redundancy in convolutional layer representations. Our results validate two fundamental data processing inequalities and reveal some fundamental properties concerning the training of CNN.
An Economic-Based Analysis of RANKING for Online Bipartite Matching
Venue: arXiv cs.GT 2020
Year: 2020

In their seminal paper, Karp, Vazirani and Vazirani (STOC'90) introduce the online bipartite matching problem, and the RANKING algorithm, which admits a tight $1-\frac{1}{e}$ competitive ratio. Since its publication, the problem has received considerable attention, including a sequence of simplified proofs. In this paper we present a new proof that gives an economic interpretation of the RANKING algorithm -- further simplifying the proof and avoiding arguments such as duality. The new proof gives a new perspective on previous proofs.
Don't Panic! Better, Fewer, Syntax Errors for LR Parsers
Venue: arXiv cs.PL 2020
Year: 2020

Syntax errors are generally easy to fix for humans, but not for parsers in general nor LR parsers in particular. Traditional 'panic mode' error recovery, though easy to implement and applicable to any grammar, often leads to a cascading chain of errors that drown out the original. More advanced error recovery techniques suffer less from this problem but have seen little practical use because their typical performance was seen as poor, their worst case unbounded, and the repairs they reported arbitrary. In this paper we introduce the CPCT+ algorithm, and an implementation of that algorithm, that address these issues. First, CPCT+ reports the complete set of minimum cost repair sequences for a given location, allowing programmers to select the one that best fits their intention. Second, on a corpus of 200,000 real-world syntactically invalid Java programs, CPCT+ is able to repair 98.37% of files within a timeout of 0.5s. Finally, CPCT+ uses the complete set of minimum cost repair sequences to reduce the cascading error problem, where incorrect error recovery causes further spurious syntax errors to be identified. Across the test corpus, CPCT+ reports 435,812 error locations to the user, reducing the cascading error problem substantially relative to the 981,628 error locations reported by panic mode.
Bayesian Auctions with Efficient Queries
Venue: arXiv cs.GT 2020
Year: 2020

Generating good revenue is one of the most important problems in Bayesian auction design, and many (approximately) optimal dominant-strategy incentive compatible (DSIC) Bayesian mechanisms have been constructed for various auction settings. However, most existing studies do not consider the complexity for the seller to carry out the mechanism. It is assumed that the seller knows "each single bit" of the distributions and is able to optimize perfectly based on the entire distributions. Unfortunately, this is a strong assumption and may not hold in reality: for example, when the value distributions have exponentially large supports or do not have succinct representations. In this work we consider, for the first time, the query complexity of Bayesian mechanisms. We only allow the seller to have limited oracle accesses to the players' value distributions, via quantile queries and value queries. For a large class of auction settings, we prove logarithmic lower-bounds for the query complexity for any DSIC Bayesian mechanism to be of any constant approximation to the optimal revenue. For single-item auctions and multi-item auctions with unit-demand or additive valuation functions, we prove tight upper-bounds via efficient query schemes, without requiring the distributions to be regular or have monotone hazard rate. Thus, in those auction settings the seller needs to access much less than the full distributions in order to achieve approximately optimal revenue.
A New Channel Boosted Convolutional Neural Network using Transfer Learning
Venue: arXiv cs.CV 2020
Year: 2020

We present a novel architectural enhancement of Channel Boosting in a deep convolutional neural network (CNN). This idea of Channel Boosting exploits both the channel dimension of CNN (learning from multiple input channels) and Transfer learning (TL). TL is utilized at two different stages; channel generation and channel exploitation. In the proposed methodology, a deep CNN is boosted by various channels available through TL from already trained Deep Neural Networks, in addition to its original channel. The deep architecture of CNN then exploits the original and boosted channels down the stream for learning discriminative patterns. Churn prediction in telecom is a challenging task due to the high dimensionality and imbalanced nature of the data. Therefore, churn prediction data is used to evaluate the performance of the proposed Channel Boosted CNN (CB CNN). In the first phase, informative discriminative features are being extracted using a stacked autoencoder, and then in the second phase, these features are combined with the original features to form Channel Boosted images. Finally, the knowledge gained by a pretrained CNN is exploited by employing TL. The results are promising and show the ability of the Channel Boosting concept in learning complex classification problems by discerning even minute differences in churners and nonchurners. The proposed work validates the concept observed from the evolution of recent CNN architectures that the innovative restructuring of a CNN architecture may increase the networks representative capacity.