LIVIVO - Search results -

Search results

Result 1 - 10 of total 20

Search options

Book ; Online: Local Borsuk-Ulam, Stability, and Replicability

Chase, Zachary / Chornomaz, Bogdan / Moran, Shay / Yehudayoff, Amir

2023

Abstract: We use and adapt the Borsuk-Ulam Theorem from topology to derive limitations on list-replicable and globally stable learning algorithms. We further demonstrate the applicability of our methods in combinatorics and topology. We show that, besides trivial ... ...

Abstract	We use and adapt the Borsuk-Ulam Theorem from topology to derive limitations on list-replicable and globally stable learning algorithms. We further demonstrate the applicability of our methods in combinatorics and topology. We show that, besides trivial cases, both list-replicable and globally stable learning are impossible in the agnostic PAC setting. This is in contrast with the realizable case where it is known that any class with a finite Littlestone dimension can be learned by such algorithms. In the realizable PAC setting, we sharpen previous impossibility results and broaden their scope. Specifically, we establish optimal bounds for list replicability and global stability numbers in finite classes. This provides an exponential improvement over previous works and implies an exponential separation from the Littlestone dimension. We further introduce lower bounds for weak learners, i.e., learners that are only marginally better than random guessing. Lower bounds from previous works apply only to stronger learners. To offer a broader and more comprehensive view of our topological approach, we prove a local variant of the Borsuk-Ulam theorem in topology and a result in combinatorics concerning Kneser colorings. In combinatorics, we prove that if $c$ is a coloring of all non-empty subsets of $[n]$ such that disjoint sets have different colors, then there is a chain of subsets that receives at least $1+ \lfloor n/2\rfloor$ colors (this bound is sharp). In topology, we prove e.g. that for any open antipodal-free cover of the $d$-dimensional sphere, there is a point $x$ that belongs to at least $t=\lceil\frac{d+3}{2}\rceil$ sets.
Keywords	Computer Science - Machine Learning ; Computer Science - Data Structures and Algorithms ; I.2.6
Subject code	514
Publishing date	2023-11-02
Publishing country	us
Document type	Book ; Online
Database	BASE - Bielefeld Academic Search Engine (life sciences selection)

Full text online

Full text

Inter-library loan at ZB MED

Your chosen title can be delivered directly to ZB MED Cologne location if you are registered as a user at ZB MED Cologne.

Book ; Online: The Sample Complexity Of ERMs In Stochastic Convex Optimization

Carmon, Daniel / Livni, Roi / Yehudayoff, Amir

2023

Abstract: Stochastic convex optimization is one of the most well-studied models for learning in modern machine learning. Nevertheless, a central fundamental question in this setup remained unresolved: "How many data points must be observed so that any empirical ... ...

Abstract	Stochastic convex optimization is one of the most well-studied models for learning in modern machine learning. Nevertheless, a central fundamental question in this setup remained unresolved: "How many data points must be observed so that any empirical risk minimizer (ERM) shows good performance on the true population?" This question was proposed by Feldman (2016), who proved that $\Omega(\frac{d}{\epsilon}+\frac{1}{\epsilon^2})$ data points are necessary (where $d$ is the dimension and $\epsilon>0$ is the accuracy parameter). Proving an $\omega(\frac{d}{\epsilon}+\frac{1}{\epsilon^2})$ lower bound was left as an open problem. In this work we show that in fact $\tilde{O}(\frac{d}{\epsilon}+\frac{1}{\epsilon^2})$ data points are also sufficient. This settles the question and yields a new separation between ERMs and uniform convergence. This sample complexity holds for the classical setup of learning bounded convex Lipschitz functions over the Euclidean unit ball. We further generalize the result and show that a similar upper bound holds for all symmetric convex bodies. The general bound is composed of two terms: (i) a term of the form $\tilde{O}(\frac{d}{\epsilon})$ with an inverse-linear dependence on the accuracy parameter, and (ii) a term that depends on the statistical complexity of the class of $\textit{linear}$ functions (captured by the Rademacher complexity). The proof builds a mechanism for controlling the behavior of stochastic convex optimization problems.
Keywords	Computer Science - Machine Learning ; Statistics - Machine Learning
Subject code	519
Publishing date	2023-11-09
Publishing country	us
Document type	Book ; Online
Database	BASE - Bielefeld Academic Search Engine (life sciences selection)

