N. Littlestone, Manfred K. Warmuth · 1989
The construction of prediction algorithms in a situation in which a learner faces a sequence of trials, with a prediction to be made in each, and the goal of the learner is to make few mistakes is studied. It is assumed that the learner has reason to believe that one of some pool of known algorithms will perform well but does not know which one. A simple and effective method, based on weighted voting, is introduced for constructing a compound algorithm in such a circumstance. It is called the weighted majority algorithm and is shown to be robust with respect to errors in the data. Various versions of the weighted majority algorithm are discussed, and error bounds for them that are closely related to the error bounds of the best algorithms of the pool are proved.< <ETX xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">></ETX>
Cited by 308
N. Littlestone, Manfred K. Warmuth · Information and Computation · 1994
Cited by 2,009
Jacob Abernethy, Petter Nilsson · 2013
Cited by 0
Li Quan, Xikun Jiang, Boris Düdder · 2025
The rise of collaborative AI, particularly in distributed Mixture-of-Experts (MoE) systems, has created a critical challenge: how to ensure trust and transparency when aggregating proprietary models from different providers. To address this, we introduce a novel cryptographic protocol ZQ-WMA that enables verifiable and privacy-preserving online learning. Our method integrates zero-knowledge proofs with a quantized version of the Weighted Majority Algorithm, allowing a central aggregator to publicly prove it is honestly combining expert advice and updating weights according to the agreed-upon rules, all without revealing any confidential model parameters.This approach ensures that expert contributions are evaluated fairly and protects valuable intellectual property. Our analysis reveals that the quantization necessary for the zero-knowledge proofs can counter-intuitively enhance prediction accuracy, a phenomenon we attribute to the maximal entropy random walks. Furthermore, our benchmarks demonstrate the efficiency of this method, showing proof generation complexity less than 10% of a standard SHA256 hash function, with O(1) proof size and verification time. This work provides a practical and scalable framework for building trustworthy collaborative AI systems.
Cited by 0
Nick Littlestone, Manfred K. Warmuth · 1992
We study the construction of prediction algorithms in a situation in which a learner faces a sequence of trials, with a prediction to be made in each, and the goal of the learner is to make few mistakes. We are interested in the case that the learner has reason to believe that one of some pool of known algorithms will perform well, but the learner does not know which one. A simple and effective method, based on weighted voting, is introduced for constructing a compound algorithm in such a circumstance. We call this method the Weighted Majority Algorithm. We show that this algorithm is robust in the presence of errors in the data. We discuss various versions of the Weighted Majority Algorithm and prove mistake bounds for them that are closely related to the mistake bounds of the best algorithms of the pool. For example, given a sequence of trials, if there is an algorithm in the pool A that makes at most m mistakes then the Weighted Majority Algorithm will make at most c(log |A| + m) mistakes on that sequence, where c is fixed constant.
Cited by 0
Dhouha Mejri, Mohamed Limam, Claus Weihs · 2013
Dynamic weighted majority-Winnow (DWM-WIN) algorithm of [5] is a powerful classification method for nonstationary environments which copes with concept drifting data streams. DWM-WIN parameters setting in a training process impacts on the classification accuracy. Unfortunately, these parameters are randomly chosen and without any rational selection. The objective of this research study is to optimize the choice of these parameters. We use genetic algorithm (GA) of [6] as an optimization method in order to dynamically search for the best parameter values of DWM-WIN and improve the classification accuracy. To assess this optimized DWM-WIN algorithm, DWMWIN is used as a fitness function in the GA. Based on 4 datasets from UCI data sets repository, simulations have shown that the proposed DWM-WIN-GA outperforms existing classification methods.
Cited by 2
Mohammadzaman Zamani, Hamid Beigy, Amirreza Shaban · arXiv (Cornell University) · 2014
With the increasing volume of data in the world, the best approach for\nlearning from this data is to exploit an online learning algorithm. Online\nensemble methods are online algorithms which take advantage of an ensemble of\nclassifiers to predict labels of data. Prediction with expert advice is a\nwell-studied problem in the online ensemble learning literature. The Weighted\nMajority algorithm and the randomized weighted majority (RWM) are the most\nwell-known solutions to this problem, aiming to converge to the best expert.\nSince among some expert, the best one does not necessarily have the minimum\nerror in all regions of data space, defining specific regions and converging to\nthe best expert in each of these regions will lead to a better result. In this\npaper, we aim to resolve this defect of RWM algorithms by proposing a novel\nonline ensemble algorithm to the problem of prediction with expert advice. We\npropose a cascading version of RWM to achieve not only better experimental\nresults but also a better error bound for sufficiently large datasets.\n
Cited by 0Open access
Cheng-Ho Huang, Jhing-Fa Wang · 2009
The important issue in multi-class classification on support vector machines is the decision rule, which determines whether an input pattern belongs to a predicted class. To enhance the accuracy of multi-class classification, this study proposes a multi-weighted majority voting algorithm of support vector machine (SVM), and applies it to overcome complex facial security application. The proposed algorithm consists of two parts: the hierarchical classification method and the multi-weighted majority voting strategy. The proposed hierarchical classification method is an SVM assembled method to create relationally hierarchical subsets to every class; the proposed multi-weighted majority voting strategy constructs multiple decision terms to estimate the performance of the decision fusion. According to experiments on the application, the performance of FRR and FAR as 1.14% and 1.28%, respectively.
Cited by 8
K Elavarasi, G. Padmavathy · 2023
The article discusses the use of the weighted probabilistic C-Means (WPCM) System, a soft clustering technique that is commonly used for cloud-based data analytics. However, it highlights the risk of exposing sensitive information through raw data when transmitting it to the cloud for analysis. Therefore, the authors propose a modification to the WPCM algorithm that utilizes the BGV encryption system to secure the raw data during the clustering process. The BGV encryption system is a homomorphic encryption method that allows computations to be performed on encrypted data without requiring decryption. This is useful because it preserves the privacy of the data and avoids the need to decrypt it, which can be a time-consuming process. To implement the modified algorithm, the authors use polynomial approximations of the weight value calculations, membership matrix updates, and cluster center updates. The polynomial functions only involve addition and multiplication, which makes them computationally efficient. The authors use the Taylor theorem to ensure that the approximations are accurate and do not affect the overall performance of the algorithm. The effectiveness of the proposed technique is evaluated by comparing it with the standard WPCM algorithm on two large datasets (eGSAD and sWSN). The results show that the proposed method outperforms the standard method in terms of effectiveness, efficiency, and scalability. Specifically, the proposed algorithm achieves better clustering accuracy, requires less computation time, and can handle larger datasets compared to the standard algorithm.
Cited by 0
Doyin Afolabi, Oladipupo Sennaike, Shawn Ogunseye et al. · 2023
Dealing with imbalanced datasets is an essential part of most analytic lifecycles. However, an inadequate classification of imbalance datasets may result in the loss of information and insights, as well as in the reduced repurposability of the data. While most well-known classification algorithms, including the decision tree algorithm, can efficiently make predictions from balanced datasets, these algorithms are inefficient when classifying imbalanced datasets. To address this concern, the present study, building on a traditional decision tree classification algorithm – namely, the ID3 algorithm –proposes a ratio-weighted majority entropy decision tree algorithm (RAMEN). RAMEN removes bias toward the majority class in imbalanced datasets. The RAMEN algorithm is then tested on two imbalanced datasets: a cancer case dataset and a banknote verification dataset. Comparing the performances of the RAMEN technique with those of the traditional ID3 decision tree algorithm and the minority entropy-based decision tree algorithm, we find that RAMEN outperforms both aforementioned algorithms for the two datasets.
Cited by 0
Yann Braouézec · Computational Economics · 2009
Cited by 3
Yann Braouézec · HAL (Le Centre pour la Communication Scientifique Directe) · 2010
Cited by 3
Nick Littlestone, Manfred K. Warmuth Y · 1992
We study the construction of prediction algorithms in a situation in which a learner faces a sequence of trials, with a prediction to be made in each, and the goal of the learner is to make few mistakes. We are interested in the case that the learner has reason to believe that one of some pool of known algorithms will perform well, but the learner does not know which one. A simple and e ective method, based on weighted voting, is introduced for constructing a compound algorithm in such a circumstance. We call this method the Weighted Majority Algorithm. We showthat this algorithm is robust in the presence of errors in the data. We discuss various versions of the Weighted Majority Algorithm and prove mistake bounds for them that are closely related to the mistake bounds of the best algorithms of the pool. For example, given a sequence of trials, if there is an algorithm in the pool A that makes at most m mistakes then the Weighted Majority Algorithm will 1
Cited by 0
Nick Littlestone, Manfred K. Warmuth Y · 1992
We study the construction of prediction algorithms in a situation in which a learner faces a sequence of trials, with a prediction to be made in each, and the goal of the learner is to make few mistakes. We are interested in the case that the learner has reason to believe that one of some pool of known algorithms will perform well, but the learner does not know which one. A simple and e ective method, based on weighted voting, is introduced for constructing a compound algorithm in such a circumstance. We call this method the Weighted Majority Algorithm. We showthat this algorithm is robust in the presence of errors in the data. We discuss various versions of the Weighted Majority Algorithm and prove mistake bounds for them that are closely related to the mistake bounds of the best algorithms of the pool. For example, given a sequence of trials, if there is an algorithm in the pool A that makes at most m mistakes then the Weighted Majority Algorithm will 1
Cited by 0
Anil Goyal, Emilie Morvant, Massih-Reza Amini · arXiv (Cornell University) · 2018
We tackle the issue of classifier combinations when observations have multiple views. Our method jointly learns view-specific weighted majority vote classifiers (i.e. for each view) over a set of base voters, and a second weighted majority vote classifier over the set of these view-specific weighted majority vote classifiers. We show that the empirical risk minimization of the final majority vote given a multiview training set can be cast as the minimization of Bregman divergences. This allows us to derive a parallel-update optimization algorithm for learning our multiview model. We empirically study our algorithm with a particular focus on the impact of the training set size on the multiview learning results. The experiments show that our approach is able to overcome the lack of labeled information.
Cited by 0Open access
2013
Recall the prediction problem that we discussed in class. In that problem, there are n experts and on day t expert i makes prediction pi,t ∈ {−1, 1}. Based upon the experts ’ predictions, we decide to predict-1 or 1. We then observe the state of the day, st. The cost of the algorithm is the total number of mistakes that it makes. Our goal is to bound the number of mistakes against those of the best expert. Weighted Majority Algorithm In class we analyzed the weighted majority algorithm. This algorithm runs as follows: 1. Initialize wi,0 = 1 for each expert i. 2. On day t, do:
Cited by 0
Kwangmo Yang, Anastasiya Kolesnikova, Won Don Lee · Journal of information and communication convergence engineering · 2013
New incremental learning algorithm using extended data expression, based on probabilistic compounding, is presented in this paper. Incremental learning algorithm generates an ensemble of weak classifiers and compounds these classifiers to a strong classifier, using a weighted majority voting, to improve classification performance. We introduce new probabilistic weighted majority voting founded on extended data expression. In this case class distribution of the output is used to compound classifiers. UChoo, a decision tree classifier for extended data expression, is used as a base classifier, as it allows obtaining extended output expression that defines class distribution of the output. Extended data expression and UChoo classifier are powerful techniques in classification and rule refinement problem. In this paper extended data expression is applied to obtain probabilistic results with probabilistic majority voting. To show performance advantages, new algorithm is compared with Learn++, an incremental ensemble-based algorithm.
Cited by 0Open access
N. A. Salas, A. E. Korolev, В. К. Конопелько · SHILAP Revista de lepidopterología · 2019
A weighted iterative majority-logic decoding algorithm of cyclic codes with soft (quantized) detections of Phase-Modulating (PM) signals is analyzed. Evaluation of the correction capability of the algorithm on cyclic codes with quantization of PM signals of 8 levels, using a majority-logic algorithm with two decoding steps in a system of divided equations, was realized. It was shown that the obtained effectiveness evaluation of the soft decoding algorithm can be extended to cyclic codes based on majority-logic with systems of associates equations, and to compound cyclic codes.
Cited by 0Open access
Yu Chen, Liwei Xu · TELKOMNIKA Indonesian Journal of Electrical Engineering · 2014
In order to deal with the problem of low categorization accuracy of minority class of the uneven forestry information text classification algorithm, this paper puts forward the uneven forestry information text classification algorithm based on weighted Gauss-Newton neural network, on the basis of weighted Gauss-Newton algorithm, the algorithm is proved via singular value decomposition principle. The experimental result shows that the algorithm has higher classification accuracy of majority class and minority class than algorithm of common classification. The algorithm expands a new method for the research on the uneven forestry information text classification algorithm. DOI : http://dx.doi.org/10.11591/telkomnika.v12i5.4388
Cited by 1
Hao Li, Ganglin Yu, Shanfang Huang et al. · Nuclear Science and Engineering · 2019
Geometric sensitivity analyses of the k-eigenvalue have many applications in analyses of geometric uncertainty, calculations of differential control rod worth, and searches for critical geometry. The adjoint-weighted first-order geometric sensitivity theory is widely used and has continuously evolved with the Monte Carlo methods. However, the existing adjoint-weighted algorithm can do only uniform isotropic expansions or contractions of surfaces. The adjoint-weighted algorithm also requires computation of adjoint-weighted scattering and fission reaction rates exactly at material interfaces, which has an infinitesimal probability in reality. This paper presents an improved geometry adjoint-weighted perturbation algorithm that is incorporated into the continuous-energy Reactor Monte Carlo (RMC) code. The improvement of the adjoint-weighted algorithm is decomposed into three steps for constructing a cross-section function of geometric parameters using logical expressions, calculating the derivative of the cross-section function, and estimating the adjoint-weighted surface reaction rates. The improved algorithm can accommodate common one-parameter geometric perturbations of internal interfaces or boundary surfaces as well as those of cells as long as the perturbed cells can be described by logical expressions of spatial surface equations. The perturbation algorithm is compared with a direct difference method, the linear least-squares fitting method with central differences, for several typical geometric perturbations including translation, fixed-axis rotation, and uniform isotropic/anisotropic expansion transformations of planar, spherical, cylindrical, and conical surfaces. The differences between the two methods are not more than 3% and not more than 3σ for the majority of the test examples. Even though the perturbation algorithm has higher figures of merit than the direct difference method for the majority of the test examples, there is no guarantee that the former can always be more efficient than the latter. The limitation in the efficiency of the perturbation algorithm was demonstrated by the totally reflecting light water reactor pin model.
Cited by 9Open access