Материал подготовлен автоматически по первоисточникам: ссылки на них — в конце статьи.
Комбинаторная размерность класса не определяет, сколько примеров нужно многоклассовому PAC-алгоритму, если после ответа он узнаёт лишь, угадал метку или нет. В препринте Guangjian Zhang, который не прошёл рецензирование и содержит расчёты самого автора, два класса с одинаковыми размерностями расходятся по сложности обучения в n раз. Поэтому BDS недостаточно для планирования объёма обучающих данных при высокой требуемой уверенности.
PAC-алгоритм должен с вероятностью не ниже 1−δ выдать классификатор с ошибкой не выше ε. BDS описывает комбинаторное разнообразие класса: сколько соседних вариантов меток он способен реализовать. Zhang нашёл два пробела в прежнем доказательстве нижней оценки и показал явные классы, где BDS равна K−1, но сложность не растёт как BDS/ε. Исправленная оценка использует якорную размерность aBDS, которая учитывает координату с общей меткой.
Главный контрпример — класс affine multiplexer из n независимых групп. Свидетельство против одной группы не помогает исключить остальные, поэтому уверенность приходится набирать отдельно для каждой. Полный профиль сложности равен Θ((n min{n, ln(1/δ)} + ln(1/δ)) / ε). Пока логарифм обратной вероятности ошибки не превышает n, цена уверенности умножается на число групп; затем наступает насыщение ранга, и основной член достигает n²/ε.
Разрыв виден у двух классов с одинаковым набором размерностей (aBDS, BDS, R)=(2n−1, 2n−1, 2n). При ε=1/16 и δ=2^(−n/4−2) классу rare-label требуется порядок n/ε примеров, а affine multiplexer — n²/ε. Значит, формула только через aBDS, BDS и число доступных меток в одной точке не даёт даже точности до полилогарифмического множителя.
Доказательства относятся к реализуемому многоклассовому обучению на независимых одинаково распределённых примерах и охватывают случайные алгоритмы, способные вернуть классификатор вне исходного класса. Общая верхняя оценка дана для любого конечного BDS, а точные профили — для явно построенных семейств. Практический риск возникает там, где продукт требует малой вероятности отказа и собирает лишь сигнал «верно или неверно»: добавочный бюджет на уверенность может превратиться в множитель.
Источники
Похоже на вашу задачу?
Расскажите, что собираете. За полчаса разложим на этапы и назовём сроки — это бесплатно и ни к чему не обязывает.