Full text online

Full text

Inter-library loan at ZB MED

Your chosen title can be delivered directly to ZB MED Cologne location if you are registered as a user at ZB MED Cologne.

Book ; Online: A Unified Characterization of Private Learnability via Graph Theory

Alon, Noga / Moran, Shay / Schefler, Hilla / Yehudayoff, Amir

2023

Abstract: We provide a unified framework for characterizing pure and approximate differentially private (DP) learnabiliity. The framework uses the language of graph theory: for a concept class $\mathcal{H}$, we define the contradiction graph $G$ of $\mathcal{H}$. ... ...

Abstract	We provide a unified framework for characterizing pure and approximate differentially private (DP) learnabiliity. The framework uses the language of graph theory: for a concept class $\mathcal{H}$, we define the contradiction graph $G$ of $\mathcal{H}$. It vertices are realizable datasets, and two datasets $S,S'$ are connected by an edge if they contradict each other (i.e., there is a point $x$ that is labeled differently in $S$ and $S'$). Our main finding is that the combinatorial structure of $G$ is deeply related to learning $\mathcal{H}$ under DP. Learning $\mathcal{H}$ under pure DP is captured by the fractional clique number of $G$. Learning $\mathcal{H}$ under approximate DP is captured by the clique number of $G$. Consequently, we identify graph-theoretic dimensions that characterize DP learnability: the clique dimension and fractional clique dimension. Along the way, we reveal properties of the contradiction graph which may be of independent interest. We also suggest several open questions and directions for future research. Comment: v1.2, acknowledgements
Keywords	Computer Science - Machine Learning
Subject code	511
Publishing date	2023-04-08
Publishing country	us
Document type	Book ; Online
Database	BASE - Bielefeld Academic Search Engine (life sciences selection)

Full text online

Full text

Inter-library loan at ZB MED

Your chosen title can be delivered directly to ZB MED Cologne location if you are registered as a user at ZB MED Cologne.

Book ; Online: Replicability and stability in learning

Chase, Zachary / Moran, Shay / Yehudayoff, Amir

2023

