Zobrazeno 1 - 10
of 159
pro vyhledávání: '"BRESSAN, MARCO"'
Autor:
Bressan, Marco, Brukhim, Nataly, Cesa-Bianchi, Nicolò, Esposito, Emmanuel, Mansour, Yishay, Moran, Shay, Thiessen, Maximilian
Cost-sensitive loss functions are crucial in many real-world prediction problems, where different types of errors are penalized differently; for example, in medical diagnosis, a false negative prediction can lead to worse consequences than a false po
Externí odkaz:
http://arxiv.org/abs/2412.08012
Autor:
Bressan, Marco, Cesa-Bianchi, Nicolò, Esposito, Emmanuel, Mansour, Yishay, Moran, Shay, Thiessen, Maximilian
Can a deep neural network be approximated by a small decision tree based on simple features? This question and its variants are behind the growing demand for machine learning models that are *interpretable* by humans. In this work we study such quest
Externí odkaz:
http://arxiv.org/abs/2406.10529
We study the problem of learning a binary classifier on the vertices of a graph. In particular, we consider classifiers given by monophonic halfspaces, partitions of the vertices that are convex in a certain abstract sense. Monophonic halfspaces, and
Externí odkaz:
http://arxiv.org/abs/2405.00853
Autor:
Bressan, Marco, Sozio, Mauro
We give the first algorithm that maintains an approximate decision tree over an arbitrary sequence of insertions and deletions of labeled examples, with strong guarantees on the worst-case running time per update request. For instance, we show how to
Externí odkaz:
http://arxiv.org/abs/2302.03994
We develop the first fully dynamic algorithm that maintains a decision tree over an arbitrary sequence of insertions and deletions of labeled examples. Given $\epsilon > 0$ our algorithm guarantees that, at every point in time, every node of the deci
Externí odkaz:
http://arxiv.org/abs/2212.00778
We study the fixed-parameter tractability of the following fundamental problem: given two directed graphs $\vec H$ and $\vec G$, count the number of copies of $\vec H$ in $\vec G$. The standard setting, where the tractability is well understood, uses
Externí odkaz:
http://arxiv.org/abs/2211.01905
Autor:
Bressan, Marco, Cesa-Bianchi, Nicolò, Lattanzi, Silvio, Paudice, Andrea, Thiessen, Maximilian
We study exact active learning of binary and multiclass classifiers with margin. Given an $n$-point set $X \subset \mathbb{R}^m$, we want to learn any unknown classifier on $X$ whose classes have finite strong convex hull margin, a new notion extendi
Externí odkaz:
http://arxiv.org/abs/2209.03996
We study the problems of counting copies and induced copies of a small pattern graph $H$ in a large host graph $G$. Recent work fully classified the complexity of those problems according to structural restrictions on the patterns $H$. In this work,
Externí odkaz:
http://arxiv.org/abs/2209.03402
We study an active cluster recovery problem where, given a set of $n$ points and an oracle answering queries like "are these two points in the same cluster?", the task is to recover exactly all clusters using as few queries as possible. We begin by i
Externí odkaz:
http://arxiv.org/abs/2106.04913
Autor:
Bressan, Marco, Roth, Marc
We study the problems of counting the homomorphisms, counting the copies, and counting the induced copies of a $k$-vertex graph $H$ in a $d$-degenerate $n$-vertex graph $G$. Our main result establishes exhaustive and explicit complexity classificatio
Externí odkaz:
http://arxiv.org/abs/2103.05588