OpenRaiser/Intern-Atlas huggingface dataset:
Cross-modal Subspace Learning via Kernel Correlation Maximization and Discriminative Structure Preserving
Venue: arXiv cs.CV 2020
Year: 2020

The measure between heterogeneous data is still an open problem. Many research works have been developed to learn a common subspace where the similarity between different modalities can be calculated directly. However, most of existing works focus on learning a latent subspace but the semantically structural information is not well preserved. Thus, these approaches cannot get desired results. In this paper, we propose a novel framework, termed Cross-modal subspace learning via Kernel correlation maximization and Discriminative structure-preserving (CKD), to solve this problem in two aspects. Firstly, we construct a shared semantic graph to make each modality data preserve the neighbor relationship semantically. Secondly, we introduce the Hilbert-Schmidt Independence Criteria (HSIC) to ensure the consistency between feature-similarity and semantic-similarity of samples. Our model not only considers the inter-modality correlation by maximizing the kernel correlation but also preserves the semantically structural information within each modality. The extensive experiments are performed to evaluate the proposed framework on the three public datasets. The experimental results demonstrated that the proposed CKD is competitive compared with the classic subspace learning methods.
Optimal Obfuscation Mechanisms via Machine Learning
Venue: arXiv cs.LG 2020
Year: 2020

We consider the problem of obfuscating sensitive information while preserving utility, and we propose a machine learning approach inspired by the generative adversarial networks paradigm. The idea is to set up two nets: the generator, that tries to produce an optimal obfuscation mechanism to protect the data, and the classifier, that tries to de-obfuscate the data. By letting the two nets compete against each other, the mechanism improves its degree of protection, until an equilibrium is reached. We apply our method to the case of location privacy, and we perform experiments on synthetic data and on real data from the Gowalla dataset. We evaluate the privacy of the mechanism not only by its capacity to defeat the classifier, but also in terms of the Bayes error, which represents the strongest possible adversary. We compare the privacy-utility tradeoff of our method to that of the planar Laplace mechanism used in geo-indistinguishability, showing favorable results. Like the Laplace mechanism, our system can be deployed at the user end for protecting his location.
The minimal probabilistic and quantum finite automata recognizing uncountably many languages with fixed cutpoints
Venue: arXiv cs.FL 2020
Year: 2020

It is known that 2-state binary and 3-state unary probabilistic finite automata and 2-state unary quantum finite automata recognize uncountably many languages with cutpoints. These results have been obtained by associating each recognized language with a cutpoint and then by using the fact that there are uncountably many cutpoints. In this note, we prove the same results for fixed cutpoints: each recognized language is associated with an automaton (i.e., algorithm), and the proofs use the fact that there are uncountably many automata. For each case, we present a new construction.
Automatic diagnosis of the 12-lead ECG using a deep neural network
Venue: arXiv cs.LG 2020
Year: 2020

The role of automatic electrocardiogram (ECG) analysis in clinical practice is limited by the accuracy of existing models. Deep Neural Networks (DNNs) are models composed of stacked transformations that learn tasks by examples. This technology has recently achieved striking success in a variety of task and there are great expectations on how it might improve clinical practice. Here we present a DNN model trained in a dataset with more than 2 million labeled exams analyzed by the Telehealth Network of Minas Gerais and collected under the scope of the CODE (Clinical Outcomes in Digital Electrocardiology) study. The DNN outperform cardiology resident medical doctors in recognizing 6 types of abnormalities in 12-lead ECG recordings, with F1 scores above 80% and specificity over 99%. These results indicate ECG analysis based on DNNs, previously studied in a single-lead setup, generalizes well to 12-lead exams, taking the technology closer to the standard clinical practice.
SANNS: Scaling Up Secure Approximate k-Nearest Neighbors Search
Venue: arXiv cs.DS 2020
Year: 2020

