Paper Group ANR 319
Rates of Convergence of Spectral Methods for Graphon Estimation. Estimating Mixed Memberships with Sharp Eigenvector Deviations. Two provably consistent divide and conquer clustering algorithms for large networks. Denoising random forests. Ubenwa: Cry-based Diagnosis of Birth Asphyxia. A Sparse Graph-Structured Lasso Mixed Model for Genetic Associa …
Rates of Convergence of Spectral Methods for Graphon Estimation
| Title | Rates of Convergence of Spectral Methods for Graphon Estimation |
| Authors | Jiaming Xu |
| Abstract | This paper studies the problem of estimating the grahpon model - the underlying generating mechanism of a network. Graphon estimation arises in many applications such as predicting missing links in networks and learning user preferences in recommender systems. The graphon model deals with a random graph of $n$ vertices such that each pair of two vertices $i$ and $j$ are connected independently with probability $\rho \times f(x_i,x_j)$, where $x_i$ is the unknown $d$-dimensional label of vertex $i$, $f$ is an unknown symmetric function, and $\rho$ is a scaling parameter characterizing the graph sparsity. Recent studies have identified the minimax error rate of estimating the graphon from a single realization of the random graph. However, there exists a wide gap between the known error rates of computationally efficient estimation procedures and the minimax optimal error rate. Here we analyze a spectral method, namely universal singular value thresholding (USVT) algorithm, in the relatively sparse regime with the average vertex degree $n\rho=\Omega(\log n)$. When $f$ belongs to H"{o}lder or Sobolev space with smoothness index $\alpha$, we show the error rate of USVT is at most $(n\rho)^{ -2 \alpha / (2\alpha+d)}$, approaching the minimax optimal error rate $\log (n\rho)/(n\rho)$ for $d=1$ as $\alpha$ increases. Furthermore, when $f$ is analytic, we show the error rate of USVT is at most $\log^d (n\rho)/(n\rho)$. In the special case of stochastic block model with $k$ blocks, the error rate of USVT is at most $k/(n\rho)$, which is larger than the minimax optimal error rate by at most a multiplicative factor $k/\log k$. This coincides with the computational gap observed for community detection. A key step of our analysis is to derive the eigenvalue decaying rate of the edge probability matrix using piecewise polynomial approximations of the graphon function $f$. |
| Tasks | Community Detection, Graphon Estimation, Recommendation Systems |
| Published | 2017-09-10 |
| URL | http://arxiv.org/abs/1709.03183v1 |
| http://arxiv.org/pdf/1709.03183v1.pdf | |
| PWC | https://paperswithcode.com/paper/rates-of-convergence-of-spectral-methods-for |
| Repo | |
| Framework | |
Estimating Mixed Memberships with Sharp Eigenvector Deviations
| Title | Estimating Mixed Memberships with Sharp Eigenvector Deviations |
| Authors | Xueyu Mao, Purnamrita Sarkar, Deepayan Chakrabarti |
| Abstract | We consider the problem of estimating community memberships of nodes in a network, where every node is associated with a vector determining its degree of membership in each community. Existing provably consistent algorithms often require strong assumptions about the population, are computationally expensive, and only provide an overall error bound for the whole community membership matrix. This paper provides uniform rates of convergence for the inferred community membership vector of each node in a network generated from the Mixed Membership Stochastic Blockmodel (MMSB); to our knowledge, this is the first work to establish per-node rates for overlapping community detection in networks. We achieve this by establishing sharp row-wise eigenvector deviation bounds for MMSB. Based on the simplex structure inherent in the eigen-decomposition of the population matrix, we build on established corner-finding algorithms from the optimization community to infer the community membership vectors. Our results hold over a broad parameter regime where the average degree only grows poly-logarithmically with the number of nodes. Using experiments with simulated and real datasets, we show that our method achieves better error with lower variability over competing methods, and processes real world networks of up to 100,000 nodes within tens of seconds. |
| Tasks | Community Detection |
| Published | 2017-09-01 |
| URL | https://arxiv.org/abs/1709.00407v3 |
| https://arxiv.org/pdf/1709.00407v3.pdf | |
| PWC | https://paperswithcode.com/paper/estimating-mixed-memberships-with-sharp |
| Repo | |
| Framework | |
Two provably consistent divide and conquer clustering algorithms for large networks
| Title | Two provably consistent divide and conquer clustering algorithms for large networks |
| Authors | Soumendu Sundar Mukherjee, Purnamrita Sarkar, Peter J. Bickel |
| Abstract | In this article, we advance divide-and-conquer strategies for solving the community detection problem in networks. We propose two algorithms which perform clustering on a number of small subgraphs and finally patches the results into a single clustering. The main advantage of these algorithms is that they bring down significantly the computational cost of traditional algorithms, including spectral clustering, semi-definite programs, modularity based methods, likelihood based methods etc., without losing on accuracy and even improving accuracy at times. These algorithms are also, by nature, parallelizable. Thus, exploiting the facts that most traditional algorithms are accurate and the corresponding optimization problems are much simpler in small problems, our divide-and-conquer methods provide an omnibus recipe for scaling traditional algorithms up to large networks. We prove consistency of these algorithms under various subgraph selection procedures and perform extensive simulations and real-data analysis to understand the advantages of the divide-and-conquer approach in various settings. |
| Tasks | Community Detection |
| Published | 2017-08-18 |
| URL | http://arxiv.org/abs/1708.05573v1 |
| http://arxiv.org/pdf/1708.05573v1.pdf | |
| PWC | https://paperswithcode.com/paper/two-provably-consistent-divide-and-conquer |
| Repo | |
| Framework | |
Denoising random forests
| Title | Denoising random forests |
| Authors | Masaya Hibino, Akisato Kimura, Takayoshi Yamashita, Yuji Yamauchi, Hironobu Fujiyoshi |
| Abstract | This paper proposes a novel type of random forests called a denoising random forests that are robust against noises contained in test samples. Such noise-corrupted samples cause serious damage to the estimation performances of random forests, since unexpected child nodes are often selected and the leaf nodes that the input sample reaches are sometimes far from those for a clean sample. Our main idea for tackling this problem originates from a binary indicator vector that encodes a traversal path of a sample in the forest. Our proposed method effectively employs this vector by introducing denoising autoencoders into random forests. A denoising autoencoder can be trained with indicator vectors produced from clean and noisy input samples, and non-leaf nodes where incorrect decisions are made can be identified by comparing the input and output of the trained denoising autoencoder. Multiple traversal paths with respect to the nodes with incorrect decisions caused by the noises can then be considered for the estimation. |
| Tasks | Denoising |
| Published | 2017-10-30 |
| URL | http://arxiv.org/abs/1710.11004v1 |
| http://arxiv.org/pdf/1710.11004v1.pdf | |
| PWC | https://paperswithcode.com/paper/denoising-random-forests |
| Repo | |
| Framework | |
Ubenwa: Cry-based Diagnosis of Birth Asphyxia
| Title | Ubenwa: Cry-based Diagnosis of Birth Asphyxia |
| Authors | Charles C Onu, Innocent Udeogu, Eyenimi Ndiomu, Urbain Kengni, Doina Precup, Guilherme M Sant’anna, Edward Alikor, Peace Opara |
| Abstract | Every year, 3 million newborns die within the first month of life. Birth asphyxia and other breathing-related conditions are a leading cause of mortality during the neonatal phase. Current diagnostic methods are too sophisticated in terms of equipment, required expertise, and general logistics. Consequently, early detection of asphyxia in newborns is very difficult in many parts of the world, especially in resource-poor settings. We are developing a machine learning system, dubbed Ubenwa, which enables diagnosis of asphyxia through automated analysis of the infant cry. Deployed via smartphone and wearable technology, Ubenwa will drastically reduce the time, cost and skill required to make accurate and potentially life-saving diagnoses. |
| Tasks | |
| Published | 2017-11-17 |
| URL | http://arxiv.org/abs/1711.06405v1 |
| http://arxiv.org/pdf/1711.06405v1.pdf | |
| PWC | https://paperswithcode.com/paper/ubenwa-cry-based-diagnosis-of-birth-asphyxia |
| Repo | |
| Framework | |
A Sparse Graph-Structured Lasso Mixed Model for Genetic Association with Confounding Correction
| Title | A Sparse Graph-Structured Lasso Mixed Model for Genetic Association with Confounding Correction |
| Authors | Wenting Ye, Xiang Liu, Haohan Wang, Eric P. Xing |
| Abstract | While linear mixed model (LMM) has shown a competitive performance in correcting spurious associations raised by population stratification, family structures, and cryptic relatedness, more challenges are still to be addressed regarding the complex structure of genotypic and phenotypic data. For example, geneticists have discovered that some clusters of phenotypes are more co-expressed than others. Hence, a joint analysis that can utilize such relatedness information in a heterogeneous data set is crucial for genetic modeling. We proposed the sparse graph-structured linear mixed model (sGLMM) that can incorporate the relatedness information from traits in a dataset with confounding correction. Our method is capable of uncovering the genetic associations of a large number of phenotypes together while considering the relatedness of these phenotypes. Through extensive simulation experiments, we show that the proposed model outperforms other existing approaches and can model correlation from both population structure and shared signals. Further, we validate the effectiveness of sGLMM in the real-world genomic dataset on two different species from plants and humans. In Arabidopsis thaliana data, sGLMM behaves better than all other baseline models for 63.4% traits. We also discuss the potential causal genetic variation of Human Alzheimer’s disease discovered by our model and justify some of the most important genetic loci. |
| Tasks | |
| Published | 2017-11-11 |
| URL | http://arxiv.org/abs/1711.04162v1 |
| http://arxiv.org/pdf/1711.04162v1.pdf | |
| PWC | https://paperswithcode.com/paper/a-sparse-graph-structured-lasso-mixed-model |
| Repo | |
| Framework | |
How will the Internet of Things enable Augmented Personalized Health?
| Title | How will the Internet of Things enable Augmented Personalized Health? |
| Authors | Amit Sheth, Utkarshani Jaimini, Hong Yung Yip |
| Abstract | Internet-of-Things (IoT) is profoundly redefining the way we create, consume, and share information. Health aficionados and citizens are increasingly using IoT technologies to track their sleep, food intake, activity, vital body signals, and other physiological observations. This is complemented by IoT systems that continuously collect health-related data from the environment and inside the living quarters. Together, these have created an opportunity for a new generation of healthcare solutions. However, interpreting data to understand an individual’s health is challenging. It is usually necessary to look at that individual’s clinical record and behavioral information, as well as social and environmental information affecting that individual. Interpreting how well a patient is doing also requires looking at his adherence to respective health objectives, application of relevant clinical knowledge and the desired outcomes. We resort to the vision of Augmented Personalized Healthcare (APH) to exploit the extensive variety of relevant data and medical knowledge using Artificial Intelligence (AI) techniques to extend and enhance human health to presents various stages of augmented health management strategies: self-monitoring, self-appraisal, self-management, intervention, and disease progress tracking and prediction. kHealth technology, a specific incarnation of APH, and its application to Asthma and other diseases are used to provide illustrations and discuss alternatives for technology-assisted health management. Several prominent efforts involving IoT and patient-generated health data (PGHD) with respect converting multimodal data into actionable information (big data to smart data) are also identified. Roles of three components in an evidence-based semantic perception approach- Contextualization, Abstraction, and Personalization are discussed. |
| Tasks | |
| Published | 2017-12-31 |
| URL | http://arxiv.org/abs/1801.00356v1 |
| http://arxiv.org/pdf/1801.00356v1.pdf | |
| PWC | https://paperswithcode.com/paper/how-will-the-internet-of-things-enable |
| Repo | |
| Framework | |
Unsupervised Document Embedding With CNNs
| Title | Unsupervised Document Embedding With CNNs |
| Authors | Chundi Liu, Shunan Zhao, Maksims Volkovs |
| Abstract | We propose a new model for unsupervised document embedding. Leading existing approaches either require complex inference or use recurrent neural networks (RNN) that are difficult to parallelize. We take a different route and develop a convolutional neural network (CNN) embedding model. Our CNN architecture is fully parallelizable resulting in over 10x speedup in inference time over RNN models. Parallelizable architecture enables to train deeper models where each successive layer has increasingly larger receptive field and models longer range semantic structure within the document. We additionally propose a fully unsupervised learning algorithm to train this model based on stochastic forward prediction. Empirical results on two public benchmarks show that our approach produces comparable to state-of-the-art accuracy at a fraction of computational cost. |
| Tasks | Document Embedding |
| Published | 2017-11-11 |
| URL | http://arxiv.org/abs/1711.04168v3 |
| http://arxiv.org/pdf/1711.04168v3.pdf | |
| PWC | https://paperswithcode.com/paper/unsupervised-document-embedding-with-cnns |
| Repo | |
| Framework | |
Batch-normalized joint training for DNN-based distant speech recognition
| Title | Batch-normalized joint training for DNN-based distant speech recognition |
| Authors | Mirco Ravanelli, Philemon Brakel, Maurizio Omologo, Yoshua Bengio |
| Abstract | Improving distant speech recognition is a crucial step towards flexible human-machine interfaces. Current technology, however, still exhibits a lack of robustness, especially when adverse acoustic conditions are met. Despite the significant progress made in the last years on both speech enhancement and speech recognition, one potential limitation of state-of-the-art technology lies in composing modules that are not well matched because they are not trained jointly. To address this concern, a promising approach consists in concatenating a speech enhancement and a speech recognition deep neural network and to jointly update their parameters as if they were within a single bigger network. Unfortunately, joint training can be difficult because the output distribution of the speech enhancement system may change substantially during the optimization procedure. The speech recognition module would have to deal with an input distribution that is non-stationary and unnormalized. To mitigate this issue, we propose a joint training approach based on a fully batch-normalized architecture. Experiments, conducted using different datasets, tasks and acoustic conditions, revealed that the proposed framework significantly overtakes other competitive solutions, especially in challenging environments. |
| Tasks | Distant Speech Recognition, Speech Enhancement, Speech Recognition |
| Published | 2017-03-24 |
| URL | http://arxiv.org/abs/1703.08471v1 |
| http://arxiv.org/pdf/1703.08471v1.pdf | |
| PWC | https://paperswithcode.com/paper/batch-normalized-joint-training-for-dnn-based |
| Repo | |
| Framework | |
The Effect of Different Writing Tasks on Linguistic Style: A Case Study of the ROC Story Cloze Task
| Title | The Effect of Different Writing Tasks on Linguistic Style: A Case Study of the ROC Story Cloze Task |
| Authors | Roy Schwartz, Maarten Sap, Ioannis Konstas, Li Zilles, Yejin Choi, Noah A. Smith |
| Abstract | A writer’s style depends not just on personal traits but also on her intent and mental state. In this paper, we show how variants of the same writing task can lead to measurable differences in writing style. We present a case study based on the story cloze task (Mostafazadeh et al., 2016a), where annotators were assigned similar writing tasks with different constraints: (1) writing an entire story, (2) adding a story ending for a given story context, and (3) adding an incoherent ending to a story. We show that a simple linear classifier informed by stylistic features is able to successfully distinguish among the three cases, without even looking at the story context. In addition, combining our stylistic features with language model predictions reaches state of the art performance on the story cloze challenge. Our results demonstrate that different task framings can dramatically affect the way people write. |
| Tasks | Language Modelling |
| Published | 2017-02-07 |
| URL | http://arxiv.org/abs/1702.01841v3 |
| http://arxiv.org/pdf/1702.01841v3.pdf | |
| PWC | https://paperswithcode.com/paper/the-effect-of-different-writing-tasks-on |
| Repo | |
| Framework | |
A network of deep neural networks for distant speech recognition
| Title | A network of deep neural networks for distant speech recognition |
| Authors | Mirco Ravanelli, Philemon Brakel, Maurizio Omologo, Yoshua Bengio |
| Abstract | Despite the remarkable progress recently made in distant speech recognition, state-of-the-art technology still suffers from a lack of robustness, especially when adverse acoustic conditions characterized by non-stationary noises and reverberation are met. A prominent limitation of current systems lies in the lack of matching and communication between the various technologies involved in the distant speech recognition process. The speech enhancement and speech recognition modules are, for instance, often trained independently. Moreover, the speech enhancement normally helps the speech recognizer, but the output of the latter is not commonly used, in turn, to improve the speech enhancement. To address both concerns, we propose a novel architecture based on a network of deep neural networks, where all the components are jointly trained and better cooperate with each other thanks to a full communication scheme between them. Experiments, conducted using different datasets, tasks and acoustic conditions, revealed that the proposed framework can overtake other competitive solutions, including recent joint training approaches. |
| Tasks | Distant Speech Recognition, Speech Enhancement, Speech Recognition |
| Published | 2017-03-23 |
| URL | http://arxiv.org/abs/1703.08002v1 |
| http://arxiv.org/pdf/1703.08002v1.pdf | |
| PWC | https://paperswithcode.com/paper/a-network-of-deep-neural-networks-for-distant |
| Repo | |
| Framework | |
Community detection in networks via nonlinear modularity eigenvectors
| Title | Community detection in networks via nonlinear modularity eigenvectors |
| Authors | Francesco Tudisco, Pedro Mercado, Matthias Hein |
| Abstract | Revealing a community structure in a network or dataset is a central problem arising in many scientific areas. The modularity function $Q$ is an established measure quantifying the quality of a community, being identified as a set of nodes having high modularity. In our terminology, a set of nodes with positive modularity is called a \textit{module} and a set that maximizes $Q$ is thus called \textit{leading module}. Finding a leading module in a network is an important task, however the dimension of real-world problems makes the maximization of $Q$ unfeasible. This poses the need of approximation techniques which are typically based on a linear relaxation of $Q$, induced by the spectrum of the modularity matrix $M$. In this work we propose a nonlinear relaxation which is instead based on the spectrum of a nonlinear modularity operator $\mathcal M$. We show that extremal eigenvalues of $\mathcal M$ provide an exact relaxation of the modularity measure $Q$, however at the price of being more challenging to be computed than those of $M$. Thus we extend the work made on nonlinear Laplacians, by proposing a computational scheme, named \textit{generalized RatioDCA}, to address such extremal eigenvalues. We show monotonic ascent and convergence of the method. We finally apply the new method to several synthetic and real-world data sets, showing both effectiveness of the model and performance of the method. |
| Tasks | Community Detection |
| Published | 2017-08-18 |
| URL | http://arxiv.org/abs/1708.05569v2 |
| http://arxiv.org/pdf/1708.05569v2.pdf | |
| PWC | https://paperswithcode.com/paper/community-detection-in-networks-via-nonlinear |
| Repo | |
| Framework | |
Multi-Focus Image Fusion Using Sparse Representation and Coupled Dictionary Learning
| Title | Multi-Focus Image Fusion Using Sparse Representation and Coupled Dictionary Learning |
| Authors | Farshad G. Veshki, Sergiy A. Vorobyov |
| Abstract | We address the multi-focus image fusion problem, where multiple images captured with different focal settings are to be fused into an all-in-focus image of higher quality. Algorithms for this problem necessarily admit the source image characteristics along with focused and blurred features. However, most sparsity-based approaches use a single dictionary in focused feature space to describe multi-focus images, and ignore the representations in blurred feature space. We propose a multi-focus image fusion approach based on sparse representation using a coupled dictionary. It exploits the observations that the patches from a given training set can be sparsely represented by a couple of overcomplete dictionaries related to the focused and blurred categories of images and that a sparse approximation based on such coupled dictionary leads to a more flexible and therefore better fusion strategy than the one based on just selecting the sparsest representation in the original image estimate. In addition, to improve the fusion performance, we employ a coupled dictionary learning approach that enforces pairwise correlation between atoms of dictionaries learned to represent the focused and blurred feature spaces. We also discuss the advantages of the fusion approach based on coupled dictionary learning, and present efficient algorithms for fusion based on coupled dictionary learning. Extensive experimental comparisons with state-of-the-art multi-focus image fusion algorithms validate the effectiveness of the proposed approach. |
| Tasks | Dictionary Learning |
| Published | 2017-05-30 |
| URL | https://arxiv.org/abs/1705.10574v3 |
| https://arxiv.org/pdf/1705.10574v3.pdf | |
| PWC | https://paperswithcode.com/paper/multi-focus-image-fusion-via-coupled-sparse |
| Repo | |
| Framework | |
Time Matters: Multi-scale Temporalization of Social Media Popularity
| Title | Time Matters: Multi-scale Temporalization of Social Media Popularity |
| Authors | Bo Wu, Wen-Huang Cheng, Yongdong Zhang, Tao Mei |
| Abstract | The evolution of social media popularity exhibits rich temporality, i.e., popularities change over time at various levels of temporal granularity. This is influenced by temporal variations of public attentions or user activities. For example, popularity patterns of street snap on Flickr are observed to depict distinctive fashion styles at specific time scales, such as season-based periodic fluctuations for Trench Coat or one-off peak in days for Evening Dress. However, this fact is often overlooked by existing research of popularity modeling. We present the first study to incorporate multiple time-scale dynamics into predicting online popularity. We propose a novel computational framework in the paper, named Multi-scale Temporalization, for estimating popularity based on multi-scale decomposition and structural reconstruction in a tensor space of user, post, and time by joint low-rank constraints. By considering the noise caused by context inconsistency, we design a data rearrangement step based on context aggregation as preprocessing to enhance contextual relevance of neighboring data in the tensor space. As a result, our approach can leverage multiple levels of temporal characteristics and reduce the noise of data decomposition to improve modeling effectiveness. We evaluate our approach on two large-scale Flickr image datasets with over 1.8 million photos in total, for the task of popularity prediction. The results show that our approach significantly outperforms state-of-the-art popularity prediction techniques, with a relative improvement of 10.9%-47.5% in terms of prediction accuracy. |
| Tasks | |
| Published | 2017-12-12 |
| URL | http://arxiv.org/abs/1801.05853v1 |
| http://arxiv.org/pdf/1801.05853v1.pdf | |
| PWC | https://paperswithcode.com/paper/time-matters-multi-scale-temporalization-of |
| Repo | |
| Framework | |
Gaussian process regression for forecasting battery state of health
| Title | Gaussian process regression for forecasting battery state of health |
| Authors | Robert R. Richardson, Michael A. Osborne, David A. Howey |
| Abstract | Accurately predicting the future capacity and remaining useful life of batteries is necessary to ensure reliable system operation and to minimise maintenance costs. The complex nature of battery degradation has meant that mechanistic modelling of capacity fade has thus far remained intractable; however, with the advent of cloud-connected devices, data from cells in various applications is becoming increasingly available, and the feasibility of data-driven methods for battery prognostics is increasing. Here we propose Gaussian process (GP) regression for forecasting battery state of health, and highlight various advantages of GPs over other data-driven and mechanistic approaches. GPs are a type of Bayesian non-parametric method, and hence can model complex systems whilst handling uncertainty in a principled manner. Prior information can be exploited by GPs in a variety of ways: explicit mean functions can be used if the functional form of the underlying degradation model is available, and multiple-output GPs can effectively exploit correlations between data from different cells. We demonstrate the predictive capability of GPs for short-term and long-term (remaining useful life) forecasting on a selection of capacity vs. cycle datasets from lithium-ion cells. |
| Tasks | |
| Published | 2017-03-16 |
| URL | http://arxiv.org/abs/1703.05687v2 |
| http://arxiv.org/pdf/1703.05687v2.pdf | |
| PWC | https://paperswithcode.com/paper/gaussian-process-regression-for-forecasting |
| Repo | |
| Framework | |
