OpenRaiser/Intern-Atlas huggingface dataset:
MixTConv: Mixed Temporal Convolutional Kernels for Efficient Action Recogntion
Venue: arXiv cs.CV 2020
Year: 2020

To efficiently extract spatiotemporal features of video for action recognition, most state-of-the-art methods integrate 1D temporal convolution into a conventional 2D CNN backbone. However, they all exploit 1D temporal convolution of fixed kernel size (i.e., 3) in the network building block, thus have suboptimal temporal modeling capability to handle both long-term and short-term actions. To address this problem, we first investigate the impacts of different kernel sizes for the 1D temporal convolutional filters. Then, we propose a simple yet efficient operation called Mixed Temporal Convolution (MixTConv), which consists of multiple depthwise 1D convolutional filters with different kernel sizes. By plugging MixTConv into the conventional 2D CNN backbone ResNet-50, we further propose an efficient and effective network architecture named MSTNet for action recognition, and achieve state-of-the-art results on multiple benchmarks.
Efficient Radial Pattern Keyword Search on Knowledge Graphs in Parallel
Venue: arXiv cs.DB 2020
Year: 2020

Recently, keyword search on Knowledge Graphs (KGs) becomes popular. Typical keyword search approaches aim at finding a concise subgraph from a KG, which can reflect a close relationship among all input keywords. The connection paths between keywords are selected in a way that leads to a result subgraph with a better semantic score. However, such a result may not meet user information need because it relies on the scoring function to decide what keywords to link closer. Therefore, such a result may miss close connections among some keywords on which users intend to focus. In this paper, we propose a parallel keyword search engine, called RAKS. It allows users to specify a query as two sets of keywords, namely central keywords and marginal keywords. Specifically, central keywords are those keywords on which users focus more. Their relationships are desired in the results. Marginal keywords are those less focused keywords. Their connections to the central keywords are desired. In addition, they provide additional information that helps discover better results in terms of user intents. To improve the efficiency, we propose novel weighting and scoring schemes that boost the parallel execution during search while retrieving semantically relevant results. We conduct extensive experiments to validate that RAKS can work efficiently and effectively on open KGs with large size and variety.
From Speech-to-Speech Translation to Automatic Dubbing
Venue: arXiv cs.CL 2020
Year: 2020

We present enhancements to a speech-to-speech translation pipeline in order to perform automatic dubbing. Our architecture features neural machine translation generating output of preferred length, prosodic alignment of the translation with the original speech segments, neural text-to-speech with fine tuning of the duration of each utterance, and, finally, audio rendering to enriches text-to-speech output with background noise and reverberation extracted from the original audio. We report on a subjective evaluation of automatic dubbing of excerpts of TED Talks from English into Italian, which measures the perceived naturalness of automatic dubbing and the relative importance of each proposed enhancement.
See More, Know More: Unsupervised Video Object Segmentation with Co-Attention Siamese Networks
Venue: arXiv cs.CV 2020
Year: 2020

We introduce a novel network, called CO-attention Siamese Network (COSNet), to address the unsupervised video object segmentation task from a holistic view. We emphasize the importance of inherent correlation among video frames and incorporate a global co-attention mechanism to improve further the state-of-the-art deep learning based solutions that primarily focus on learning discriminative foreground representations over appearance and motion in short-term temporal segments. The co-attention layers in our network provide efficient and competent stages for capturing global correlations and scene context by jointly computing and appending co-attention responses into a joint feature space. We train COSNet with pairs of video frames, which naturally augments training data and allows increased learning capacity. During the segmentation stage, the co-attention model encodes useful information by processing multiple reference frames together, which is leveraged to infer the frequently reappearing and salient foreground objects better. We propose a unified and end-to-end trainable framework where different co-attention variants can be derived for mining the rich context within videos. Our extensive experiments over three large benchmarks manifest that COSNet outperforms the current alternatives by a large margin.
On the Minimum Achievable Age of Information for General Service-Time Distributions
Venue: arXiv cs.IR 2020
Year: 2020

There is a growing interest in analysing the freshness of data in networked systems. Age of Information (AoI) has emerged as a popular metric to quantify this freshness at a given destination. There has been a significant research effort in optimizing this metric in communication and networking systems under different settings. In contrast to previous works, we are interested in a fundamental question, what is the minimum achievable AoI in any single-server-single-source queuing system for a given service-time distribution? To address this question, we study a problem of optimizing AoI under service preemptions. Our main result is on the characterization of the minimum achievable average peak AoI (PAoI). We obtain this result by showing that a fixed-threshold policy is optimal in the set of all randomized-threshold causal policies. We use the characterization to provide necessary and sufficient conditions for the service-time distributions under which preemptions are beneficial.
Chaining with overlaps revisited
Venue: arXiv cs.DS 2020
Year: 2020

