more_vert

Google TechTalks check_circle

787 views 4 days ago

00:12:43

How I Wrote 10K Lines of Go in a Weekend

more_vert

Google TechTalks check_circle

2K views 3 months ago

00:56:58

Privacy Preserving ML with Fully Homomorphic Encryption

more_vert

Google TechTalks check_circle

1 views 5 months ago

00:52:19

KAN: Kolmogorov-Arnold Networks

more_vert

Google TechTalks check_circle

1 views 5 months ago

,A Google Algorithms Seminar TechTalk, presented by Ziming Liu, 2024-06-04 ABSTRACT: Inspired by the Kolmogorov-Arnold representation theorem, we propose Kolmogorov-Arnold Networks (KANs) as promising alternatives to Multi-Layer Perceptrons (MLPs). While MLPs have fixed activation functions on nodes ("neurons"), KANs have learnable activation functions on edges ("weights"). KANs have no linear weights at all -- every weight parameter is replaced by a univariate function parametrized as a spline. We show that this seemingly simple change makes KANs outperform MLPs in terms of accuracy and interpretability. For accuracy, much smaller KANs can achieve comparable or better accuracy than much larger MLPs in data fitting and PDE solving. Theoretically and empirically, KANs possess faster neural scaling laws than MLPs. For interpretability, KANs can be intuitively visualized and can easily interact with human users. Through two examples in mathematics and physics, KANs are shown to be useful collaborators helping scientists (re)discover mathematical and physical laws. In summary, KANs are promising alternatives for MLPs, opening opportunities for further improving today's deep learning models which rely heavily on MLPs. ABOUT THE SPEAKER: Ziming Liu is a fourth-year PhD student at MIT & IAIFI, advised by Prof. Max Tegmark. His research interests lie in the intersection of AI and physics (science in general): Physics of AI: “AI as simple as physics” Physics for AI: “AI as natural as physics” AI for physics: “AI as powerful as physicists” He publishes papers both in top physics journals and AI conferences. He serves as a reviewer for Physcial Reviews, NeurIPS, ICLR, IEEE, etc. He co-organized the AI4Science workshops. His research have strong interdisciplinary nature, e.g., Kolmogorov-Arnold networks (Math for AI), Poisson Flow Generative Models (Physics for AI), Brain-inspired modular training (Neuroscience for AI), understanding Grokking (physics of AI), conservation laws and symmetries (AI for physics).

00:59:46

Understanding Oversmoothing in Graph Neural Networks (GNNs): Insights from Two Theoretical Studies

more_vert

Google TechTalks check_circle

1 views 10 months ago

,A Google TechTalk, presented by Xinyi Wu, 2024-01-18 A Google Algorithm Seminar. ABSTRACT: Oversmoothing in Graph Neural Networks (GNNs) refers to the phenomenon where increasing network depth leads to homogeneous node representations. Over the last few years, it has remained as one of the central challenges of building more powerful Graph Neural Networks (GNNs). In this talk, I will discuss two recent papers on this phenomenon and provide some new insights. The first work studies why oversmoothing happens at a relatively shallow depth in GNNs. By carefully analyzing the oversmoothing mechanisms in a stylized formulation, we distinguish between adverse mixing that homogenizes nodes across different classes and beneficial denoising within the same class. We quantify these two effects on random graphs sampled from the Contextual Stochastic Block Model (CSBM) and show that oversmoothing occurs once the mixing effect starts to dominate the denoising effect. We establish that the number of layers required for this transition is O(logN/log(logN)) for sufficiently dense graphs with N nodes. We also extend our analysis to study the effects of Personalized PageRank (PPR), or equivalently, the effects of initial residual connections on oversmoothing, and shed light on when and why they might not be an ideal solution to the problem. In the second work, we study oversmoothing in attention-based GNNs, such as Graph Attention Networks (GATs) and transformers. Treating attention-based GNNs as dynamical systems, our study demonstrates that the graph attention mechanism cannot prevent oversmoothing and loses expressive power exponentially. From a technical point of view, the proposed framework significantly extends the existing results on oversmoothing, and can account for asymmetric, state-dependent and time-varying aggregation operators and a wide range of common nonlinear activation functions, such as ReLU, LeakyReLU, GELU and SiLU. The talk is based on the following papers: https://arxiv.org/abs/2212.10701, https://arxiv.org/abs/2305.16102. Joint works with Amir Ajorlou (MIT), Zhengdao Chen (NYU/Google), William Wang (MIT), Zihui Wu (Caltech) and Ali Jadbabaie (MIT). ABOUT THE SPEAKER: Xinyi Wu is a fourth-year Ph.D. student in the Institute for Data, Systems, and Society (IDSS) at Massachusetts Institute of Technology (MIT), advised by Professor Ali Jadbabaie. She is affiliated with the Laboratory for Information and Decision Systems (LIDS). She is a recipient of the MIT Michael Hammer Fellowship. She is interested in applied graph theory, dynamical systems, networks, and machine learning on graphs. Her work on oversmoothing in GNNs has been awarded as Spotlight paper in NeurIPS 2023.

