Narayana Santhanam

Changlong Wu, Narayana Prasad Santhanam

Given a length $n$ sample from $\mathbb{R}^d$ and a neural network with a fixed architecture with $W$ weights, $k$ neurons, linear threshold activation functions, and binary outputs on each neuron, we study the problem of uniformly sampling from all possible labelings on the sample corresponding to different choices of weights. We provide an algorithm that runs in time polynomial both in $n$ and $W$ such that any labeling appears with probability at least $\left(\frac{W}{2ekn}\right)^W$ for $W<n$. For a single neuron, we also provide a random walk based algorithm that samples exactly uniformly.

Alon Orlitsky, Narayana Santhanam, Krishnamurthy Viswanathan et al.

We consider the problem of estimating the distribution underlying an observed sample of data. Instead of maximum likelihood, which maximizes the probability of the ob served values, we propose a different estimate, the high-profile distribution, which maximizes the probability of the observed profile the number of symbols appearing any given number of times. We determine the high-profile distribution of several data samples, establish some of its general properties, and show that when the number of distinct symbols observed is small compared to the data size, the high-profile and maximum-likelihood distributions are roughly the same, but when the number of symbols is large, the distributions differ, and high-profile better explains the data.