Chaining algorithms aim to form a semi-global alignment of two sequences based on a set of anchoring local alignments as input. Depending on the optimization criteria and the exact definition of a chain, there are several $O(n \log n)$ time algorithms to solve this problem optimally, where $n$ is the number of input anchors. In this paper, we focus on a formulation allowing the anchors to overlap in a chain. This formulation was studied by Shibuya and Kurochin (WABI 2003), but their algorithm comes with no proof of correctness. We revisit and modify their algorithm to consider a strict definition of precedence relation on anchors, adding the required derivation to convince on the correctness of the resulting algorithm that runs in $O(n \log^2 n)$ time on anchors formed by exact matches. With the more relaxed definition of precedence relation considered by Shibuya and Kurochin or when anchors are non-nested such as matches of uniform length ($k$-mers), the algorithm takes $O(n \log n)$ time. We also establish a connection between chaining with overlaps to the widely studied longest common subsequence (LCS) problem.
A survey of parameterized algorithms and the complexity of edge modification
Venue: arXiv cs.DS 2020
Year: 2020

The survey provides an overview of the developing area of parameterized algorithms for graph modification problems. We concentrate on edge modification problems, where the task is to change a small number of adjacencies in a graph in order to satisfy some required property.
Modeling Supply-Chain Networks with Firm-to-Firm Wire Transfers
Venue: arXiv cs.SI 2020
Year: 2020

We study a novel economic network (supply chain) comprised of wire transfers (electronic payment transactions) among the universe of firms in Brazil (6.2 million firms). We construct a directed and weighted network in which vertices represent cities and edges connote pairwise economic dependence between cities. Cities (vertices) represent the collection of all firms in that location and links denote intercity wire transfers. We find a high degree of economic integration among cities in the trade network, which is consistent with the high degree of specialization found across Brazilian cities. We are able to identify which cities have a dominant role in the entire supply chain process using centrality network measures. We find that the trade network has a disassortative mixing pattern, which is consistent with the power-law shape of the firm size distribution in Brazil. After the Brazilian recession in 2014, we find that the disassortativity becomes even stronger as a result of the death of many small firms and the consequent concentration of economic flows on large firms. Our results suggest that recessions have a large impact on the trade network with meaningful and heterogeneous economic consequences across municipalities. We run econometric exercises and find that courts efficiency plays a dual role. From the customer perspective, it plays an important role in reducing contractual frictions as it increases economic transactions between different cities. From the supplier perspective, cities that are central suppliers to the supply chain seem to use courts inefficiency as a lawsuit barrier from their customers.
Modeling of Deep Neural Network (DNN) Placement and Inference in Edge Computing
Venue: arXiv cs.NI 2020
Year: 2020

With the edge computing becoming an increasingly adopted concept in system architectures, it is expected its utilization will be additionally heightened when combined with deep learning (DL) techniques. The idea behind integrating demanding processing algorithms in Internet of Things (IoT) and edge devices, such as Deep Neural Network (DNN), has in large measure benefited from the development of edge computing hardware, as well as from adapting the algorithms for use in resource constrained IoT devices. Surprisingly, there are no models yet to optimally place and use machine learning in edge computing. In this paper, we propose the first model of optimal placement of Deep Neural Network (DNN) Placement and Inference in edge computing. We present a mathematical formulation to the DNN Model Variant Selection and Placement (MVSP) problem considering the inference latency of different model-variants, communication latency between nodes, and utilization cost of edge computing nodes. We evaluate our model numerically, and show that for low load increasing model co-location decreases the average latency by 33% of millisecond-scale per request, and for high load, by 21%.
Probabilistic Output Analyses for Deterministic Programs --- Reusing Existing Non-probabilistic Analyses
Venue: arXiv cs.PL 2020
Year: 2020

We consider reusing established non-probabilistic output analyses (either forward or backwards) that yield over-approximations of a program's pre-image or image relation, e.g., interval analyses. We assume a probability measure over the program input and present two techniques (one for forward and one for backward analyses) that both derive upper and lower probability bounds for the output events. We demonstrate the most involved technique, namely the forward technique, for two examples and compare their results to a cutting-edge probabilistic output analysis.
Finding the Sparsest Vectors in a Subspace: Theory, Algorithms, and Applications
Venue: arXiv cs.LG 2020
Year: 2020

The problem of finding the sparsest vector (direction) in a low dimensional subspace can be considered as a homogeneous variant of the sparse recovery problem, which finds applications in robust subspace recovery, dictionary learning, sparse blind deconvolution, and many other problems in signal processing and machine learning. However, in contrast to the classical sparse recovery problem, the most natural formulation for finding the sparsest vector in a subspace is usually nonconvex. In this paper, we overview recent advances on global nonconvex optimization theory for solving this problem, ranging from geometric analysis of its optimization landscapes, to efficient optimization algorithms for solving the associated nonconvex optimization problem, to applications in machine intelligence, representation learning, and imaging sciences. Finally, we conclude this review by pointing out several interesting open problems for future research.
Coded Caching with Polynomial Subpacketization
Venue: arXiv cs.IT 2020
Year: 2020

