TITLE

Applying Sequence to expression modeling to experiment design and analysis

ABSTRACT

DNA sequence consists of coding and non-coding region. Coding regions are transcribed to mRNA and later translated to proteins, but the role of non-coding region which forms nearly 98% of the total DNA is not clear. Parts of non-coding region that contain binding sites for proteins called transcription factors (TFs) are known as enhancers. Enhancers are known to regulate the expression of nearby genes. We use Thermodynamic models to explain the expression of one gene based on the sequence of its enhancer, the relative concentration of its relevant TFs and known binding sites for each TF. Modeling approach leads to an ensemble of models in agreement with current data. In order to constrain the ensemble, we choose variants that distinguish our models the most and test them experimentally using massively parallel reporter assays. Refining the models using the experimental results helps us to unravel the complex regulatory network governing the expression of gene of interest.

TITLE

Randomness extraction from generalized Santha-Vazirani sources

ABSTRACT

Randomized algorithms and protocols require a source of randomness for their execution. However, in the real world most sources of randomness are imperfect. Randomness extraction is the process of turning a slightly random bit string into a shorter almost perfectly random string. A Santha-Vazirani (SV) source is a sequence of random bits where the conditional distribution of each bit, given the previous bits, can be partially controlled by an adversary. We talk about a generalization of SV sources for non-binary sequences. We show using "martingales" that unlike the binary case, deterministic randomness extraction in the generalized case is sometimes possible. We also consider a distributed version of SV sources in which the goal of the extraction is to obtain common randomness shared among different parties. We show using "maximal correlation" that randomness extraction in this distributed case essentially reduces to randomness extraction from (non-distributed) SV sources.

TITLE

Parallel Garbage collection in Solid State Drives

ABSTRACT

In the last decade NAND Flash-based SSDs have been widely adopted for high-end enterprise systems in an attempt to provide a high-performance and reliable storage. However, inferior performance is frequently attained mainly due to need for Garbage Collection (GC). GC in flash memory is the process of identifying and clearing the blocks of unneeded data to create space for the new data to be allocated. GC is high-latency operation and once it is scheduled it can increase latency for later arriving I/O requests. On the other hands, SSDs have high levels of parallelism provided by channels, chips, dies and planes, which is sometimes under-utilized due to the resource contention. In this work, we propose a novel GC strategy, which leverages plane-level parallelism to improve GC latency and reduce performance inconsistencies.

TITLE

Improving reliability, performance, and energy efficiency of STT-MRAM with dynamic write latency

ABSTRACT

High write latency and high write energy are the major challenges in Spin Transfer Torque Magnetic Random Access Memory (STT-MRAM) design. The write operation in STT-MRAM is of stochastic nature. Therefore, it requires a very long timing margin to maintain an acceptable level of reliability and yield. Traditionally, Error Correction Codes (ECCs) are used to reduce the timing margin in STT-MRAM. However, they impose high storage and latency overheads. In this talk, I present a low-cost architecture-level technique to significantly reduce the amount of required timing margin. This technique employs a handshaking protocol between the memory and its controller to dynamically determine the write latency at run-time. The simulation infrastructure comprehensively models the combined effect of process variation and stochastic write behavior at circuit-level and abstracts it to architecture-level. The simulation results show that this technique not only considerably reduces the write error rate but also improves the overall system performance on average by 15.4% compared to existing solutions.

TITLE

Beyond Supervised Deep Learning

ABSTRACT

Deep learning has transformed the way in which we design machine learning systems. In this talk I will provide a brief overview of modern advances to the deep learning paradigm. Starting off with deep reinforcement learning: DQN (Nature, 2015) and A3C (CoRR, 2015), I will then motivate the role of generative modelling in the emerging research landscape and discuss several recent models, including Pixel CNNs (ICML, 2016), AIR (NIPS, 2016) and Conditional 2D->3D (NIPS, 2016).

TITLE

Deep Learning Approaches to Structured Signal Recovery