The $k$-Nearest Neighbor Search ($k$-NNS) is the backbone of several cloud-based services such as recommender systems, face recognition, and database search on text and images. In these services, the client sends the query to the cloud server and receives the response in which case the query and response are revealed to the service provider. Such data disclosures are unacceptable in several scenarios due to the sensitivity of data and/or privacy laws. In this paper, we introduce SANNS, a system for secure $k$-NNS that keeps client's query and the search result confidential. SANNS comprises two protocols: an optimized linear scan and a protocol based on a novel sublinear time clustering-based algorithm. We prove the security of both protocols in the standard semi-honest model. The protocols are built upon several state-of-the-art cryptographic primitives such as lattice-based additively homomorphic encryption, distributed oblivious RAM, and garbled circuits. We provide several contributions to each of these primitives which are applicable to other secure computation tasks. Both of our protocols rely on a new circuit for the approximate top-$k$ selection from $n$ numbers that is built from $O(n + k^2)$ comparators. We have implemented our proposed system and performed extensive experimental results on four datasets in two different computation environments, demonstrating more than $18-31\times$ faster response time compared to optimally implemented protocols from the prior work. Moreover, SANNS is the first work that scales to the database of 10 million entries, pushing the limit by more than two orders of magnitude.
Beyond #CSP: A Dichotomy for Counting Weighted Eulerian Orientations with ARS
Venue: arXiv cs.CC 2020
Year: 2020

We define and explore a notion of unique prime factorization for constraint functions, and use this as a new tool to prove a complexity classification for counting weighted Eulerian orientation problems with arrow reversal symmetry (ARS). We prove that all such problems are either polynomial-time computable or #P-hard. We show that the class of weighted Eulerian orientation problems subsumes all weighted counting constraint satisfaction problems (#CSP) on Boolean variables. More significantly, we establish a novel connection between #CSP and counting weighted Eulerian orientation problems that is global in nature. This connection is based on a structural determination of all half-weighted affine linear subspaces over $\mathbb{Z}_2$, which is proved using Möbius inversion.
Empirical Bayes Regret Minimization
Venue: arXiv cs.LG 2020
Year: 2020

Most bandit algorithm designs are purely theoretical. Therefore, they have strong regret guarantees, but also are often too conservative in practice. In this work, we pioneer the idea of algorithm design by minimizing the empirical Bayes regret, the average regret over problem instances sampled from a known distribution. We focus on a tractable instance of this problem, the confidence interval and posterior width tuning, and propose an efficient algorithm for solving it. The tuning algorithm is analyzed and evaluated in multi-armed, linear, and generalized linear bandits. We report several-fold reductions in Bayes regret for state-of-the-art bandit algorithms, simply by optimizing over a small sample from a distribution.
How should my chatbot interact? A survey on human-chatbot interaction design
Venue: arXiv cs.HC 2020
Year: 2020

Chatbots' growing popularity has brought new challenges to HCI, having changed the patterns of human interactions with computers. The increasing need to approximate conversational interaction styles raises expectations for chatbots to present social behaviors that are habitual in human-human communication. In this survey, we argue that chatbots should be enriched with social characteristics that cohere with users' expectations, ultimately avoiding frustration and dissatisfaction. We bring together the literature on disembodied, text-based chatbots to derive a conceptual model of social characteristics for chatbots. We analyzed 56 papers from various domains to understand how social characteristics can benefit human-chatbot interactions and identify the challenges and strategies to designing them. Additionally, we discussed how characteristics may influence one another. Our results provide relevant opportunities to both researchers and designers to advance human-chatbot interactions.
Branched Multi-Task Networks: Deciding What Layers To Share
Venue: arXiv cs.CV 2020
Year: 2020