Consider a centralized caching network with a single server and $K$ users. The server has a database of $N$ files with each file being divided into $F$ packets ($F$ is known as subpacketization), and each user owns a local cache that can store $\frac{M}{N}$ fraction of the $N$ files. We construct a family of centralized coded caching schemes with polynomial subpacketization. Specifically, given $M$, $N$ and an integer $n\geq 0$, we construct a family of coded caching schemes for any $(K,M,N)$ caching system with $F=O(K^{n+1})$. More generally, for any $t\in\{1,2,\cdots,K-2\}$ and any integer $n$ such that $0\leq n\leq t$, we construct a coded caching scheme with $\frac{M}{N}=\frac{t}{K}$ and $F\leq K\binom{\left(1-\frac{M}{N}\right)K+n}{n}$.
BAASH: Enabling Blockchain-as-a-Service on High-Performance Computing Systems
Venue: arXiv cs.DC 2020
Year: 2020

The state-of-the-art approach to manage blockchains is to process blocks of transactions in a shared-nothing environment. Although blockchains have the potential to provide various services for high-performance computing (HPC) systems, HPC will not be able to embrace blockchains before the following two missing pieces become available: (i) new consensus protocols being aware of the shared-storage architecture in HPC, and (ii) new fault-tolerant mechanisms compensating for HPC's programming model---the message passing interface (MPI)---that is vulnerable for blockchain-like workloads. To this end, we design a new set of consensus protocols crafted for the HPC platforms and a new fault-tolerance subsystem compensating for the failures caused by faulty MPI processes. Built on top of the new protocols and fault-tolerance mechanism, a prototype system is implemented and evaluated with two million transactions on a 500-core HPC cluster, showing $6\times$, $12\times$, and $75\times$ higher throughput than Hyperldeger, Ethereum, and Parity, respectively.
Segment blockchain: A size reduced storage mechanism for blockchain
Venue: arXiv cs.CR 2020
Year: 2020

The exponential growth of the blockchain size has become a major contributing factor that hinders the decentralisation of blockchain and its potential implementations in data-heavy applications. In this paper, we propose segment blockchain, an approach that segmentises blockchain and enables nodes to only store a copy of one blockchain segment. We use \emph{PoW} as a membership threshold to limit the number of nodes taken by an Adversary---the Adversary can only gain at most $n/2$ of nodes in a network of $n$ nodes when it has $50\%$ of the calculation power in the system (the Nakamoto blockchain security threshold). A segment blockchain system fails when an Adversary stores all copies of a segment, because the Adversary can then leave the system, causing a permanent loss of the segment. We theoretically prove that segment blockchain can sustain a $(AD/n)^m$ failure probability when the Adversary has no more than $AD$ number of nodes and every segment is stored by $m$ number of nodes. The storage requirement is mostly shrunken compared to the traditional design and therefore making the blockchain more suitable for data-heavy applications.
On the Necessity and Design of Coordination Mechanism for Cognitive Autonomous Networks
Venue: arXiv cs.NI 2020
Year: 2020

Cognitive Autonomous Networks (CAN) are promoted to advance Self Organizing Network (SON), replacing rule-based SON Functions (SFs) with Cognitive Functions (CFs), which learn optimal behavior by interacting with the network. As in SON, CFs do encounter conflicts due to overlap in parameters or objectives. However, owing to the non-deterministic behavior of CFs, these conflicts cannot be resolved using rulebased methods and new solutions are required. This paper investigates the CF deployments with and without a coordination mechanism, and proves both heuristically and mathematically that a coordination mechanism is required. Using a two-CF Multi-Agent-System model with the possible types of conflicts, we show that the challenge is a typical bargaining problem, for which the optimal response is the Nash bargaining Solution (NBS). We use NBS to propose a coordination mechanism design that is capable of resolving the conflicts and show via simulations how implementation of the proposed solution is feasible in real life scenario.
Multiplication fusion of sparse and collaborative-competitive representation for image classification
Venue: arXiv cs.CV 2020
Year: 2020

