I have a question on whether the Weighted Majority Algorithm (WMA) could be used in an online learning setting where "experts" are not predefined, but they are learned, as new training examples stream-in. For instance, assume that we want to learn a set of if-then rules, where the "if" part is a conjunction of attributes and the "then" part is a class label. We assume an online setting, where the learning algorithm receives an example, makes a prediction with the current version of its rule set (1 if at least one rule fires, 0 else) and suffers the loss after the true label of the example is revealed. The rule set is updated in some way (based on the current loss) and we move on to the next example. For simplicity, assume that there is no concept drift. The goal would be to learn a good set of rules (e.g. one that is a good approximation of a target concept), while having a guarantee on the upper number of mistakes made along the way.
To make a prediction in this process, an idea would be to use the WMA with each rule in the current rule set acting as an "expert", in a WMA context, and combining independent expert advice (i.e. independent rules' predictions) to make the final prediction at each example. The main reason for this approach would be to take advantage of WMA's nice guarantees on the mistake bound. However, these guarantees (given in terms of the mistakes made by the the best expert in the committee, the total number of experts and the number of examples seen so far) are valid only when the experts are fixed from the start. But in the context I described, enumerating all "experts" (rules) from the start would yield an "committee" of size exponential in the number of possible attributes in the domain, which is clearly infeasible. So, before giving up this idea entirely, I was wondering if anyone knows of existing work where the experts for the WMA are somehow created "on demand", progressively as the learning evolves, while some guarantees on the mistake bound are still possible?