Training multiclass classifiers on weakly labeled datasets, where labels provide only partial or noisy information about the true class, poses a significant challenge in machine learning. To address various forms of label corruption, including noisy, complementary, supplementary, or partial labels, as well as positive-unlabeled data, forward and backward correction losses have been widely employed. Adopting a general formulation that encompasses all these types of label corruption, we introduce a new family of loss functions, termed forward-backward losses, which generalizes both forward and backward correction. We analyze the theoretical properties of this family, providing sufficient conditions under which these losses are proper, ranking-calibrated, classification-calibrated, convex, or lower-bounded. This unified view will be useful to show, through theoretical analysis and experiments, that proper forward losses consistently outperform other forward-backward losses in terms of robustness and accuracy. However, the optimal choice of loss for ranking- and classification-calibrated settings remains an open question. Our work provides a comprehensive framework for weak label learning, offering new directions to develop more robust and effective algorithms.

Abstract Distributed machine learning approaches are required when training data cannot be collected in a central location, due to storage, transmission or privacy/security constraints. An important task in any distributed machine learning context, and Federated Learning is no exception, is data value estimation or credit allocation, where the goal is to reward each participant proportionally to their contribution to the final performance of the machine learning model. However, all existing data value estimation techniques require that training be completed before the data values are obtained, and in this sense they can be considered as “a posteriori” approaches. Thus, all potential contributors must participate in the training process, regardless of the quality of their data or the final reward they can obtain. Here we present an “a priori” Shapley data value estimation technique in which, based on some statistical measures provided by the participants, the central counterpart or aggregator can obtain reasonably accurate data value estimates before actually starting the distributed learning process. To the best of our knowledge, this is the first “a priori” data value estimation approach proposed in the literature, and it can be used for the pre-selection of participants or to implement new pricing schemes. The introduced algorithms have been benchmarked using a variety of datasets and a logistic regression model, and we show that our “a priori” estimates are very accurate, compared to the centralized Shapley data values.

This paper explores the mechanisms to efficiently combine annotations of different quality for multiclass classification datasets, as we argue that it is easier to obtain large collections of weak labels as opposed to true labels. Since labels come from different sources, their annotations may have different degrees of reliability (e.g., noisy labels, supersets of labels, complementary labels or annotations performed by domain experts), and we must make sure that the addition of potentially inaccurate labels does not degrade the performance achieved when using only true labels. For this reason, we consider each group of annotations as being weakly supervised and pose the problem as finding the optimal combination of such collections. We propose an efficient algorithm based on expectation-maximization and show its performance in both synthetic and real-world classification tasks in a variety of weak label scenarios.

In this paper, we describe and optimize a general scheme based on lifting transforms on graphs for video coding. A graph is constructed to represent the video signal. Each pixel becomes a node in the graph and links between nodes represent similarity between them. Therefore, spatial neighbors and temporal motion-related pixels can be linked, while nonsimilar pixels (e.g., pixels across an edge) may not be. Then, a lifting-based transform, in which filtering operations are performed using linked nodes, is applied to this graph, leading to a 3D (spatio-temporal) directional transform, which can be viewed as an extension of wavelet transforms for video. The design of the proposed scheme requires four main steps: 1) graph construction; 2) graph splitting; 3) filter design; and 4) extension of the transform to different levels of decomposition. We focus on the optimization of these steps in order to obtain an effective transform for video coding. Furthermore, based on this scheme, we propose a coefficient reordering method and an entropy coder leading to a complete video encoder that achieves better coding performance than a motion-compensated temporal filtering wavelet-based encoder, and a simple encoder derived from H.264/AVC that makes use of similar tools as our proposed encoder (reference software JM15.1 configured to use one reference frame, no subpixel motion estimation, and 16 × 16 inter and 4 × 4 intra modes).

