Title : Random Cubic Sum Graphs
Speaker : Andrew Beveridge
When : 4:30-5:30pm April 19
Where : PPB 300
Abstract:
Consider set of all graphs whose nodes are labeled with non-identity elements of the n-dimensional hypercube so that there is an edge between nodes with labels $a$ and $b$ if and only if the node $a+b$ is also in the graph (where $a+b$ is the group operation).
A random cubic sum graph is a randomly chosen element from this set where each vertex is included independently with probability $p$. As $p$ increases from $0$ to $1$, the expected structure undergoes radical changes. As with classical random graphs, we obtain thresholds functions for graph properties. In this talk, we characterize the threshold for the appearance of the first triangle, the threshold for isolated triangles and the threshold for connectivity.
Friday April 20th, 2007
3:30pm, WEH 7220
Robust Reductions from Ranking to Classification
Alina Beygelzimer, IBM Watson
We show how to convert any binary classifier learning algorithm into a ranking algorithm. The reduction is robust in the sense that it transforms classification regret R into AUC regret at most 2R. We show that this bound is tight and that the reduction provides the same regret transform as an optimal solution to the (NP-hard) feedback arc set problem. (Regret of an algorithm on a given problem is the difference between the loss incurred by the algorithm and the loss of the best predictor on the same problem.) This is a large improvement over commonly used approaches such as ordering according to regressed scores, which have a regret transform of R->NR, where N is the number of elements.
Joint work with Nina Balcan, Nikhil Bansal, Don Coppersmith, John Langford, and Greg Sorkin. To appear in COLT-07.
SPEAKER: Doru Balcan
TIME: Wednesday 12-1pm, April 18, 2007
PLACE: NSH 1507
TITLE: Characterization of Robust Linear Coding Solutions
ABSTRACT:
Many linear encoding approaches focus on representing information by approximating the underlying statistical density of the data, like PCA or ICA, or by developing encoding/decoding algorithms with desirable computational and representational properties, such as Fourier and wavelet-based codes. However, if the coefficients’ precision is limited, optimality of the representation cannot be guaranteed. The issue of optimality under limited precision is a common practical concern, and it is also relevant to biological neural representations, where the coding precision of individual neurons has been reported to be as low as a few bits per spike. In this talk, I will present a new coding scheme called Robust (Linear) Coding, that makes use of arbitrarily many coding units to minimize reconstruction error. One characteristic of Robust Coding is that it can introduce redundancy in the code to compensate for channel noise, unlike PCA or ICA, which aim to reduce redundancy. We can completely analyze the under- and overcomplete cases, and identify necessary and sufficient conditions of the optimal encoder/decoder pair in each case. In the process, we find an exact formula for the lower bound of the error function, as well as an efficient procedure for computing the optima.
Joint work with Eizaburo Doi and Mike Lewicki.