ABSTRACT

The promise of compressive sensing (CS) has been offset by two significant challenges. First, real-world data is not exactly sparse in a fixed basis. Second, current high-performance recovery algorithms are slow to converge, which limits CS to either non-real-time applications or scenarios where massive back-end computing is available. We attack both of these challenges head-on by developing new signal recovery frameworks using deep learning techniques.

TITLE

Using Deep Neural Networks to Understand the Cell Identity by Expression Fingerprints

ABSTRACT

Understanding the cell identity is a critically important task in many biomedical areas, such as regenerative medicine and cancer research. The expression patterns of some marker genes have been used to assign the cells to a limited number of cell types. The limitations are unknown markers to accurately characterize many cell types, and the expression of markers in more than one cell type. A possible answer is using the whole-genome gene expression profiles (GEPs), but it has been computationally challenging to decide which genes can more accurately characterize the cell identity. Classical machine learning approaches, such as simple classification or clustering algorithms, have been applied for this problem as well as many other biological problems. Many aspects of biology, however, are much more sophisticated than can be modelled accurately using the simple approaches. During the past few years the deep learning methods have provided promising results in learning different patterns in games, images and video, etc. Their application in biology and health, however, has been limited. Here we analyzed a massive number of gene and miRNA expression profiles, measured by both Microarray and Next Generation Sequencing (NGS) platforms, to learn the more sphisticated biological properties of the data. After analyzing different architectures, we identified a specific artchitecture of the deep autoencoders that can compress the whole gene expression profiles into a small gene expression fingerprint (GEF) consisting of as few as 30 numeric values, that can reproduce the expression values of tens of thousands of genes with an accuracy comparable to technical replictes of the same experiment. We show that the scalars of the GEFs represent different biological pathways or processes, which are learned in an unsupervised approach. Furthermore, the cell identity can be inferred from the GEFs at very high accuracy, comparable to the state-of-the-art tools that work on the whole GEP.

TITLE

Extracting Sound from Silent Video

ABSTRACT

When sound waves propagate in air, they cause small vibrations when they hit objects. It has been shown that sound waves can be extracted by measuring these small vibrations in a video. In a recent work, we show that certain pixels in a video can record sound similar to a microphone. By studying local vibrations in detail, we isolate locations with higher sound quality and significantly improve sound quality. We also estimate incoming sound direction for the first time by measuring the delay between local sound readings. Finally, we reach real-time performance in 20KHz video by limiting computation to only a few localities.

TITLE

Advancements and challenges in quantum computers and quantum networks

ABSTRACT

Over the past few decades, from a long standing effort by generations of scientist trying to understand the fundamentals of quantum mechanics, new concepts has emerged which is known as quantum computers and quantum networks. These platforms take advantage of parallel interaction between quantum two level systems – known as quantum bits (qbit) – in order to deliver efficient and novel techniques for some of the computational tasks that is either impossible or extremely difficult to solve via classical computers. This opens a new era in computer science not only to extend our computational capabilities but also paves the way for an unexplored regime that previously was not accessible with classical computers. On the other hand, quantum laws can be used in secure communication. Over the past years, scientist introduced several communication protocols that are impossible to hack and its security is guaranteed by the fundamental laws of quantum mechanics. These mostly theoretical achievements has raised interest among many researchers around the world in order to realize the quantum computers and quantum communication. In this talk we will review some of the basics of quantum computers and quantum communication protocol and their advantages compare to classical computers and finally discuss the experimental challenges in creating these platforms. In this talk, we start by reviewing some basics about quantum mechanics, especially how quantum computers and quantum communication protocols are deeply connected to the concepts of entanglement and act of measurements in quantum mechanics. Then we briefly review the building blocks of quantum computers, known as quantum gates and the basic working principles of quantum computers. In the next step we discuss how quantum computers can solve some class of computational tasks in a more efficient way by taking advantages of their large Hilbert space and briefly introduce the Shor’s algorithm as an example. Next we review some of the experimental challenges in building the quantum computers and especially discuss how temperature pose a fundamental limit on quantum computers via the process of thermal decoherence. Next we briefly introduce several experimental platforms such as superconducting circuits, atom trapping and etc. which was studied by researchers in recent years. Finally we will see in more details how nano-mechanical oscillator can play a role as a novel platform for some applications in quantum computer domain such as quantum memories and quantum transducers.