Representation based classification methods have become a hot research topic during the past few years, and the two most prominent approaches are sparse representation based classification (SRC) and collaborative representation based classification (CRC). CRC reveals that it is the collaborative representation rather than the sparsity that makes SRC successful. Nevertheless, the dense representation of CRC may not be discriminative which will degrade its performance for classification tasks. To alleviate this problem to some extent, we propose a new method called sparse and collaborative-competitive representation based classification (SCCRC) for image classification. Firstly, the coefficients of the test sample are obtained by SRC and CCRC, respectively. Then the fused coefficient is derived by multiplying the coefficients of SRC and CCRC. Finally, the test sample is designated to the class that has the minimum residual. Experimental results on several benchmark databases demonstrate the efficacy of our proposed SCCRC. The source code of SCCRC is accessible at https://github.com/li-zi-qi/SCCRC.
An interpretable neural network model through piecewise linear approximation
Venue: arXiv cs.LG 2020
Year: 2020

Most existing interpretable methods explain a black-box model in a post-hoc manner, which uses simpler models or data analysis techniques to interpret the predictions after the model is learned. However, they (a) may derive contradictory explanations on the same predictions given different methods and data samples, and (b) focus on using simpler models to provide higher descriptive accuracy at the sacrifice of prediction accuracy. To address these issues, we propose a hybrid interpretable model that combines a piecewise linear component and a nonlinear component. The first component describes the explicit feature contributions by piecewise linear approximation to increase the expressiveness of the model. The other component uses a multi-layer perceptron to capture feature interactions and implicit nonlinearity, and increase the prediction performance. Different from the post-hoc approaches, the interpretability is obtained once the model is learned in the form of feature shapes. We also provide a variant to explore higher-order interactions among features to demonstrate that the proposed model is flexible for adaptation. Experiments demonstrate that the proposed model can achieve good interpretability by describing feature shapes while maintaining state-of-the-art accuracy.
Model Reuse with Reduced Kernel Mean Embedding Specification
Venue: arXiv cs.LG 2020
Year: 2020

Given a publicly available pool of machine learning models constructed for various tasks, when a user plans to build a model for her own machine learning application, is it possible to build upon models in the pool such that the previous efforts on these existing models can be reused rather than starting from scratch? Here, a grand challenge is how to find models that are helpful for the current application, without accessing the raw training data for the models in the pool. In this paper, we present a two-phase framework. In the upload phase, when a model is uploading into the pool, we construct a reduced kernel mean embedding (RKME) as a specification for the model. Then in the deployment phase, the relatedness of the current task and pre-trained models will be measured based on the value of the RKME specification. Theoretical results and extensive experiments validate the effectiveness of our approach.
Towards Social Identity in Socio-Cognitive Agents
Venue: arXiv cs.AI 2020
Year: 2020

Current architectures for social agents are designed around some specific units of social behaviour that address particular challenges. Although their performance might be adequate for controlled environments, deploying these agents in the wild is difficult. Moreover, the increasing demand for autonomous agents capable of living alongside humans calls for the design of more robust social agents that can cope with diverse social situations. We believe that to design such agents, their sociality and cognition should be conceived as one. This includes creating mechanisms for constructing social reality as an interpretation of the physical world with social meanings and selective deployment of cognitive resources adequate to the situation. We identify several design principles that should be considered while designing agent architectures for socio-cognitive systems. Taking these remarks into account, we propose a socio-cognitive agent model based on the concept of Cognitive Social Frames that allow the adaptation of an agent's cognition based on its interpretation of its surroundings, its Social Context. Our approach supports an agent's reasoning about other social actors and its relationship with them. Cognitive Social Frames can be built around social groups, and form the basis for social group dynamics mechanisms and construct of Social Identity.
RDSP: Rapidly Deployable Wireless Ad Hoc System for Post-Disaster Management
Venue: arXiv cs.NI 2020
Year: 2020

In post-disaster scenarios, such as after floods, earthquakes, and in war zones, the cellular communication infrastructure may be destroyed or seriously disrupted. In such emergency scenarios, it becomes very important for first aid responders to communicate with other rescue teams in order to provide feedback to both the central office and the disaster survivors. To address this issue, rapidly deployable systems are required to re-establish connectivity and assist users and first responders in the region of incident. In this work, we describe the design, implementation, and evaluation of a rapidly deployable system for first response applications in post-disaster situations, named RDSP. The proposed system helps early rescue responders and victims by sharing their location information to remotely located servers by utilizing a novel routing scheme. This novel routing scheme consists of the Dynamic ID Assignment (DIA) algorithm and the Minimum Maximum Neighbor (MMN) algorithm. The DIA algorithm is used by relay devices to dynamically select their IDs on the basis of all the available IDs of networks. Whereas, the MMN algorithm is used by the client and relay devices to dynamically select their next neighbor relays for the transmission of messages. The RDSP contains three devices; the client device sends the victim's location information to the server, the relay device relays information between client and server device, the server device receives messages from the client device to alert the rescue team. We deployed and evaluated our system in the outdoor environment of the university campus. The experimental results show that the RDSP system reduces the message delivery delay and improves the message delivery ratio with lower communication overhead.