In the context of multi-task learning, neural networks with branched architectures have often been employed to jointly tackle the tasks at hand. Such ramified networks typically start with a number of shared layers, after which different tasks branch out into their own sequence of layers. Understandably, as the number of possible network configurations is combinatorially large, deciding what layers to share and where to branch out becomes cumbersome. Prior works have either relied on ad hoc methods to determine the level of layer sharing, which is suboptimal, or utilized neural architecture search techniques to establish the network design, which is considerably expensive. In this paper, we go beyond these limitations and propose an approach to automatically construct branched multi-task networks, by leveraging the employed tasks' affinities. Given a specific budget, i.e. number of learnable parameters, the proposed approach generates architectures, in which shallow layers are task-agnostic, whereas deeper ones gradually grow more task-specific. Extensive experimental analysis across numerous, diverse multi-tasking datasets shows that, for a given budget, our method consistently yields networks with the highest performance, while for a certain performance threshold it requires the least amount of learnable parameters.
System FR as Foundations for Stainless
Venue: arXiv cs.LO 2020
Year: 2020

We present the design, implementation, and foundation of a verifier for higher-order functional programs with generics and recursive data types. Our system supports proving safety and termination using preconditions, postconditions and assertions. It supports writing proof hints using assertions and recursive calls. To formalize the soundness of the system we introduce System FR, a calculus supporting System F polymorphism, dependent refinement types, and recursive types (including recursion through contravariant positions of function types). Through the use of sized types, System FR supports reasoning about termination of lazy data structures such as streams. We formalize a reducibility argument using the Coq proof assistant and prove the soundness of a type-checker with respect to call-by-value semantics, ensuring type safety and normalization for typeable programs. Our program verifier is implemented as an alternative verification-condition generator for the Stainless tool, which relies on existing SMT-based solver backend for automation. We demonstrate the efficiency of our approach by verifying a collection of higher-order functional programs comprising around 14000 lines of polymorphic higher-order Scala code, including graph search algorithms, basic number theory, monad laws, functional data structures, and assignments from popular Functional Programming MOOCs.
UG$^{2+}$ Track 2: A Collective Benchmark Effort for Evaluating and Advancing Image Understanding in Poor Visibility Environments
Venue: arXiv cs.CV 2020
Year: 2020

The UG$^{2+}$ challenge in IEEE CVPR 2019 aims to evoke a comprehensive discussion and exploration about how low-level vision techniques can benefit the high-level automatic visual recognition in various scenarios. In its second track, we focus on object or face detection in poor visibility enhancements caused by bad weathers (haze, rain) and low light conditions. While existing enhancement methods are empirically expected to help the high-level end task, that is observed to not always be the case in practice. To provide a more thorough examination and fair comparison, we introduce three benchmark sets collected in real-world hazy, rainy, and low-light conditions, respectively, with annotate objects/faces annotated. To our best knowledge, this is the first and currently largest effort of its kind. Baseline results by cascading existing enhancement and detection models are reported, indicating the highly challenging nature of our new data as well as the large room for further technical innovations. We expect a large participation from the broad research community to address these challenges together.
A review on Neural Turing Machine
Venue: arXiv cs.NE 2020
Year: 2020

One of the major objectives of Artificial Intelligence is to design learning algorithms that are executed on a general purposes computational machines such as human brain. Neural Turing Machine (NTM) is a step towards realizing such a computational machine. The attempt is made here to run a systematic review on Neural Turing Machine. First, the mind-map and taxonomy of machine learning, neural networks, and Turing machine are introduced. Next, NTM is inspected in terms of concepts, structure, variety of versions, implemented tasks, comparisons, etc. Finally, the paper discusses on issues and ends up with several future works.
Text-based depression detection on sparse data
Venue: arXiv cs.LG 2020
Year: 2020

Previous text-based depression detection is commonly based on large user-generated data. Sparse scenarios like clinical conversations are less investigated. This work proposes a text-based multi-task BGRU network with pretrained word embeddings to model patients' responses during clinical interviews. Our main approach uses a novel multi-task loss function, aiming at modeling both depression severity and binary health state. We independently investigate word- and sentence-level word-embeddings as well as the use of large-data pretraining for depression detection. To strengthen our findings, we report mean-averaged results for a multitude of independent runs on sparse data. First, we show that pretraining is helpful for word-level text-based depression detection. Second, our results demonstrate that sentence-level word-embeddings should be mostly preferred over word-level ones. While the choice of pooling function is less crucial, mean and attention pooling should be preferred over last-timestep pooling. Our method outputs depression presence results as well as predicted severity score, culminating a macro F1 score of 0.84 and MAE of 3.48 on the DAIC-WOZ development set.
ClinicalBERT: Modeling Clinical Notes and Predicting Hospital Readmission
Venue: arXiv cs.CL 2020
Year: 2020