TITLE

Nearly optimal Sparse FF

ABSTRACT

The problem of approximately computing the k dominant Fourier coefficients of a vector quickly and using few samples in time domain is known as the Sparse Fourier Transform (Sparse FFT) problem. A long line of work on Sparse FFT has resulted in algorithms with O(k log⁡n log⁡〖(n/k)〗) runtime and O(k log⁡n) sample complexity [Hassanieh et al’STOC’12]. The mentioned result is non-adaptive, and is essentially the best possible under the sparsity assumption alone: It is known that even adaptive algorithms must use Ω((k log⁡n)/log⁡log⁡n ) samples [Hassanieh et al, STOC’12]. We consider the problem of computing the k-sparse approximation to the discrete Fourier transform of an n-dimensional signal. The following are presented in [Hassanieh et al’STOC’12]: • An O(k log⁡n)-time randomized algorithm for the case where the input signal has at most k non-zero Fourier coefficients, and • An O(k log⁡n log⁡〖(n/k)〗)-time randomized algorithm for general input signals. Both algorithms achieve o(n log⁡n) time, and thus improve over the Fast Fourier Transform, for any k=o(n). They are the first known algorithms that satisfy this property. Also, if one assumes that the Fast Fourier Transform is optimal, the algorithm for the exactly k-sparse case is optimal for any k=n^(Ω(1)).

TITLE

How to Architect a Query Compiler

ABSTRACT

In this talk we study architecting query compilers. The state of the art in query compiler construction is lagging behind that in the compilers field. We attempt to remedy this by exploring the key causes of technical challenges in need of well founded solutions, and by gathering the most relevant ideas and approaches from the PL and compilers communities for easy digestion by database researchers. All query compilers known to us are more or less monolithic template expanders that do the bulk of the compilation task in one large leap. Such systems are hard to build and maintain. We propose to use a stack of multiple DSLs on different levels of abstraction with lowering in multiple steps to make query compilers easier to build and extend, ultimately allowing us to create more convincing and sustainable compiler-based data management systems. We attempt to derive our advice for creating such DSL stacks from widely acceptable principles. We have also re-created a well-known query compiler following these ideas and report on this effort.

TITLE

The Application of Game Theory in Analyzing Public Health Issues

ABSTRACT

This research introduces a variation of the Bertrand price game, in which production capacity constraints and product differentiation are incorporated. Equilibrium prices in both pure strategy and mixed strategy are sought. Complete characterization of mixed strategy equilibrium in such games is introduced. The game is applied to identify the equilibrium prices of the vaccines sold in the US pediatric vaccine market. The results provide insights for pediatric healthcare community, including federal government officials and vaccine manufacturers who are seeking effective pricing strategies.

TITLE

Practical vs Theoretical Computer Science

ABSTRACT

In this talk we focus on the Travelling Salesman Problem in two different settings. First we focus on the theoretical results for this problem, then we continue by introducing one on the applications of this problem in real world. The application that we discuss is “over-night bike rebalancing”. We present the state of the art algorithm that Citibike, the biggest bike sharing company in US, is currently using.

TITLE

Real-Time Optimization of Personalized Assortments

ABSTRACT

Motivated by the availability of real-time data on customer characteristics, we consider the problem of personalizing the assortment of products for each arriving customer. Using actual sales data from an online retailer, we demonstrate that personalization based on each customer’s location can lead to over 10% improvements in revenue compared to a policy that treats all customers the same. We propose a family of index-based policies that effectively coordinate the real-time assortment decisions with the backend supply chain constraints. We allow the demand process to be arbitrary and prove that our algorithms achieve an optimal competitive ratio. In addition, we show that our algorithms perform even better if the demand is known to be stationary. Our approach is also flexible and can be combined with existing methods in the literature, resulting in a hybrid algorithm that brings out the advantages of other methods while maintaining the worst-case performance guarantees