In this paper, we propose the BGP Visibility Toolkit, a system for detecting and analyzing anomalous behavior in the Internet. We show that interdomain prefix visibility can be used to single out cases of erroneous demeanors resulting from misconfiguration or bogus routing policies. The implementation of routing policies with BGP is a complicated process, involving fine-tuning operations and interactions with the policies of the other active ASes. Network operators might end up with faulty configurations or unintended routing policies that prevent the success of their strategies and impact their revenues. As part of the Visibility Toolkit, we propose the BGP Visibility Scanner, a tool which identifies limited visibility prefixes in the Internet. The tool enables operators to provide feedback on the expected visibility status of prefixes. We build a unique set of ground-truth prefixes qualified by their ASes as intended or unintended to have limited visibility. Using a machine learning algorithm, we train on this unique dataset an alarm system that separates with 95% accuracy the prefixes with unintended limited visibility. Hence, we find that visibility features are generally powerful to detect prefixes which are suffering from inadvertent effects of routing policies. Limited visibility could render a whole prefix globally unreachable. This points towards a serious problem, as limited reachability of a non-negligible set of prefixes undermines the global connectivity of the Internet. We thus verify the correlation between global visibility and global connectivity of prefixes.

In this paper, we propose a novel censoring policy for energy-efficient transmissions in energy-harvesting sensors. The problem is formulated as an infinite-horizon Markov Decision Process (MDP). The objective to be optimized is the expected sum of the importance (utility) of all transmitted messages. Assuming that such importance can be evaluated at the transmitting node, we show that, under certain conditions on the battery model, the optimal censoring policy is a threshold function on the importance value. Specifically, messages are transmitted only if their importance is above a threshold whose value depends on the battery level. Exploiting this property, we propose a model-based stochastic scheme that approximates the optimal solution, with less computational complexity and faster convergence speed than a conventional Q-learning algorithm. Numerical experiments in single-hop and multi-hop networks confirm the analytical advantages of the proposed scheme.

In this paper, we propose the use of prefix visibility at the interdomain level as an early symptom of anomalous events in the Internet. We focus on detecting anomalies which, despite their significant impact on the routing system, remain concealed from state of the art tools. We design a machine learning system to winnow the prefixes with unintended limited visibility - symptomatic of anomalous events - from the prefixes with intended limited visibility - resulting from legitimate routing operations. We train a winnowing algorithm with ground-truth data on 20,000 operational limited visibility prefixes (LVPs) already classified by the operators of the origin networks. The ground-truth was collected using the BGP Visibility Scanner, a tool we developed to provide operators with a multi-angle view on the efficacy of their routing policies. We build a dataset with the pre-classified prefixes and the features describing their visibility status dynamics. We further use this dataset to derive a boosted decision tree which winnows unintended LVPs with an accuracy of 95%.

The basis functions of lifting transform on graphs are completely determined by finding a bipartition of the graph and defining the prediction and update filters to be used. In this work we consider the design of prediction filters that minimize the quadratic prediction error and therefore the energy of the detail coefficients, which will give rise to higher energy compaction. Then, to determine the graph bipartition, we propose a distributed maximum-cut algorithm that significantly reduces the computational cost with respect to the centralized version used in our previous work. The proposed techniques show improvements in coding performance and computational cost as compared to our previous work.

This paper discusses the problem of calibrating posterior class probabilities from partially labelled data. Each instance is assumed to be labelled as belonging to one of several candidate categories, at most one of them being true. We generalize the concept of proper loss to this scenario, establish a necessary and sufficient condition for a loss function to be proper, and we show a direct procedure to construct a proper loss for partial labels from a conventional proper loss. The problem can be characterized by the mixing probability matrix relating the true class of the data and the observed labels. An interesting result is that the full knowledge of this matrix is not required, and losses can be constructed that are proper in a subset of the probability simplex.

The minimization of the empirical risk based on an arbitrary Bregman divergence is known to provide posterior class probability estimates in classification problems, but the accuracy of the estimate for a given value of the true posterior depends on the specific choice of the divergence. Ad hoc Bregman divergences can be designed to get a higher estimation accuracy for the posterior probability values that are most critical for a particular cost-sensitive classification scenario. Moreover, some sequences of Bregman loss functions can be constructed in such a way that their minimization guarantees, asymptotically, minimum number of errors in nonseparable cases, and maximum margin classifiers in separable problems. In this paper, we analyze general conditions on the Bregman generator to satisfy this property, and generalize the result for cost-sensitive classification.