Clinical notes contain information about patients that goes beyond structured data like lab values and medications. However, clinical notes have been underused relative to structured data, because notes are high-dimensional and sparse. This work develops and evaluates representations of clinical notes using bidirectional transformers (ClinicalBERT). ClinicalBERT uncovers high-quality relationships between medical concepts as judged by humans. ClinicalBert outperforms baselines on 30-day hospital readmission prediction using both discharge summaries and the first few days of notes in the intensive care unit. Code and model parameters are available.
Quasi-popular Matchings, Optimality, and Extended Formulations
Venue: arXiv cs.DS 2020
Year: 2020

Let G = ((A,B),E) be an instance of the stable marriage problem where every vertex ranks its neighbors in a strict order of preference. A matching M in G is popular if M does not lose a head-to-head election against any matching. Popular matchings are a well-studied generalization of stable matchings, introduced with the goal of enlarging the set of admissible solutions, while maintaining a certain level of fairness. Every stable matching is a min-size popular matching. Unfortunately, when there are edge costs, it is NP-hard to find a popular matching of minimum cost -- even worse, the min-cost popular matching problem is hard to approximate up to any factor. Let opt be the cost of a min-cost popular matching. Our goal is to efficiently compute a matching of cost at most opt by paying the price of mildly relaxing popularity. Our main positive results are two bi-criteria algorithms that find in polynomial time a near-popular or quasi-popular matching of cost at most opt. Moreover, one of the algorithms finds a quasi-popular matching of cost at most that of a min-cost popular fractional matching, which could be much smaller than opt. Key to the other algorithm is a polynomial-size extended formulation for an integral polytope sandwiched between the popular and quasi-popular matching polytopes. We complement these results by showing that it is NP-hard to find a quasi-popular matching of minimum cost, and that both the popular and quasi-popular matching polytopes have near-exponential extension complexity. This version of the paper goes beyond the conference version [12] in the following two points: (i) the algorithm for finding a quasi-popular matching of cost at most that of a min-cost popular fractional matching is new; (ii) the proofs from Section 6.1 and Section 7.3 are now self-contained (the conference version used constructions from [10] to show these lower bounds).
Towards Formalizing the GDPR's Notion of Singling Out
Venue: arXiv cs.CY 2020
Year: 2020

There is a significant conceptual gap between legal and mathematical thinking around data privacy. The effect is uncertainty as to which technical offerings adequately match expectations expressed in legal standards. The uncertainty is exacerbated by a litany of successful privacy attacks, demonstrating that traditional statistical disclosure limitation techniques often fall short of the sort of privacy envisioned by legal standards. We define predicate singling out, a new type of privacy attack intended to capture the concept of singling out appearing in the General Data Protection Regulation (GDPR). Informally, an adversary predicate singles out a dataset $X$ using the output of a data release mechanism $M(X)$ if it manages to find a predicate $p$ matching exactly one row $x \in X$ with probability much better than a statistical baseline. A data release mechanism that precludes such attacks is secure against predicate singling out (PSO secure). We argue that PSO security is a mathematical concept with legal consequences. Any data release mechanism that purports to "render anonymous" personal data under the GDPR must be secure against singling out, and hence must be PSO secure. We then analyze PSO security, showing that it fails to self-compose. Namely, a combination of $ω(\log n)$ exact counts, each individually PSO secure, enables an attacker to predicate single out. In fact, the composition of just two PSO-secure mechanisms can fail to provide PSO security. Finally, we ask whether differential privacy and $k$-anonymity are PSO secure. Leveraging a connection to statistical generalization, we show that differential privacy implies PSO security. However, $k$-anonymity does not: there exists a simple and general predicate singling out attack under mild assumptions on the $k$-anonymizer and the data distribution.
Towards Photographic Image Manipulation with Balanced Growing of Generative Autoencoders
Venue: arXiv cs.LG 2020
Year: 2020