TITLE

Exploiting Experts' Knowledge for Structure Learning of Bayesian Networks

TITLE

How Deep Learning shapes the future of Bioinformatics

ABSTRACT

In this talk we go over different aspects of Bioinformatics and show how Machine Learning and specifically Deep Learning will have such an impact that future Bioinformaticians are none but Computer Scientists specialized on Deep Learning. We show how Google and Microsoft are the ones that not only lead bioinformatics but also can monopolize this industry. What we call Bioinformatics today will be the blueprint of manufacturing of all kind of products from foods and drugs to batteries, solar cells, industrial and construction materials. Such an explosion of applications are not possible without turning to deep learning as the core engine of deciphering the protein-DNA interaction and designing new strands of RNA-DNA. This talk covers the following topics - Primary Analysis - Downstream or Secondary Analysis - Genome-Wide Association Study (GWAS) - Genetic Origami - CRISPR-CAS9

TITLE

Sparse robust expander

ABSTRACT

One of the most exciting developments in combinatorics in the past four decades is that of expanders. It was first introduced to construct networks (represented by graphs) that are economical (sparse) and robust (highly connected). Depending on the perspective, expanders can be defined in various different ways. From the algebraic point of view, expanders are the graphs with large spectral gap; from the probabilistic point of view, random walks on expanders are rapidly mixing; and from the graph theoretic point of view, an expander is a graph whose vertex subsets have `large' boundaries. Due to this nature, expanders have found applications in other areas of mathematics and theoretical computer science. In this talk, I will present an embedding strategy using a notion of sublinear expander first introduced by Komlos and Szemeredi. As applications, it settles a conjecture of Mader in $1999$ on large clique-subdivisions in dense graphs without $4$-cycles. Joint work with Jozsef Balogh and Hong Liu.

TITLE

The problem of relevant features in distributions: Learning and Testing Junta Distributions

ABSTRACT

We consider the problem of learning distributions in the presence of irrelevant features. This problem is formalized by introducing a new notion of k-junta distributions. Informally, a distribution D over the domain Xⁿ is k-junta distribution with respect to another distribution U over the same domain if there is a set J ⊆ n of size |J| ≤ k that captures the difference between D and U. We show that it is possible to learn k-junta distributions with respect to the uniform distribution over the Boolean hypercube {0, 1}ⁿ in time poly(n^k, 1/ε). This result is obtained via a new Fourier-based learning algorithm inspired by the Low-Degree Algorithm of Linial, Mansour, and Nisan (1993). We also consider the problem of testing whether an unknown distribution is a k-junta distribution with respect to the uniform distribution. We give a nearly-optimal algorithm for this task. Both the analysis of the algorithm and the lower bound showing its optimality are obtained by establishing connections between the problem of testing junta distributions and testing uniformity of weighted collections of distributions.

TITLE

Synaptic Plasticity Rules: Neural Substrates of Learning

ABSTRACT

One of the most significant characteristics of our brain is the ability of quick learning and adaptation. In order to unravel the mysteries behind learning, we need to have a strong theoretical framework that explains how a network of neurons can efficiently process huge amount of information. In this talk, I will focus on theoretical cornerstone of synaptic plasticity rules that can be used to describe behavioral properties of memory formation and action learning in the brain. I will describe two general classes of (Hebbian and neo-Hebbian) learning rules, and demonstrate how they can be used for general paradigms of learning in unsupervised and reinforcement-based fashion, respectively. I will specifically focus on models of plasticity that are under the influence of global factors (such as reward or surprise) which can represent the action of one or several neuromodulators, attentional control, or feedback from large populations of neurons.

TITLE

Repairing Transaction Conflicts in Optimistic Multi-Version Concurrency Control

ABSTRACT

The optimistic variants of Multi-Version Concurrency Control (MVCC) avoid blocking concurrent transactions at the cost of having a validation phase. Upon failure in the validation phase, the transaction is usually aborted and restarted from scratch. The “abort and restart” approach becomes a performance bottleneck for use cases with high contention objects or long running transactions. In addition, restarting from scratch creates a negative feedback loop in the system, because the system incurs additional overhead that may create even more conflicts. In this paper, we propose a novel approach for conflict resolution in MVCC for in-memory databases. This low overhead approach summarizes the transaction programs in the form of a dependency graph. The dependency graph also contains the constructs used in the validation phase of the MVCC algorithm. Then, when encountering conflicts among transactions, our mechanism quickly detects the conflict locations in the program and partially re-executes the conflicting transactions. This approach maximizes the reuse of the computations done in the initial execution round, and increases the transaction processing throughput.

TITLE

Robustness of Image Classifiers

ABSTRACT

In this talk, we will present tools to assess the robustness of image classifiers to a diverse set of perturbations, ranging from adversarial to random noise. In particular, we will propose a semi-random noise regime that generalizes both the random and adversarial noise regimes. We provide theoretical bounds on the robustness of classifiers in this general regime, which depends on the curvature of the classifier's decision boundary. In a final part of the talk, we will show how it can explain the surprising existence of universal perturbation images that cause most natural images to be misclassified by state-of-the-art deep neural network classifiers.

TITLE

Online Stochastic Optimisation for Large-Scale Machine Learning Problems in Big Data

ABSTRACT

Support vector machine (SVM) is considered as the standard technique for a wide range of data classification problems in many different fields, such as cancer diagnostic in bioinformatics, image classification, face recognition in computer vision and text categorisation in document processing. However, in a big data environment, computing the SVM classifier amounts to solve a large-scale optimisation which is mathematically complex and computationally expensive and the existing optimisation methods would not be fast enough. The main objective of this talk is to propose an accelerated stochastic optimisation method to solve SVMs for big data applications, which benefits from fast convergence, low complexity and easy implementation. The convergence analysis of the new method is theoretically investigated and also using some real-world data sets, the proposed algorithm is compared to the existing state of the art algorithms. Numerical results show that the proposed method significantly outperforms the existing schemes with orders of magnitude higher convergence rate.

TITLE

Parallel Garbage collection in Solid State Drives

ABSTRACT

In the last decade NAND Flash-based SSDs have been widely adopted for high-end enterprise systems in an attempt to provide a high-performance and reliable storage. However, inferior performance is frequently attained mainly due to need for Garbage Collection (GC). GC in flash memory is the process of identifying and clearing the blocks of unneeded data to create space for the new data to be allocated. GC is high-latency operation and once it is scheduled it can increase latency for later arriving I/O requests. On the other hands, SSDs have high levels of parallelism provided by channels, chips, dies and planes, which is sometimes under-utilized due to the resource contention. In this work, we propose a novel GC strategy, which leverages plane-level parallelism to improve GC latency and reduce performance inconsistencies.

TITLE

Code Obfuscation from Encryption?

ABSTRACT

Code obfuscation can be seen as "encrypting" a "program" in a way that allows us to run it, while keeping its implementation as hidden as possible. So it is natural to ask whether code obfuscation could be based on very strong recently developed forms of encryption such as: witness encryption, predicate encryption, or functional encryption. In this talk, I will describe what these primitives are, and then I will describe a set of positive and negative results that give almost a full picture for the question above.

TITLE

Automated Visual Inspection for Industrial Quality Assurance

ABSTRACT

In the manufacturing process, an inspection is aimed at determining if a product deviates from a set of given specifications. Depending on the demands and the product features, different visual inspection techniques are typically applied in industry, including but not limited to, laser triangulation, fringe projection, and deflectometry. The inspection setups have often several degrees of freedom including the position and orientation of the cameras and the illuminations, as well as their optical configurations. A manual setup design for inspecting complicated products, such as an engine block, requires a tedious trial-and-error process, associated with high costs and often non-optimal results. This talk will give an overview of different visual techniques used for industrial 3D scanning, starting from the traditional stereo reconstruction to specific technical solutions. Moreover, I will introduce the “Inspection Planning” problem for optimizing the sequence of sensor acquisitions to best scan a product. To quantify an inspection quality, we formulate the amount of information an acquisition delivers, as a reduction of our uncertainty about the product surface, using a Bayesian framework. This is then used an optimization cost fuction for the planning problem.This talk will also cover topics regarding the physically-based computer graphics simulation of images, and methods for quantification of the measurement uncertainty in an optical measurement.

TITLE

Applications of Matrix Factorization in signal processing

ABSTRACT

Matrix factorization-that is, representing a signal by suitable basis functions is widely used in machine learning, image denoising, signal processing and neuroscience. This problem usually comes with two main assumptions about the signal: the signal’s components either are independent or sparse. More precisely, in the independent-component analysis (ICA), the signal considered is a mixture of some independent sources. Source separation is one example for ICA. In contrast, in the sparse component analysis (SCA), the signal is assumed to be a mixture of sparse sources. We present an overview of the ICA and SCA from the matrix factorization point of view.

TITLE

Continuous Distributed Representation of Biological Sequences and Their Applications in Bioinformatics

ABSTRACT

Biophysical and biochemical principles govern biological sequences (e.g., DNA, RNA, and protein sequences) similar to the way grammar of a natural language determines the structure of clauses and sentences. This analogy motivates ‘life language processing’, i.e. treating biological sequences as the output of a certain language and adopt/develop language processing methods to preform analyses and predictions in that language. We propose two specific aims for life language processing: (1) Developing computational linguistics representation learning for biological sequences: the large gap between the number of known sequences (raw data) versus the number of known functions/structures associated with these sequences (meta-data), encourage us to develop methods that can obtain prior knowledge from the existing sequences. Continuous vector representations of words known as word vectors have recently become popular in natural language processing (NLP) as an efficient unsupervised approach to represent semantic/syntactic units of text helping in the downstream NLP tasks (e.g., machine translation, part-of-speech tagging, information retrieval, etc.). In this work, we propose distributed vector representations of biological sequence segments (n-grams), called bio-vectors, using skip-gram neural network. We propose intrinsic evaluation of bio-vectors by measuring the continuity of the underlying biophysical and biochemical properties (e.g., average mass, hydrophobicity, charge, and etc.). In addition to intrinsic evaluations, for the purpose of extrinsic evaluations, we have employed this representation in classification of 324018 protein sequences belonging to 7027 protein families, where an average family classification accuracy of 93%±0.06% was obtained. In addition, incorporation of bio-vector representation versus one-hot vector features in Maxmargin Markov Network (M3Net) for intron-exon prediction and domain identification tasks could improve the sequence labeling accuracy from 73.84% to 74.99% and from 82.4% to 89.8%, respectively. (2) Performing computational linguistics comparison of genomic language variations: the purpose of this aim is to quantify the distances between syntactic and semantic features of two genomic language variations, with various applications in comparative genomics. Training model of bio-vectors is analogous to neural probabilistic language modeling. Hence, such representations can characterize sequences in terms of underlying biochemical and biophysical patterns. This makes the network of n-grams in this space an indirect representation of the underlying language model. Considering this fact, we propose a new quantitative measure of distance between genomic language variations based on the divergence between networks of ngrams in different genetic variations, called word embedding language divergence. We perform language comparison for the coding regions in the genomes of 12 different organisms (4 plants, 6 animals, and two human subjects). Our results confirm a significant high-level difference in the genetic language model of humans/animals versus plants. The proposed method is a step toward defining a new quantitative measure of similarity between genomic languages, with applications in characterization/classification of sequences of interest.