The construction of multiclass classifiers from binary classifiers is studied in this paper, and performance is quantified by the regret, defined with respect to the Bayes optimal log-loss. We start by proving that the regret of the well known One vs. All (OVA) method is upper bounded by the sum of the regrets of its constituent binary classifiers. We then present a new method called Conditional OVA (COVA), and prove that its regret is given by the weighted sum of the regrets corresponding to the constituent binary classifiers. Lastly, we present a method termed Leveraged COVA (LCOVA), designated to reduce the regret of a multiclass classifier by breaking it down to independently optimized binary classifiers.

The essential interactive capacity of a discrete memoryless channel is defined in this paper as the maximal rate at which the transcript of any interactive protocol can be reliably simulated over the channel, using a deterministic coding scheme. In contrast to other interactive capacity definitions in the literature, this definition makes no assumptions on the order of speakers (which can be adaptive) and does not allow any use of private/public randomness; hence, the essential interactive capacity is a function of the channel model only. It is shown that the essential interactive capacity of any binary memoryless symmetric (BMS) channel is at least 0.0302 its Shannon capacity. To that end, we present a simple coding scheme, based on extended-Hamming codes combined with error detection, that achieves the lower bound in the special case of the binary symmetric channel (BSC). We then adapt the scheme to the entire family of BMS channels, and show that it achieves the same lower bound using extremes of the Bhattacharyya parameter.

We define the interactive capacity of the binary symmetric channel (BSC) as the maximal rate for which any interactive protocol can be fully and reliably simulated over a pair of BSC's. We show that this quantity is at least 1/40 of the BSC Shannon capacity, uniformly for all channel crossover probabilities. Our result is based on a public-coin rewind-if-error coding scheme in the spirit of Kol & Raz 2013 [1].

We address the problem of simulating a binary interactive protocol over a pair of binary symmetric channels with crossover probability ε. We are interested in the achievable rates of reliable simulation, i.e., in characterizing the smallest possible blowup in communications such that a vanishing error probability in the protocol length can be attained. We analyze the family of Mth-order Markovian protocols in which the transmission at every time depends only on the last M bits of the protocol. For M =1 (first-order Markovian) we prove that all protocols can be simulated at Shannon's capacity. For M > 1 we characterize large classes of protocols that can be simulated at Shannon's capacity.

We study the problem of communication over an additive white Gaussian noise (AWGN) channel with an AWGN feedback channel. When the feedback channel is noiseless, the classic Schalkwijk-Kailath (S-K) scheme is known to achieve capacity in a simple sequential fashion, while attaining reliability superior to non-feedback schemes. In this paper, we show how simplicity and reliability can be attained even when the feedback is noisy, provided that the feedback channel is sufficiently better than the feedforward channel. Specifically, we introduce a low-complexity low-delay interactive scheme that operates close to capacity for a fixed bit error probability (e.g., 10-6). We then build on this scheme to provide two asymptotic constructions, one based on high dimensional lattices, and the other based on concatenated coding, that admit an error exponent significantly exceeding the best possible non-feedback exponent. Our approach is based on the interpretation of feedback transmission as a side-information problem, and employs an interactive modulo-lattice solution.

Consider a pair of terminals connected by two independent (feedforward and feedback) Additive White Gaussian Noise (AWGN) channels, and limited by individual power constraints. The first terminal would like to reliably send information to the second terminal at a given rate. While the reliability in the cases of no feedback and of noiseless feedback is well studied, not much is known about the case of noisy feedback. In this work, we present an interactive scheme that significantly improves the reliability relative to the no-feedback setting, whenever the feedback Signal to Noise Ratio (SNR) is sufficiently larger than the feedforward SNR. The scheme combines Schalkwijk-Kailath (S-K) coding and modulo-lattice analog transmission.

We consider the problem of communication over a two-user Additive White Gaussian Noise Broadcast Channel (AWGN-BC) with an AWGN Multiple Access (MAC) active feedback. We describe a constructive reduction from this setup to the well-studied setup of linear-feedback coding over the AWGN-BC with noiseless feedback (and different parameters). This reduction facilitates the design of linear-feedback coding schemes in the (passive) noiseless feedback regime, which can then be easily and constructively transformed into coding schemes in the MAC feedback regime that attain the exact same rates. Our construction introduces an element of interaction into the coding protocol, and is based on modulo-lattice operations. As an example, we apply our method to the Ozarow-Leung scheme, and demonstrate how MAC feedback can be used to enlarge the capacity region of the AWGN-BC.

We introduce a discriminative training algorithm for the estimation of hidden Markov model (HMM) parameters. This algorithm is based on an approximation of the maximum mutual information (MMI) objective function and its maximization in a technique similar to the expectation-maximization (EM) algorithm. The algorithm is implemented by a simple modification of the standard Baum-Welch algorithm, and can be applied to speech recognition as well as to word-spotting systems. Three tasks were tested: isolated digit recognition in a noisy environment, connected digit recognition in a noisy environment and word-spotting. In all tasks a significant improvement over maximum likelihood (ML) estimation was observed. We also compared the new algorithm to the commonly used extended Baum-Welch MMI algorithm. In our tests the algorithm showed advantages in terms of both performance and computational complexity.