01:02:12

Socially Responsible Software Development (Teaching Software Design Systematically)

more_vert

Google TechTalks check_circle

1 views 11 months ago

00:57:03

Understanding and Mitigating Copying in Diffusion Models

more_vert

Google TechTalks check_circle

1 views 11 months ago

00:49:05

High-Dimensional Prediction for Sequential Decision Making

more_vert

Google TechTalks check_circle

1 views 11 months ago

,A Google TechTalk, presented by Georgy Noarov, 2023-11-16 Google Algorithms Seminar - ABSTRACT: In predictions-to-decisions pipelines, statistical forecasts are useful insofar as they are a trustworthy guide to downstream rational decision making. Towards this, we study the problem of making online predictions of an adversarially chosen high-dimensional state that are emph{unbiased} subject to an arbitrary collection of conditioning events, with the goal of tailoring these events to downstream decision makers who will use these predictions to inform their actions. We give efficient general algorithms for solving this problem, and a number of applications that stem from choosing an appropriate set of conditioning events, including: (1) tractable algorithms with strong no-regret guarantees over large action spaces, (2) a high-dimensional best-in-class (omniprediction) result, (3) fairness guarantees of various flavors, and (4) a novel framework for uncertainty quantification in multiclass settings. For example, we can efficiently produce predictions targeted at any polynomially many decision makers, offering each of them optimal swap regret if they simply best respond to our predictions. Generalizing this, in the online combinatorial optimization setting we obtain the first efficient algorithms that guarantee, for up to polynomially many decision makers, no regret on any polynomial number of {subsequences} that can depend on their actions as well as any external context. As an illustration, for the online routing problem this easily implies --- for the first time --- efficiently obtainable no-swap-regret guarantees over all exponentially many paths that make up an agent's action space (and this can be obtained for multiple agents at once); by contrast, prior no swap regret algorithms such as Blum-Mansour would be intractable in this setting as they need to enumerate over the exponentially large action space. Moreover, our results imply novel regret guarantees for extensive-form games. Turning to uncertainty quantification in ML, we show how our methods let us estimate (in the online adversarial setting) multiclass/multilabel probability vectors in a transparent and trustworthy fashion: in particular, downstream prediction set algorithms (i.e., models that predict multiple labels at once rather than a single one) will be incentivized to simply use our estimated probabilities as if they were the true conditional class probabilities, and their predictions will be guaranteed to satisfy multigroup fairness and other "conditional coverage" guarantees. This gives a powerful new alternative to well-known set-valued prediction paradigms such as conformal and top-K prediction. Moreover, our predictions can be guaranteed to be "best-in-class" --- i.e. to beat any polynomial collection of other (e.g. NN-based) multiclass vector predictors, simultaneously as measured by all Lipschitz Bregman loss functions (including L2 loss, cross-entropy loss, etc.). This can be interpreted as a high-dimensional omniprediction result. ABOUT THE SPEAKER: George Noarov is a CS PhD student at the University of Pennsylvania, advised by Michael Kearns and Aaron Roth. He is broadly interested in theoretical CS and ML, with particular focus on fair/robust/trustworthy ML, online learning, algorithmic game theory, and uncertainty quantification. He obtained his B.A. in Mathematics from Princeton University, where his advisors were Mark Braverman and Matt Weinberg. He has received several academic awards, and his research has been supported by an Amazon Gift for Research in Trustworthy AI.

00:58:01

Representational Strengths and Limitations of Transformers

more_vert

Google TechTalks check_circle

1 views 1 year ago

00:50:09

Revisiting Nearest Neighbors from a Sparse Signal Approximation View

more_vert

Google TechTalks check_circle

1 views 1 year ago