Abstract: Replicability is essential in science as it allows us to validate and verify research findings. Impagliazzo, Lei, Pitassi and Sorrell (`22) recently initiated the study of replicability in machine learning. A learning algorithm is replicable if it ... ...

Abstract	Replicability is essential in science as it allows us to validate and verify research findings. Impagliazzo, Lei, Pitassi and Sorrell (`22) recently initiated the study of replicability in machine learning. A learning algorithm is replicable if it typically produces the same output when applied on two i.i.d. inputs using the same internal randomness. We study a variant of replicability that does not involve fixing the randomness. An algorithm satisfies this form of replicability if it typically produces the same output when applied on two i.i.d. inputs (without fixing the internal randomness). This variant is called global stability and was introduced by Bun, Livni and Moran ('20) in the context of differential privacy. Impagliazzo et al. showed how to boost any replicable algorithm so that it produces the same output with probability arbitrarily close to 1. In contrast, we demonstrate that for numerous learning tasks, global stability can only be accomplished weakly, where the same output is produced only with probability bounded away from 1. To overcome this limitation, we introduce the concept of list replicability, which is equivalent to global stability. Moreover, we prove that list replicability can be boosted so that it is achieved with probability arbitrarily close to 1. We also describe basic relations between standard learning-theoretic complexity measures and list replicable numbers. Our results, in addition, imply that besides trivial cases, replicable algorithms (in the sense of Impagliazzo et al.) must be randomized. The proof of the impossibility result is based on a topological fixed-point theorem. For every algorithm, we are able to locate a "hard input distribution" by applying the Poincar\'{e}-Miranda theorem in a related topological setting. The equivalence between global stability and list replicability is algorithmic. Comment: 17 pages
Keywords	Computer Science - Machine Learning ; Mathematics - Combinatorics ; Statistics - Machine Learning
Subject code	006
Publishing date	2023-04-07
Publishing country	us
Document type	Book ; Online
Database	BASE - Bielefeld Academic Search Engine (life sciences selection)

Full text online

Full text

Inter-library loan at ZB MED

Your chosen title can be delivered directly to ZB MED Cologne location if you are registered as a user at ZB MED Cologne.

Book ; Online: Slicing the hypercube is not easy

Yehuda, Gal / Yehudayoff, Amir

2021

Abstract: We prove that at least $\Omega(n^{0.51})$ hyperplanes are needed to slice all edges of the $n$-dimensional hypercube. We provide a couple of applications: lower bounds on the computational complexity of parity, and a lower bound on the cover number of ... ...

Abstract	We prove that at least $\Omega(n^{0.51})$ hyperplanes are needed to slice all edges of the $n$-dimensional hypercube. We provide a couple of applications: lower bounds on the computational complexity of parity, and a lower bound on the cover number of the hypercube by skew hyperplanes. Comment: 20 pages
Keywords	Mathematics - Combinatorics ; Computer Science - Artificial Intelligence ; Computer Science - Computational Complexity ; 05D05 ; 52C35 ; F.2 ; G.2.1
Publishing date	2021-02-10
Publishing country	us
Document type	Book ; Online
Database	BASE - Bielefeld Academic Search Engine (life sciences selection)

Full text online

Full text

Inter-library loan at ZB MED

Your chosen title can be delivered directly to ZB MED Cologne location if you are registered as a user at ZB MED Cologne.

Article: A pilot study for a non-invasive system for detection of malignancy in canine subcutaneous and cutaneous masses using machine learning.

Dank, Gillian / Buber, Tali / Polliack, Gabriel / Aviram, Gal / Rice, Anna / Yehudayoff, Amir / Kent, Michael S

Frontiers in veterinary science

2023 Volume 10, Page(s) 1109188

Abstract: Introduction: Early diagnosis of cancer enhances treatment planning and improves prognosis. Many masses presenting to veterinary clinics are difficult to diagnose without using invasive, time-consuming, and costly tests. Our objective was to perform a ... ...

Abstract	Introduction: Early diagnosis of cancer enhances treatment planning and improves prognosis. Many masses presenting to veterinary clinics are difficult to diagnose without using invasive, time-consuming, and costly tests. Our objective was to perform a preliminary proof-of-concept for the HT Vista device, a novel artificial intelligence-based thermal imaging system, developed and designed to differentiate benign from malignant, cutaneous and subcutaneous masses in dogs. Methods: Forty-five dogs with a total of 69 masses were recruited. Each mass was clipped and heated by the HT Vista device. The heat emitted by the mass and its adjacent healthy tissue was automatically recorded using a built-in thermal camera. The thermal data from both areas were subsequently analyzed using an Artificial Intelligence algorithm. Cytology and/or biopsy results were later compared to the results obtained from the HT Vista system and used to train the algorithm. Validation was done using a "Leave One Out" cross-validation to determine the algorithm's performance. Results: The accuracy, sensitivity, specificity, positive predictive value, and negative predictive value of the system were 90%, 93%, 88%, 83%, and 95%, respectively for all masses. Conclusion: We propose that this novel system, with further development, could be used to provide a decision-support tool enabling clinicians to differentiate between benign lesions and those requiring additional diagnostics. Our study also provides a proof-of-concept for ongoing prospective trials for cancer diagnosis using advanced thermodynamics and machine learning procedures in companion dogs.
Language	English
Publishing date	2023-01-26
Publishing country	Switzerland
Document type	Journal Article
ZDB-ID	2834243-4
ISSN	2297-1769
ISSN	2297-1769
DOI	10.3389/fvets.2023.1109188
Database	MEDical Literature Analysis and Retrieval System OnLINE

Order via subito

This service is chargeable due to the Delivery terms set by subito. Orders including an article and supplementary material will be classified as separate orders. In these cases, fees will be demanded for each order.

Article: Training and validation of a novel non-invasive imaging system for ruling out malignancy in canine subcutaneous and cutaneous masses using machine learning in 664 masses.

Dank, Gillian / Buber, Tali / Rice, Anna / Kraicer, Noa / Hanael, Erez / Shasha, Tamir / Aviram, Gal / Yehudayoff, Amir / Kent, Michael S

Frontiers in veterinary science

2023 Volume 10, Page(s) 1164438

Abstract: Objective: To train and validate the use of a novel artificial intelligence-based thermal imaging system as a screening tool to rule out malignancy in cutaneous and subcutaneous masses in dogs.: Animals: Training study: 147 client-owned dogs with 233 ...

Abstract	Objective: To train and validate the use of a novel artificial intelligence-based thermal imaging system as a screening tool to rule out malignancy in cutaneous and subcutaneous masses in dogs. Animals: Training study: 147 client-owned dogs with 233 masses. Validation Study: 299 client-owned dogs with 525 masses. Cytology was non-diagnostic in 94 masses, resulting in 431 masses from 248 dogs with diagnostic samples. Procedures: The prospective studies were conducted between June 2020 and July 2022. During the scan, each mass and its adjacent healthy tissue was heated by a high-power Light-Emitting Diode. The tissue temperature was recorded by the device and consequently analyzed using a supervised machine learning algorithm to determine whether the mass required further investigation. The first study was performed to collect data to train the algorithm. The second study validated the algorithm, as the real-time device predictions were compared to the cytology and/or biopsy results. Results: The results for the validation study were that the device correctly classified 45 out of 53 malignant masses and 253 out of 378 benign masses (sensitivity = 85% and specificity = 67%). The negative predictive value of the system (i.e., percent of benign masses identified as benign) was 97%. Clinical relevance: The results demonstrate that this novel system could be used as a decision-support tool at the point of care, enabling clinicians to differentiate between benign lesions and those requiring further diagnostics.
Language	English
Publishing date	2023-09-29
Publishing country	Switzerland
Document type	Journal Article
ZDB-ID	2834243-4
ISSN	2297-1769
ISSN	2297-1769
DOI	10.3389/fvets.2023.1164438
Database	MEDical Literature Analysis and Retrieval System OnLINE

Order via subito

Book ; Online: On Symmetry and Initialization for Neural Networks

Nachum, Ido / Yehudayoff, Amir

2019

Abstract: This work provides an additional step in the theoretical understanding of neural networks. We consider neural networks with one hidden layer and show that when learning symmetric functions, one can choose initial conditions so that standard SGD training ... ...

Abstract	This work provides an additional step in the theoretical understanding of neural networks. We consider neural networks with one hidden layer and show that when learning symmetric functions, one can choose initial conditions so that standard SGD training efficiently produces generalization guarantees. We empirically verify this and show that this does not hold when the initial conditions are chosen at random. The proof of convergence investigates the interaction between the two layers of the network. Our results highlight the importance of using symmetry in the design of neural networks.
Keywords	Computer Science - Machine Learning ; Statistics - Machine Learning
Publishing date	2019-07-01
Publishing country	us
Document type	Book ; Online
Database	BASE - Bielefeld Academic Search Engine (life sciences selection)

Full text online

Full text

Inter-library loan at ZB MED

Your chosen title can be delivered directly to ZB MED Cologne location if you are registered as a user at ZB MED Cologne.

Book ; Online: Regularization by Misclassification in ReLU Neural Networks

Cornacchia, Elisabetta / Hązła, Jan / Nachum, Ido / Yehudayoff, Amir

2021

Abstract: We study the implicit bias of ReLU neural networks trained by a variant of SGD where at each step, the label is changed with probability $p$ to a random label (label smoothing being a close variant of this procedure). Our experiments demonstrate that ... ...

Abstract	We study the implicit bias of ReLU neural networks trained by a variant of SGD where at each step, the label is changed with probability $p$ to a random label (label smoothing being a close variant of this procedure). Our experiments demonstrate that label noise propels the network to a sparse solution in the following sense: for a typical input, a small fraction of neurons are active, and the firing pattern of the hidden layers is sparser. In fact, for some instances, an appropriate amount of label noise does not only sparsify the network but further reduces the test error. We then turn to the theoretical analysis of such sparsification mechanisms, focusing on the extremal case of $p=1$. We show that in this case, the network withers as anticipated from experiments, but surprisingly, in different ways that depend on the learning rate and the presence of bias, with either weights vanishing or neurons ceasing to fire.
Keywords	Computer Science - Machine Learning ; Computer Science - Neural and Evolutionary Computing
Subject code	006
Publishing date	2021-11-03
Publishing country	us
Document type	Book ; Online
Database	BASE - Bielefeld Academic Search Engine (life sciences selection)

Full text online

Full text

Inter-library loan at ZB MED

Your chosen title can be delivered directly to ZB MED Cologne location if you are registered as a user at ZB MED Cologne.

Book ; Online: A Characterization of Multiclass Learnability

Brukhim, Nataly / Carmon, Daniel / Dinur, Irit / Moran, Shay / Yehudayoff, Amir

2022

Abstract: A seminal result in learning theory characterizes the PAC learnability of binary classes through the Vapnik-Chervonenkis dimension. Extending this characterization to the general multiclass setting has been open since the pioneering works on multiclass ... ...

Abstract	A seminal result in learning theory characterizes the PAC learnability of binary classes through the Vapnik-Chervonenkis dimension. Extending this characterization to the general multiclass setting has been open since the pioneering works on multiclass PAC learning in the late 1980s. This work resolves this problem: we characterize multiclass PAC learnability through the DS dimension, a combinatorial dimension defined by Daniely and Shalev-Shwartz (2014). The classical characterization of the binary case boils down to empirical risk minimization. In contrast, our characterization of the multiclass case involves a variety of algorithmic ideas; these include a natural setting we call list PAC learning. In the list learning setting, instead of predicting a single outcome for a given unseen input, the goal is to provide a short menu of predictions. Our second main result concerns the Natarajan dimension, which has been a central candidate for characterizing multiclass learnability. This dimension was introduced by Natarajan (1988) as a barrier for PAC learning. Whether the Natarajan dimension characterizes PAC learnability in general has been posed as an open question in several papers since. This work provides a negative answer: we construct a non-learnable class with Natarajan dimension one. For the construction, we identify a fundamental connection between concept classes and topology (i.e., colorful simplicial complexes). We crucially rely on a deep and involved construction of hyperbolic pseudo-manifolds by Januszkiewicz and Swiatkowski. It is interesting that hyperbolicity is directly related to learning problems that are difficult to solve although no obvious barriers exist. This is another demonstration of the fruitful links machine learning has with different areas in mathematics. Comment: 35 pages, 5 figures
Keywords	Computer Science - Machine Learning ; Mathematics - Statistics Theory ; 68T99 ; 68R05 ; 62-08 ; I.2.6 ; G.2.1
Subject code	006
Publishing date	2022-03-03
Publishing country	us
Document type	Book ; Online
Database	BASE - Bielefeld Academic Search Engine (life sciences selection)

Full text online

Full text

Inter-library loan at ZB MED

Your chosen title can be delivered directly to ZB MED Cologne location if you are registered as a user at ZB MED Cologne.

To top

Full text online

More links

Kategorien

Inter-library loan at ZB MED

Full text online

More links

Kategorien

Inter-library loan at ZB MED

Full text online

More links

Kategorien

Inter-library loan at ZB MED

Full text online

More links

Kategorien

Inter-library loan at ZB MED

Full text online

More links

Kategorien

Inter-library loan at ZB MED

More links

Kategorien

Order via subito

More links

Kategorien

Order via subito

Full text online

More links

Kategorien

Inter-library loan at ZB MED

Full text online

More links

Kategorien

Inter-library loan at ZB MED

Full text online

More links

Kategorien

Inter-library loan at ZB MED