We present a generative autoencoder that provides fast encoding, faithful reconstructions (eg. retaining the identity of a face), sharp generated/reconstructed samples in high resolutions, and a well-structured latent space that supports semantic manipulation of the inputs. There are no current autoencoder or GAN models that satisfactorily achieve all of these. We build on the progressively growing autoencoder model PIONEER, for which we completely alter the training dynamics based on a careful analysis of recently introduced normalization schemes. We show significantly improved visual and quantitative results for face identity conservation in CelebAHQ. Our model achieves state-of-the-art disentanglement of latent space, both quantitatively and via realistic image attribute manipulations. On the LSUN Bedrooms dataset, we improve the disentanglement performance of the vanilla PIONEER, despite having a simpler model. Overall, our results indicate that the PIONEER networks provide a way towards photorealistic face manipulation.
P-Optimal Proof Systems for Each NP-Complete Set but no Complete Disjoint NP-Pairs Relative to an Oracle
Venue: arXiv cs.CC 2020
Year: 2020

Pudlák [Pud17] lists several major conjectures from the field of proof complexity and asks for oracles that separate corresponding relativized conjectures. Among these conjectures are: - $\mathsf{DisjNP}$: The class of all disjoint NP-pairs does not have many-one complete elements. - $\mathsf{SAT}$: NP does not contain many-one complete sets that have P-optimal proof systems. - $\mathsf{UP}$: UP does not have many-one complete problems. - $\mathsf{NP}\cap\mathsf{coNP}$: $\text{NP}\cap\text{coNP}$ does not have many-one complete problems. As one answer to this question, we construct an oracle relative to which $\mathsf{DisjNP}$, $\neg \mathsf{SAT}$, $\mathsf{UP}$, and $\mathsf{NP}\cap\mathsf{coNP}$ hold, i.e., there is no relativizable proof for the implication $\mathsf{DisjNP}\wedge \mathsf{UP}\wedge \mathsf{NP}\cap\mathsf{coNP}\Rightarrow\mathsf{SAT}$. In particular, regarding the conjectures by Pudlák this extends a result by Khaniki [Kha19].
A Game-Theoretic Approach to Decision Making for Multiple Vehicles at Roundabout
Venue: arXiv cs.SY 2020
Year: 2020

In this paper, we study the decision making of multiple autonomous vehicles at a roundabout. The behaviours of the vehicles depend on their aggressiveness, which indicates how much they value speed over safety. We propose a distributed decision-making process that balances safety and speed of the vehicles. In the proposed process, each vehicle estimates other vehicles' aggressiveness and formulates the interactions among the vehicles as a finite sequential game. Based on the Nash equilibrium of this game, the vehicle predicts other vehicles' behaviours and makes decisions. We perform numerical simulations to illustrate the effectiveness of the proposed process, both for safety (absence of collisions), and speed (time spent within the roundabout).
Building Scalable Decentralized Payment Systems
Venue: arXiv cs.CR 2020
Year: 2020

Increasing the transactional throughput of decentralized blockchains in a secure manner has been the holy grail of blockchain research for most of the past decade. This paper introduces a scheme for scaling blockchains while retaining virtually identical security and decentralization, colloquially known as optimistic rollup. We propose a layer-2 scaling technique using a permissionless side chain with merged consensus. The side chain only supports functionality to transact UTXOs and transfer funds to and from a parent chain in a trust-minimized manner. Optimized implementation and engineering of client code, along with improvements to block propagation efficiency versus currently deployed systems, allow use of this side chain to scale well beyond the capacities exhibited by contemporary blockchains without undue resource demands on full nodes.