,A Google TechTalk, presented by Sarath Shekkizhar, 2023-07-10 Google Algorithms Seminar ABSTRACT: Neighborhood and graph construction is fundamental in data analysis and machine learning. k-nearest neighbor (kNN) and epsilon-neighborhood methods are the most commonly used methods for this purpose due to their computational simplicity. However, the interpretation and the choice of parameter k/epsilon, though receiving much attention over the years, still remains ad hoc. In this talk, I will present an alternative view of neighborhoods where I demonstrate that neighborhood definitions are sparse signal approximation problems. Specifically, we will see that (1) kNN and epsilon-neighborhood approaches are sub-optimal thresholding-based representations; (2) an improved and efficient definition based on basis pursuits exists, namely, non-negative kernel regression (NNK); and (3) selecting orthogonal signals for sparse approximation corresponds to the selection of neighbors that are not geometrically redundant. NNK neighborhoods are adaptive, sparse, and exhibit superior performance in graph-based signal processing and machine learning. We will then discuss a k-means like algorithm where we leverage the polytope geometry and sparse coding view of NNK for data summarization and outlier detection. I will conclude by discussing a graph framework for an empirical understanding of deep neural networks (DNN). The developed graph metrics characterize the input-output geometry of the embedding spaces induced in DNN and provide insights into the similarities and differences between models, their invariances, and their generalization and transfer learning performances. Bio: Sarath Shekkizhar received his bachelor's (Electronics and Communication) and double master's (Electrical Engineering, Computer Science) degrees from the National Institute of Technology, Tiruchirappalli, India, and the University of Southern California (USC), Los Angeles, USA, respectively. He recently graduated from Antonio Ortega's group with his doctoral degree in Electrical and Computer Engineering at USC. He is the recipient of the IEEE best student paper award at ICIP 2020 and was named a Rising Star in Signal Processing at ICASSP 2023. His research interests include graph signal processing, non-parametric methods, and machine learning.

00:17:16

2023 Blockly Developer Summit Day 2-5: Plug-ins Demonstration

more_vert

Google TechTalks check_circle

1 views 1 year ago

00:55:27

Open Problems in Mechanistic Interpretability: A Whirlwind Tour

more_vert

Google TechTalks check_circle

1 views 1 year ago

00:50:17

Differentially Private Online to Batch

more_vert

Google TechTalks check_circle

1 views 1 year ago

00:53:11

Improved Feature Importance Computation for Tree Models Based on the Banzhaf Value

more_vert

Google TechTalks check_circle

1 views 1 year ago

,A Google TechTalk, presented by Piotr Sankowski, 2023-03-30 ABSTRACT: The Shapley value -- a fundamental game-theoretic solution concept -- has recently become one of the main tools used to explain predictions of tree ensemble models. Another well-known game-theoretic solution concept is the Banzhaf value. Although the Banzhaf value is closely related to the Shapley value, its properties w.r.t. feature attribution have not been understood equally well. This paper shows that, for tree ensemble models, the Banzhaf value offers some crucial advantages over the Shapley value while providing similar feature attributions. In particular, we first give an optimal O(TL+n) time algorithm for computing the Banzhaf value-based attribution of a tree ensemble model's output. Here, T is the number of trees, L is the maximum number of leaves in a tree, and n is the number of features. In comparison, the state-of-the-art Shapley value-based algorithm runs in O(TLD^2+n) time, where D denotes the maximum depth of a tree in the ensemble. Next, we experimentally compare the Banzhaf and Shapley values for tree ensemble models. Both methods deliver essentially the same average importance scores for the studied datasets using two different tree ensemble models (the sklearn implementation of Decision Trees or xgboost implementation of Gradient Boosting Decision Trees). However, our results indicate that, on top of being computable faster, the Banzhaf is more numerically robust than the Shapley value. Joint work with A. Karczmarz, A. Mukherjee, P. Wygocki and T. Michalak. About the Speaker: Piotr Sankowski is a professor at the Institute of Informatics, University of Warsaw, where he received his habilitation in 2009 and where he received a doctorate in computer science in 2005. His research interest focuses on practical application of algorithms, ranging from economic applications, through learning data structures, to parallel algorithms for data science. In 2009, Piotr Sankowski received also a doctorate in physics in the field of solid state theory at the Polish Academy of Sciences. In 2010 he received ERC Starting Independent Researcher Grant, in 2015 ERC Proof of Concept Grant, and in 2017 ERC Consolidator Grant. He is a president of IDEAS NCBR – a research and development centre operating in the field of artificial intelligence and digital economy. Piotr Sankowski is also a co-founder of the spin-off company MIM Solutions. A Google Talk Series on Algorithms, Theory, and Optimization