High availability communication networks with very low failure rates are often designed by using physical diversity, i.e., the traffic between a given pair of nodes is routed by using several physically disjoint paths. The selection of the pair of routes that maximizes the connectivity of a node is not an easy problem, because such connectivity cannot be expressed as an additive function of the availability of links and nodes in the path pairs. Previous algorithms for searching the optimal route use additive costs, which can be a loose assumption either when high failure rates can be locally present, or when fully disjoints paths do not exist. In this paper, we construct a Bayesian network to encode the probabilistic relation between the connectivity of a node and the availability of nodes and links. The problem of selecting an optimal pair of routes becomes equivalent to optimizing the structure of the Bayesian network. By introducing appropriate approximations on the double route availability equations, we propose a new algorithm, which outperforms other classical methods when there are sporadic high error rate elements in the network. Simulations and an application example in an electric transport telecontrol network show the performance of the method when compared to standard search.

Scenarios where nodes have limited energy and forward messages of different importances (priorities) are frequent in the context of wireless sensor networks. Tailored to those scenarios, this paper relies on stochastic tools to develop selective message forwarding schemes. The schemes will depend on parameters such as the available battery at the node, the energy cost of retransmitting a message, or the importance of messages. The forwarding schemes are designed for three different cases: 1) when sensors maximize the importance of their own transmitted messages; 2) when sensors maximize the importance of messages that have been successfully retransmitted by at least one of its neighbors; and 3) when sensors maximize the importance of messages that successfully arrive to the sink. More sophisticated schemes will achieve better importance performance, but will also require information from other sensors. The results contribute to identify the variables that, when made available to other nodes, have a greater impact on the overall network performance. Suboptimal schemes that rely on local estimation algorithms and entail reduced computational cost are also designed.

High reliability communication networks (HRCN) are characterized by very low failure rates, and extremely short unavailability periods. The accurate modeling of the link availability in HRCN is a non-trivial problem, given that an extremely low number of historic events have been observed. We propose a statistical learning model for link event prediction in HRCN based on support vector machines (SVM) for nonlinear regression. The model flexibility can be improved by grouping predictor variables of different nature. A surrogate data set is made, which mimics the basic properties of links in a real network, and it is used for simulations that yield basic knowledge about the use and performance of the proposed SVM model. A true network example, based on two years of historic data, is also analysed. The proposed SVM model yields better performance than other tested methods (frequentist, and neural network estimators), specially during the first years obtaining the historic data in a HRCN, when the number of events is critically low.

Medical applications, such as medical diagnosis, can be understood as classification problems. While usual approaches try to minimize the number of errors, medical scenarios often require classifiers that face up with different types of costs. This paper analyzes the application of a particular class of Bregman divergences to design cost sensitive classifiers for medical applications. It has been shown that these divergence measures can be used to estimate posterior probabilities with maximal accuracy for the probability values that are close to the decision boundaries. Experimental results on various medical datasets support the efficacy of our method.

An optimum selective transmission scheme for energy-limited sensor networks, where sensors send or forward messages of different importance (priority), is developed. Considering the energy costs, the available battery, the message importances and their statistical distribution, sensors decide whether to transmit or discard a message so that the importance sum of the effectively transmitted messages is maximized. It turns out that the optimal decision is made comparing the message importance with a time-variant threshold. Moreover, the gain of the selective transmission scheme, compared to a nonselective one, critically depends on the energy expenses, among other factors. Albeit suboptimal, practical schemes that operate under less demanding conditions than those for the optimal one are developed. Effort is placed into three directions: 1) the analysis of the optimal transmission policy for several stationary importance distributions; 2) the design of a transmission policy with invariant threshold that entails asymptotic optimality; and 3) the design of an adaptive algorithm that estimates the importance distribution from the actual received (or sensed) messages. Numerical results corroborating our theoretical claims and quantifying the gains of implementing the selective scheme close this paper.

