1,720,967 research outputs found
Recommended from our members
Feature engineering for supervised learning
Get PDFThe main objective of this study is to investigate the possibility of generating extremely effective features when dealing with multicluster, multidimensional datasets with low information features. We present the design and development of a general-purpose, interpretable, and rectifiable continual learning algorithm. We introduce Patch, an algorithm that identifies ideal binary features, termed “one-way classifiers”. A one-way classifier predicts the class accurately when the feature is active and remains non-specific when the feature is inactive. Patch finds these classifiers in a parallelizable manner, optimizing for reliability and preventing overfitting. This concept is extended to residuals through our PatchAugment algorithm, which improves the performance of any baseline model by focusing on poorly predicted data points. Our formalization of manufactured features as one-way classifiers distinguishes our work from traditional embedding-based feature construction methods. Unlike embeddings that require all components to work in unison, each feature created by Patch is independently informative for a subset of the data, making it highly interpretable and verifiable. The contributions of this thesis are twofold: first, we introduce a robust algorithm for automatic feature construction; second, we develop a novel continual learning approach that leverages these features to enhance model performance. Experiments on multiple real-world datasets demonstrate significant improvements in AUC, validating the efficacy of our methods. The structure of this thesis is as follows: Chapter 2 surveys related work. Chapter 3 formulates the feature construction problem and presents our model. Chapter 4 details our algorithms for feature construction and continual learning. Chapter 5 provides empirical validation, and Chapter 6 concludes the thesis.Mechanical Engineerin
Recommended from our members
Heterogeneous and dynamic network modeling and statistical inference with provable guarantees
No full textNetworks, or graphs, are fundamental objects used to model a huge range of phenomena such as social interactions, biological processes, and the global economy. Due to this broad applicability, both the development of network models and statistical inference problems related to networks are major areas of research. In this thesis, we propose new models of networks both capture real-world phenomena and enable learning algorithms with provable guarantees. First, we introduce new models of distributional shifts for network models, and give transfer learning methods to estimate a target network with limited and noisy data. For latent variable networks (Chapter 2), which generalize common network models such as Stochastic Block Models and Graphons, we give a transfer learning algorithm for combinatorial distributional shifts. In this setup, we observe an o(1) fraction of the target data for a graph Q, as well as side information in the form of a source graph P. We give an efficient algorithm to estimate Q that achieves vanishing error with high probability. Moreover, we give minimax lower bounds for the special case of Stochastic Block Models, and give an efficient algorithm to achieve the minimax rate in this setting. Furthermore, we validate our results on real-world transfer learning problems in cell biology and dynamic social networks. Next, we study transfer learning for matrix completion, which generalizes the problem of network estimation with missing data (Chapter 3). We consider low-rank source matrix P and target matrix Q which are related via a linear shift in their row and column singular subspaces, which is a commonly studied geometric model of distributional shift. The target matrix Q is noisily observed in a Missing Not-at-Random (MNAR) setting that is motivated by biological problems; entire rows and columns missing, making estimation impossible without side information. Unlike our work on latent variable models in Chapter 2, we consider both the active and passive sampling of rows and columns. We establish minimax lower bounds for entrywise estimation error in each setting. Further, we give a computationally efficient estimation framework to achieve the lower bound for the active setting, which leverages the source data to query the most informative rows and columns of Q. This avoids the need for incoherence assumptions required for rate optimality in the passive sampling setting. We demonstrate the effectiveness of our approach through comparisons with existing algorithms on real-world biological datasets. Second, we study various network models for heterogeneous and dynamic real-world settings in economics and sociology. We first propose a network model of bilateral contracts between heterogeneous, mean-variance optimizing agents (Chapter 4). Our model applies to several important classes of economic networks, such as the multi-trillion dollar market of derivatives contracts between large financial institutions. We give an efficient algorithm for honest agents to find a stable network from iterative pairwise negotiations, and prove that it converges to a strong (coalitional) Nash equilibrium. This algorithm is decentralized, and only requires that agents communicate with their neighbors in order to myopically update their preferred contract sizes based on their own utility functions. Moreover, we give a learning algorithm that recovers network parameters from time-series data using Semidefinite Programming. Further, we empirically demonstrate how an external observer can learn the source of a network shock based on observing the equilibrium before and after the shock. We verify our findings with experiments on real-world international trade networks, and networks constructed from real-world portfolio data. Next, we study a model of strategic negotiations in which agents can manipulate the pairwise negotiation algorithm of Chapter 4 by misrepresenting their true preferences (Chapter 5). By negotiating strategically, agents can obtain better contracts. Unlike prior works on strategic behavior in network games, which consider honest behavior or a single strategic agent, we allow any subset of agents to be strategic. We provide an efficient algorithm for finding the set of Nash equilibria of the game played by the strategic agents, if any exist, and certify their nonexistence otherwise. We also show that when several strategic agents are present, their utilities can increase or decrease compared to when they are all honest. Small changes in the inter-agent correlations can cause such shifts. Finally, we develop an algorithm by which new agents can learn the information needed for strategic behavior. Our algorithm works even when the (unknown) strategic agents deviate from the Nash-optimal strategies. We verify these results on both simulated networks and a real-world dataset on international trade. Finally, we introduce a model of opinion formation in social networks where strategic agents can manipulate publicly expressed opinions to further their own narratives (Chapter 6). This captures real-world manipulation of social networks, such as during the 2016 US elections and the 2019 Hong Kong protests. As in Chapter 5, we go beyond prior works by considering multiple strategic actors, who can have conflicting goals. Unlike Chapter 5, our focus is not on the formation of a network of contracts, but rather on the equilibrium opinions expressed in an exogenous social network, such as Twitter. We characterize the Nash Equilibrium of the resulting meta-game played by the strategic actors. Experiments on real-world social network datasets from Twitter, Reddit, and Political Blogs show that strategic agents can significantly increase polarization and disagreement, as well as increase the “cost” of the equilibrium. To this end, we give worst-case upper bounds on the Price of Misreporting (analogous to the Price of Anarchy). Finally, we give efficient learning algorithms for the platform to (i) detect whether strategic manipulation has occurred, and (ii) learn who the strategic actors are. Our algorithms are accurate on the same real-world datasets, suggesting how platforms can take steps to mitigate the effects of strategic behavior.Computer Scienc
Going Beyond Counting First Authors in Author Co-citation Analysis
Get PDFThe present study examines one of the fundamental aspects of author co-citation analysis (ACA) - the way co-citation
counts are defined. Co-citation counting provides the data on which all subsequent statistical analyses and mappings
are based, and we compare ACA results based on two different types of co-citation counting - the traditional type that
only counts the first one among a cited work's authors on the one hand and a non-traditional type that takes into
account the first 5 authors of a cited work on the other hand. Results indicate that the picture produced through this non-traditional author co-citation counting contains more coherent author groups and is therefore considerably clearer. However, this picture represents fewer specialties in the research field being studied than that produced through the traditional first-author co-citation counting when the same number of top-ranked authors is selected and analyzed. Reasons for these effects are discussed
Recommended from our members
Network inference with statistical guarantees
Get PDFNetworks arise in a huge variety of real data scenarios: starting from social networks like Facebook or user product networks in recommendation systems to protein-protein interaction networks in biological systems, etc. In this thesis, we focus on developing fast and provable algorithms for some network inference problems.
In the first part, we are interested in overlapping community detection problem under the popular Mixed Membership Stochastic Blockmodel (MMSB). We firstly establish sufficient conditions for the symmetric non-negative matrix factorization optimization to have a unique solution under MMSB, and propose a computationally efficient algorithm called GeoNMF that is provably optimal and hence consistent for a broad parameter regime. Then using the inherent geometry of MMSB, we link the inference of overlapping communities to the problem of finding corners in a noisy rotated and scaled simplex, for which consistent algorithms exist. We use this as a building block for our algorithm to infer the community memberships of each node, and provide uniform rates of convergence for the inferred community membership vector of each node in the network. As a byproduct of our analysis, we derive sharp row-wise eigenvector deviation bounds, and provide a cleaning step that improves the performance drastically for sparse networks. 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.
For the second part, we go beyond MMSB for overlapping community detection. Notice that many existing overlapping clustering methods model each person (or word, or book) as a non-negative weighted combination of "exemplars" who belong solely to one community, with some small noise. Geometrically, each person is a point on a cone whose corners are these exemplars. This basic form encompasses the widely used MMSB of networks and its degree corrected variants, as well as topic models such as LDA. We show that a simple one-class SVM yields provably consistent parameter inference for all such models, and scales to large datasets. Experimental results on several simulated and real datasets show our algorithm (called SVM-cone) is both accurate and scalable.
The final contribution of this thesis is novel nonparametric methods for network covariate estimation. Networks with node covariates are commonplace: for example, people in a social network have interests, or product preferences, etc. If we know the covariates for some nodes, can we infer them for the remaining nodes? We provide two provably consistent methods to solve this problem. For "low-rank" latent variable models, we develop SVD-RBF, which uses the top principal components of the network in a non-parametric regression. For general models, we present CN-VEC, which constructs a similarity measure between two nodes, based on the patterns of their 2-hop neighborhoods. CN-VEC then predicts node covariates by averaging the covariates of the top-k most similar nodes using this measure. SVD-RBF is consistent for low-rank models when the average degree grows with Õ(log n), while CN-VEC is consistent for a wide range of models when the degree grows with Õ(n¹ [superscript /] ³). To our knowledge, CN-VEC is the first provably consistent method for this problem under general models. Both methods are fast, and CN-VEC is also parameter-free. Experiments on 4 simulated network models and 3 real-world datasets show the effectiveness of our algorithms compared to the state of the art.Computer Scienc
Recommended from our members
Distributed and dynamic factor modeling of online data
Get PDFThe domain of data mining and machine learning has expanded rapidly in recent years to include both large-scale distributed and streaming computation. Although many open-source and cloud-based frameworks are available for these tasks, many of which are used in-production by industry, this is a rapidly-evolving technology landscape, and the gap between the academic role of algorithm development and discovery and code available for use with real-world data has grown. In addition, although there is a rich history of mathematical models for streaming data on continuous vector spaces, there has been significantly less work on streaming discrete spaces. However, much if not most of the data available online is composed of high-dimensional sparse counts, such as text corpora and interaction networks.
We attempt to help bridge this gap by extending promising Bayesian Poisson factorization and co-factorization models that can be used, for example, to model not only text corpora but also related user interactions in a social network. We construct a dependent process prior that enables dynamic latent factor modeling in the natural probability space of the factors, rather than in the raw data. These models are then scaled to and implemented for distributed compute systems and streaming data.
We develop an adaptive hashing method (AdaHash) for lambda architectures that can use latent factors calculated during periodic batch mode updates as a similarity metric for hierarchical grouping, or for finding similar factors to reconcile parameters in a distributed compute scenario. In addition, we develop a novel Hidden Markov variant using particle filters to update prior factors and probabilistically group with new factors in a dynamic inference model (D-GaPS).
We show experimentally that the distributed model converges to similar factors as single-process inference, and the dynamic model yields superior quality topics over batch mode alternatives. Empirical studies are presented on the use of a U.S. Senate voting and bill summary data set that is readily interpretable with regard to latent factors.Electrical and Computer Engineerin
Recommended from our members
A multi-scale framework for graph based machine learning problems
Get PDFGraph data have become essential in representing and modeling relationships between entities and complex network structures in various domains such as social networks and recommender systems. As a main contributor of the recent Big Data trend, the massive scale of graphs in modern machine learning problems easily overwhelms existing methods and thus sophisticated scalable algorithms are needed for real-world applications. In this thesis, we develop a novel multi-scale framework based on the divide-and-conquer principle as an effective and scalable approach for machine learning tasks involving large sparse graphs. We first demonstrate how our multi-scale framework can be applied to the problem of computing the spectral decomposition of massive graphs, which is one of the most fundamental low-rank matrix approximations used in numerous machine learning tasks. While popular solvers suffer from slow convergence, especially when the desired rank is large, our method exploits the clustering structure of the graph and achieves superior performance compared to existing algorithms in terms of both accuracy and scalability. While the main goal of the divide-and-conquer approach is to efficiently compute solutions for the original problem, the proposed multi-scale framework further admits an attractive but less obvious feature that machine learning problems can benefit from. Particularly, we consider partial solutions of the subproblems computed in the process as localized models of the entire problem. By doing so, we can combine models at multiple scales from local to global and generate a holistic view of the underlying problem to achieve better performance than a single global view. We adapt such multi-scale view for the problems of link prediction in social networks and collaborative filtering in recommender systems with additional side information to obtain a model that can make accurate and robust predictions in a scalable manner.Computer Scienc
Recommended from our members
Essays on data-driven optimization
Get PDFThe estimation of a data matrix contains two parts: the well estimated and the poorly estimated. The latter is usually throwing away because the estimations are off. As argued in this paper, ignoring is the wrong thing to do as the poorly estimated part is orthogonal to the well estimated. I will show how to use such orthogonality information via robust optimization and provide application in portfolio optimization, least-square regression, and dimension reduction. Across a large number of experiments, utilizing the orthogonality information consistently improves the performance.Information, Risk, and Operations Management (IROM
Variations on the Author
Get PDF“Variations on the Author” discusses two of Eduardo Coutinho’s recent films (Um Dia na Vida, from 2010, and Últimas Conversas, posthumously released in 2015) and their contribution to the general question of documentary authorship. The director’s filmography is characterized by a consistent yet self-effacing form of authorial self-inscription: Coutinho often features as an interviewer that rather than express opinions propels discourses; an interviewer that is good at listening. This mode of self-inscription characterizes him as an author who is not expressive but who is nonetheless markedly present on the screen. In Um Dia na Vida, however, Coutinho is completely absent form the image, while Últimas Conversas, on the contrary, includes a confessional prologue that moves the director from the margins to the center of his films. This article examines the ways in which these works stand out in the filmography of a director who offers new insights into the notion of cinematic authorship
Appropriate Similarity Measures for Author Cocitation Analysis
Get PDFWe provide a number of new insights into the methodological discussion about author cocitation analysis. We first argue that the use of the Pearson correlation for measuring the similarity between authors’ cocitation profiles is not very satisfactory. We then discuss what kind of similarity measures may be used as an alternative to the Pearson correlation. We consider three similarity measures in particular. One is the well-known cosine. The other two similarity measures have not been used before in the bibliometric literature. Finally, we show by means of an example that our findings have a high practical relevance.information science;Pearson correlation;cosine;similarity measure;author cocitation analysis
- …
