Для массива строк из d битов с именем G и целого числа k.
Для любого массива размером k строк из d битов A и неотрицательного числа r мы определяем:
диапазон (A, r) = {h (G [1], A) <= r, h (G [2], A) <= r, ..., h (G [n], A) < = r} </p>
быть логическим массивом размера n, где h (G [i], A) обозначает расстояние Хэмминга G [i] до ближайшей строки в A (строка с наименьшим Расстояние Хэмминга).
Мы определяем диапазоны как набор всех возможных логических массивов, которые диапазон функций может вернуть нам для любого массива A и r.
V C -размерность Расстояние Хэмминга k-средних ограничено логарифмом | диапазонов | поэтому я пытаюсь найти жесткую границу для | диапазонов |.
То, что я сделал до сих пор:
Я нашел (вероятно, очень не жесткую границу ) из диапазонов | VCd
Вот что я сделал:
Расстояние Хэмминга такое же, как у евклидова квадрата расстояние, где каждый бит находится в другом измерении, поэтому:
ч (G [i], A) <= r совпадает с D ^ 2 (G [i], A) <= r, что так же, как D (G [i], A) <= sqrt (r). </p>
, где D обозначает евклидово расстояние, и теперь мы рассматриваем G [i] как d-мерную точку вместо битовой string.
Теперь мы можем думать о D (G [i], A) <= sqrt (r) как о том, находится ли G [i] внутри одной из сфер с радиусом sqrt (r) вокруг точки A, поэтому мы можем перемещать и уменьшать каждую такую сферу, чтобы она была минимальной охватывающей сферой точек из G, находящихся внутри нее, без изменения диапазона, теперь, поскольку каждая такая сфера может быть определена не более чем d + 1 точками от G и есть k сфер, диапазон может быть определен не более чем k (d + 1) точками, поэтому общее количество диапазонов ограничено: </p>
сигма i от 0 до k (d + 1) ) of (n выберите i), и это легко показать n должно быть меньше, чем n ^ (kd + 1).
Вероятно, здесь не такая уж и жесткая часть: я никогда не использовал тот факт, что значения каждого измерения точек G и A должны быть либо 0 или 1, то, что я показал здесь, это просто V C -мерность для квадратов евклидовых расстояний (которая является верхней границей для расстояний Хэмминга, но, вероятно, не жесткой). Так есть ли более жесткие ограничения для этой проблемы?