A rate control (RC) algorithm for H.264 video coding with stored-B (SB) pictures is proposed for low-delay applications. Different models for P and SB pictures are defined for a better QP and MAD estimation. Furthermore, a novel saw-tooth shaped model of target buffer level has also been introduced for a proper bit allocation in GOP structures with SB pictures. Our experimental results show that this proposal outperforms the reference software RC in terms of buffer occupancy and target bit rate adjustment at the expense of slight quality reduction.

Energy is a valuable resource in wireless sensor networks since it constitutes a limiting factor for the network lifetime. In order to make an efficient use of its own energy resources, each node in the network should be aware of the energy resources at other nodes, which can be relevant to the success of their routing decisions. The proposal of this paper is twofold: (i) to design a routing algorithm based on learning patterns using geographic information and (ii) to focus on the cut down in energy consumption. We show that by exploiting local information from the signals detected at each node, sensor nodes can learn to route messages in order to improve the communication performance of the overall network and minimize the need of coordination or signalling protocols among nodes. Moreover, if messages are prioritized by some importance parameter, the overall importance of the successfully transmitted messages can be drastically improved. Experimental results highlight that our algorithm achieves a good performance in terms of successful delivery rate and maximizes the importance of the received messages.

The design of a minimum risk classifier based on data usually stems from the stationarity assumption that the conditions during training and test are the same: the misclassification costs assumed during training must be in agreement with real costs, and the same statistical process must have generated both training and test data. Unfortunately, in real world applications, these assumptions may not hold. This paper deals with the problem of training a classifier when prior probabilities cannot be reliably induced from training data. Some strategies based on optimizing the worst possible case (conventional minimax) have been proposed previously in the literature, but they may achieve a robust classification at the expense of a severe performance degradation. In this paper we propose a minimax regret (minimax deviation) approach, that seeks to minimize the maximum deviation from the performance of the optimal risk classifier. A neural-based minimax regret classifier for general multi-class decision problems is presented. Experimental results show its robustness and the advantages in relation to other approaches.

This paper proposes a novel algorithm to jointly determine the structure and the parameters of a posteriori probability model based on neural networks (NNs). It makes use of well-known ideas of pruning, splitting, and merging neural components and takes advantage of the probabilistic interpretation of these components. The algorithm, so called a posteriori probability model selection (PPMS), is applied to an NN architecture called the generalized softmax perceptron (GSP) whose outputs can be understood as probabilities although results shown can be extended to more general network architectures. Learning rules are derived from the application of the expectation-maximization algorithm to the GSP-PPMS structure. Simulation results show the advantages of the proposed algorithm with respect to other schemes.

In this paper, we analyze stochastic gradient learning rules for posterior probability estimation using networks with a single layer of weights and a general nonlinear activation function. We provide necessary and sufficient conditions on the learning rules and the activation function to obtain probability estimates. Also, we extend the concept of well-formed cost function, proposed by Wittner and Denker, to multiclass problems, and we provide theoretical results showing the advantages of this kind of objective functions.

Decision theory shows that the optimal decision is a function of the posterior class probabilities. More specifically, in binary classification, the optimal decision is based on the comparison of the posterior probabilities with some threshold. Therefore, the most accurate estimates of the posterior probabilities are required near these decision thresholds. This paper discusses the design of objective functions that provide more accurate estimates of the probability values, taking into account the characteristics of each decision problem. We propose learning algorithms based on the stochastic gradient minimization of these loss functions. We show that the performance of the classifier is improved when these algorithms behave like sample selectors: samples near the decision boundary are the most relevant during learning.

In some real applications, such as medical diagnosis or remote sensing, available training data do not often reflect the true a priori probabilities of the underlying data distribution. The classifier designed from these data may be suboptimal. Building classifiers that are robust against changes in prior probabilities is possible by applying a minimax learning strategy. In this paper, we propose a simple fixed-point algorithm that is able to train a neural minimax classifier [i.e., a classifier minimizing the worst (maximum) possible risk]. Moreover, we present a new parametric family of loss functions that is able to provide the most accurate estimates for the posterior class probabilities near the decision regions, and we also discuss the application of these functions together with a minimax learning strategy. The results of the experiments carried out on different real databases point out the ability of the proposed algorithm to find the minimax solution and produce a robust classifier when the real a priori probabilities differ from the estimated ones.

In the context of classification problems, the paper analyzes the general structure of the strict sense Bayesian (SSB) cost functions, those having a unique minimum when the soft decisions are equal to the posterior class probabilities. We show that any SSB cost is essentially the sum of a generalized measure of entropy, which does not depend on the targets, and an error component. Symmetric cost functions are analyzed in detail. Our results provide a further insight on the behavior of this family of objective functions and are the starting point for the exploration of novel algorithms. Two applications are proposed. First, the use of asymmetric SSB cost functions for posterior probability estimation in non-maximum a posteriori (MAP) decision problems. Second, a novel entropy minimization principle for hybrid learning: use labeled data to minimize the cost function, and unlabeled data to minimize the corresponding entropy measure.

Analyzing the structure of the family of cost functions that are minimum when the classifier outputs are equal to the class probabilities, we found that all of them can be expressed as sum of a generalized entropy measure and an error component. This suggests a novel algorithm for classification that uses both labeled an unlabeled data and is based on the following idea: use labeled data to minimize the cost function and unlabeled data to minimize the corresponding entropy measure. This entropy minimization principle is applied to terrain classification of Landsat images.

A new algorithm, the joint network and data density estimation (JNDDE), is proposed to estimate the 'a posteriori' probabilities of the targets with neural networks in multiple classes problems. It is based on the estimation of conditional density functions for each class with some restrictions or constraints imposed by the classifier structure and the use Bayes rule to force the a posteriori probabilities at the output of the network, known here as a implicit set. The method is applied to train perceptrons by means of Gaussian mixture inputs, as a particular example for the generalized Softmax perceptron (GSP) network. The method has the advantage of providing a clear distinction between the network architecture and the model of the data constraints, giving network parameters or weights on one side and data over parameters on the other. MLE stochastic gradient based rules are obtained for JNDDE. This algorithm can be applied to hybrid labeled and unlabeled learning in a natural fashion.

In time series problems, where time ordering is a crucial issue, the use of partial likelihood estimation (PLE) represents a specially suitable method for the estimation of parameters in the model. We propose a general supervised neural network algorithm, joint network and data density estimation (JNDDE), that employs PLE to approximate conditional probability density functions for multi-class classification problems. The logistic regression analysis is generalized to multiple class problems with a softmax regression neural network used to model the a posteriori probabilities such that they are approximated by the network outputs. Constraints to the network architecture, as well as to the model of data, are imposed, resulting in both a flexible network architecture and distribution modeling. We consider application of JNDDE to channel equalization and present simulation results.

The problem of designing cost functions to estimate a posteriori probabilities in multiclass problems is addressed in this paper. We establish necessary and sufficient conditions that these costs must satisfy in one-class one-output networks whose outputs are consistent with probability laws. We focus our attention on a particular subset of the corresponding cost functions; those which verify two usually interesting properties: symmetry and separability (well-known cost functions, such as the quadratic cost or the cross entropy are particular cases in this subset). Finally, we present a universal stochastic gradient learning rule for single-layer networks, in the sense of minimizing a general version of these cost functions for a wide family of nonlinear activation functions.

An optimal least-mean-square (LMS) algorithm is presented to be used with a lookup-table plus transversal filter adaptive echo canceller that has independent steps for the non-overlapped and overlapped parts of the transversal structure. Its advantage over previous schemes and algorithms used with this family of structures is presented. A suboptimal switched step version is discussed. Some simulation examples illustrate the performances of these schemes.>