Grid Search y Random Search

Fundamentos Matemáticos de Búsqueda de Hiperparámetros

Volver

1. Fundamentos Matemáticos del Espacio de Búsqueda

Definición Formal del Espacio de Hiperparámetros

El espacio de hiperparámetros Θ se define como el producto cartesiano de los dominios individuales de cada hiperparámetro:

$$ \Theta = \Theta_1 \times \Theta_2 \times \cdots \times \Theta_n = \prod_{i=1}^{n} \Theta_i $$

Donde cada Θi puede ser:

  • Discreto finito: Θi = {v₁, v₂, ..., vpᵢ} (ej: numTrees ∈ {10, 50, 100})
  • Continuo acotado: Θi = [a, b] ⊂ ℝ (ej: regParam ∈ [0.001, 10.0])
  • Categórico: Θi = {cat₁, cat₂, ...} (ej: kernel ∈ {linear, rbf, poly})

Cardinalidad del Espacio (Espacios Discretos)

Para espacios completamente discretos, la cardinalidad (número total de configuraciones) es:

$$ |\Theta| = \prod_{i=1}^{n} |\Theta_i| = p_1 \times p_2 \times \cdots \times p_n $$

Ejemplo Concreto: Random Forest

Configuración:

  • numTrees: [10, 50, 100, 200] → |Θ₁| = 4
  • maxDepth: [5, 10, 15, 20] → |Θ₂| = 4
  • maxBins: [16, 32, 64] → |Θ₃| = 3
  • subsamplingRate: [0.6, 0.8, 1.0] → |Θ₄| = 3

Cardinalidad total:

|Θ| = 144

4 × 4 × 3 × 3 configuraciones

La Maldición de la Dimensionalidad en Tuning

El espacio de búsqueda crece exponencialmente con el número de hiperparámetros. Con n hiperparámetros y p valores por hiperparámetro (promedio):

$$ |\Theta| \approx p^n \quad \Rightarrow \quad \text{Complejidad: } O(p^n) $$
Dimensiones (n) p=3 p=5 p=10
n = 2 9 25 100
n = 3 27 125 1,000
n = 4 81 625 10,000
n = 5 243 3,125 100,000

Con 5-fold CV, cada celda se multiplica por 5. Ej: 3,125 configs × 5 folds = 15,625 entrenamientos.

Función Objetivo a Optimizar

El objetivo del tuning es encontrar la configuración óptima que minimiza el error esperado en validación:

$$ \begin{aligned} \lambda^* &= \underset{\lambda \in \Theta}{\text{argmin}} \, \mathbb{E}_{(X,Y) \sim \mathcal{D}_{\text{val}}} \left[ L(f_\lambda(X), Y) \right] \\[0.8em] &= \underset{\lambda \in \Theta}{\text{argmin}} \, \int L(f_\lambda(x), y) \, p(x, y) \, dx \, dy \end{aligned} $$

Donde:

  • λ: configuración de hiperparámetros (ej: {numTrees=100, maxDepth=10})
  • fλ: modelo entrenado con configuración λ
  • L: función de pérdida (MSE, cross-entropy, etc.)
  • 𝒟val: distribución de datos de validación

Observación Crítica

Esta función objetivo es:

  • No convexa: múltiples mínimos locales
  • No diferenciable: no podemos usar gradientes
  • Ruidosa: varía por el fold de validación
  • Costosa de evaluar: requiere entrenar modelo completo

Por eso necesitamos métodos de búsqueda especializados (Grid, Random, Bayesian).

2. Grid Search: Búsqueda Exhaustiva

Definición y Algoritmo

Grid Search evalúa exhaustivamente todas las combinaciones posibles en un grid discreto predefinido del espacio de hiperparámetros.

$$ \begin{aligned} &\text{Entrada: } \Theta_{\text{grid}} = \{(\lambda_1^{(1)}, \lambda_2^{(1)}, \ldots, \lambda_n^{(1)}), \ldots, (\lambda_1^{(N)}, \lambda_2^{(N)}, \ldots, \lambda_n^{(N)})\} \\[0.5em] &\text{Para cada } \lambda_i \in \Theta_{\text{grid}}: \\[0.3em] &\quad\quad \text{1. Entrenar modelo } f_{\lambda_i} \text{ con configuración } \lambda_i \\[0.3em] &\quad\quad \text{2. Evaluar error } CV(\lambda_i) = \frac{1}{K} \sum_{k=1}^{K} L(f_{\lambda_i}^{(-k)}, D_k) \\[0.3em] &\text{Salida: } \lambda^* = \underset{\lambda_i \in \Theta_{\text{grid}}}{\text{argmin}} \, CV(\lambda_i) \end{aligned} $$

Visualización 2D: Grid Search

graph LR
    A["Grid 4x4
(16 configs)"] --> B["λ₁ = numTrees"] A --> C["λ₂ = maxDepth"] B --> B1["10"] B --> B2["50"] B --> B3["100"] B --> B4["200"] C --> C1["5"] C --> C2["10"] C --> C3["15"] C --> C4["20"] B1 -.-> D["(10, 5)"] B1 -.-> E["(10, 10)"] B2 -.-> F["(50, 15)"] B3 -.-> G["(100, 20)"] D --> H["CV = 0.23"] E --> I["CV = 0.19"] F --> J["CV = 0.15"] G --> K["CV = 0.12 ⭐"] style A fill:#3b82f6,stroke:#60a5fa,color:#fff style G fill:#10b981,stroke:#34d399,color:#fff style K fill:#10b981,stroke:#34d399,color:#fff

Grid Search evalúa todas las 16 combinaciones y selecciona la mejor: (100, 20) con CV=0.12

Ventajas

  • 1.
    Garantía de Optimalidad: Encuentra el mejor punto dentro del grid.
    λ* = argminλ∈Θgrid CV(λ)
  • 2.
    Paralelización Perfecta: Todas las evaluaciones son independientes, permitiendo paralelización completa en cluster Spark.
  • 3.
    Reproducibilidad: Determinístico, siempre produce los mismos resultados (dado el mismo grid y datos).
  • 4.
    Interpretabilidad: Fácil visualizar superficie de error completa.

Desventajas

  • 1.
    Explosión Combinatoria: Complejidad O(pn) inmanejable en dimensiones altas.
  • 2.
    Ineficiencia en Regiones Malas: Gasta recursos evaluando configuraciones claramente subóptimas.
  • 3.
    Discretización Forzada: Hiperparámetros continuos deben discretizarse, posiblemente perdiendo el óptimo real.
  • 4.
    Mala Escalabilidad: Agregar 1 dimensión multiplica el costo por p.

Análisis de Complejidad Temporal

La complejidad total de Grid Search con K-fold cross-validation es:

$$ \begin{aligned} T_{\text{GridSearch}} &= |\Theta_{\text{grid}}| \times K \times T_{\text{train}} \\[0.5em] &= \left(\prod_{i=1}^{n} p_i\right) \times K \times T_{\text{train}} \\[0.5em] &\approx p^n \times K \times T_{\text{train}} \end{aligned} $$

Donde:

  • grid|: cardinalidad del grid (∏pᵢ)
  • K: número de folds en cross-validation (típicamente 3-10)
  • Ttrain: tiempo de entrenar el modelo una vez
  • p: promedio de valores por hiperparámetro
  • n: número de hiperparámetros

Ejemplo Numérico:

• Grid 5×5×4 = 100 configs, 5-fold CV, Ttrain = 3 minutos
• Tiempo total sin paralelización: 100 × 5 × 3 = 1,500 minutos (25 horas)
• Con 20 executors paralelos: 1,500 / 20 = 75 minutos (1.25 horas)

3. Random Search: Búsqueda Aleatoria Eficiente

Motivación y Definición

Random Search muestrea B configuraciones uniformemente del espacio de hiperparámetros (continuo o discreto), donde B es el presupuesto de evaluaciones.

$$ \begin{aligned} &\text{Entrada: } \Theta, \, B \text{ (presupuesto de evaluaciones)} \\[0.5em] &\text{Para } i = 1 \text{ hasta } B: \\[0.3em] &\quad\quad \text{1. Muestrear } \lambda_i \sim \mathcal{U}(\Theta) \text{ uniformemente} \\[0.3em] &\quad\quad \text{2. Evaluar } CV(\lambda_i) = \frac{1}{K} \sum_{k=1}^{K} L(f_{\lambda_i}^{(-k)}, D_k) \\[0.5em] &\text{Salida: } \lambda^* = \underset{i \in [1,B]}{\text{argmin}} \, CV(\lambda_i) \end{aligned} $$

Teorema de Bergstra & Bengio (2012)

Intuición clave: Si solo d de las n dimensiones son realmente importantes (d < n), Random Search explora esas dimensiones efectivas con mayor resolución que Grid Search con el mismo número de evaluaciones.

$$ \begin{aligned} &\text{Grid Search con } B \text{ evals: } B^{1/n} \text{ puntos por dimensión} \\[0.5em] &\text{Random Search con } B \text{ evals: } B \text{ puntos en dimensiones importantes} \end{aligned} $$

Ejemplo Ilustrativo:

Supón n=9 hiperparámetros, pero solo d=2 son importantes. Con B=100 evaluaciones:

  • Grid Search: 1001/9 ≈ 1.78 puntos por dimensión → ~3 valores en las 2 dimensiones importantes (grid 3×3×...)
  • Random Search: 100 samples aleatorios → ~100 valores únicos en las 2 dimensiones importantes

→ Random Search explora 33× más densamente las dimensiones críticas

Visualización Comparativa: Grid vs Random

Grid Search (9 puntos)

●   ●   ●
●   ●   ●
●   ●   ●

3×3 grid regular
(solo 3 valores únicos por dimensión)

Random Search (9 puntos)

    ●       ●
  ●     ●
        ●   ●
● ●         ●

Muestreo aleatorio
(9 valores únicos por dimensión)

Random Search tiene mayor probabilidad de encontrar el óptimo cuando las dimensiones tienen importancia heterogénea.

Ventajas

  • 1.
    Mejor en Alta Dimensionalidad: Escala mejor que Grid Search (lineal vs exponencial).
  • 2.
    Presupuesto Controlable: Parámetro B permite ajustar tiempo/precisión.
  • 3.
    Maneja Continuos Naturalmente: No requiere discretización manual.
  • 4.
    Paralelizable: Todas las evaluaciones son independientes.
  • 5.
    Convergencia Rápida: Encuentra buenos modelos antes que Grid Search.

Desventajas

  • 1.
    No Determinístico: Resultados varían entre ejecuciones (excepto con seed fijo).
  • 2.
    Sin Garantías de Optimalidad: Probabilístico, no garantiza encontrar el mejor.
  • 3.
    Puede Desperdiciar Samples: Muestrea regiones ya exploradas por azar.
  • 4.
    Difícil Visualización: No produce grid regular para graficar superficie.

Análisis de Complejidad

Random Search con presupuesto B tiene complejidad:

$$ T_{\text{RandomSearch}} = B \times K \times T_{\text{train}} $$

Nota: Independiente de n (número de hiperparámetros), a diferencia de Grid Search O(pn).

4. Análisis Probabilístico: ¿Cuántos Samples Necesito?

Probabilidad de Encontrar Región Óptima

Supongamos que la región óptima ocupa una fracción ε del espacio total (ε ∈ (0, 1)). Con Random Search de B samples, la probabilidad de al menos un sample caer en la región óptima es:

$$ \begin{aligned} P(\text{encontrar óptimo}) &= 1 - P(\text{ningún sample en región óptima}) \\[0.5em] &= 1 - (1 - \varepsilon)^B \\[0.5em] &\approx 1 - e^{-\varepsilon B} \quad \text{(para } \varepsilon \text{ pequeño)} \end{aligned} $$

Calculadora de Probabilidad

¿Cuántos samples B necesito para encontrar región óptima (fracción ε) con probabilidad ≥ 95%?

$$ \begin{aligned} 1 - (1 - \varepsilon)^B &\geq 0.95 \\[0.3em] (1 - \varepsilon)^B &\leq 0.05 \\[0.3em] B \log(1 - \varepsilon) &\leq \log(0.05) \\[0.3em] B &\geq \frac{\log(0.05)}{\log(1 - \varepsilon)} = \frac{-2.996}{\log(1 - \varepsilon)} \end{aligned} $$
Fracción Óptima (ε) Interpretación Samples para 95% (B) Samples para 99% (B)
ε = 0.10 10% del espacio es "bueno" 29 44
ε = 0.05 5% del espacio es "bueno" 59 90
ε = 0.01 1% del espacio es "bueno" 299 459
ε = 0.001 0.1% del espacio es "bueno" 2,995 4,603

Conclusión: Si la región óptima es razonablemente grande (ε ≥ 5%), Random Search con 50-100 samples tiene alta probabilidad de encontrarla.

Gráfica de Convergencia

P(encontrar) vs Samples (B):

1.0 |                  ████████████
    |              ████
0.8 |          ████
    |       ███
0.6 |     ██
    |   ██
0.4 |  █
    | █
0.2 |█
    |
0.0 +--------------------------------
    0    50   100  150  200  250  300
            Samples (B)

ε = 0.05 (5% óptimo)

Ejemplo para diferentes ε:

ε = 0.10 → B = 29

Convergencia rápida

ε = 0.05 → B = 59

Moderado

ε = 0.01 → B = 299

Convergencia lenta

ε = 0.001 → B = 2995

Muy costoso

5. Cross-Validation: Estimando el Error de Generalización

K-Fold Cross-Validation

Para evaluar cada configuración λ, necesitamos estimar su error de generalización. K-fold CV divide los datos de entrenamiento en K particiones (folds) y entrena K modelos, cada uno usando K-1 folds para entrenar y 1 para validar.

$$ CV(\lambda) = \frac{1}{K} \sum_{k=1}^{K} L(f_\lambda^{(-k)}, D_k) $$

Donde:

  • fλ(-k): modelo entrenado con config λ sin fold k
  • Dk: k-ésimo fold (datos de validación)
  • L: función de pérdida (MSE, log-loss, etc.)

Visualización de 5-Fold CV

graph TD
    A[Dataset Completo] --> B[Fold 1]
    A --> C[Fold 2]
    A --> D[Fold 3]
    A --> E[Fold 4]
    A --> F[Fold 5]

    B --> G[Iter 1: Val]
    C --> G
    D --> G
    E --> G
    F --> G

    G --> H[Modelo₁ → Error₁]

    B --> I[Iter 2: Train]
    C --> J[Iter 2: Val]
    D --> I
    E --> I
    F --> I

    I --> K[Modelo₂ → Error₂]
    J --> K

    H --> L["CV = (E₁+E₂+E₃+E₄+E₅)/5"]
    K --> L

    style A fill:#9333ea,stroke:#a855f7,color:#fff
    style L fill:#10b981,stroke:#34d399,color:#fff
                        

Cada fold actúa como validación exactamente una vez. El error promedio es el estimador CV.

Sesgo-Varianza del Estimador CV

El estimador CV(λ) es en sí una variable aleatoria (depende de los folds). Su calidad se analiza mediante:

$$ \begin{aligned} \text{Sesgo:} \quad &\mathbb{E}[CV(\lambda)] - \text{Error}_{\text{true}}(\lambda) \\[0.5em] \text{Varianza:} \quad &\text{Var}[CV(\lambda)] = \mathbb{E}\left[\left(CV(\lambda) - \mathbb{E}[CV(\lambda)]\right)^2\right] \end{aligned} $$
Mayor K (K=10, K=n):
  • Sesgo: Bajo (más datos de entrenamiento)
  • Varianza: Alta (folds más correlacionados)
  • Costo: Alto (K entrenamientos)
Menor K (K=3, K=5):
  • Sesgo: Alto (menos datos de entrenamiento)
  • Varianza: Baja (folds menos correlacionados)
  • Costo: Bajo (menos entrenamientos)

Trade-off típico: K=5 o K=10 balancean sesgo, varianza y costo computacional.

TrainValidationSplit: Alternativa Más Rápida

En lugar de K-fold CV, se puede usar una sola división train/val (típicamente 80/20):

$$ \text{Val-Error}(\lambda) = L(f_\lambda^{\text{train}}, D_{\text{val}}) $$

Ventajas:

  • K veces más rápido que K-fold CV
  • ✓ Suficiente para datasets grandes
  • ✓ Menor varianza (un solo split)

Desventajas:

  • ✗ Mayor sesgo (menos datos para entrenar)
  • ✗ Estimador menos robusto
  • ✗ Sensible a la partición elegida

Regla práctica: Usa TrainValidationSplit si N > 100K y el tiempo es crítico; usa CrossValidator si necesitas estimador robusto.

6. Implementación Completa: Grid Search en Spark ML

Implementación paso a paso de Grid Search con 5-fold cross-validation para Random Forest:

Python + PySpark Grid Search + CrossValidator
from pyspark.ml.classification import RandomForestClassifier
from pyspark.ml.evaluation import BinaryClassificationEvaluator
from pyspark.ml.tuning import CrossValidator, ParamGridBuilder
from pyspark.ml.feature import VectorAssembler

# ============================================================
# PASO 1: Preparar datos
# ============================================================
# Supongamos df_train con columnas: feature1, feature2, ..., label

assembler = VectorAssembler(
    inputCols=["feature1", "feature2", "feature3", "feature4"],  # Características
    outputCol="features"
)

df_assembled = assembler.transform(df_train)

# ============================================================
# PASO 2: Definir modelo base
# ============================================================
rf = RandomForestClassifier(
    featuresCol="features",
    labelCol="label",
    seed=42  # Para reproducibilidad
)

# ============================================================
# PASO 3: Construir grid de hiperparámetros
# ============================================================
# Definimos espacio de búsqueda: Θ = Θ₁ × Θ₂ × Θ₃ × Θ₄
paramGrid = ParamGridBuilder() \
    .addGrid(rf.numTrees, [10, 50, 100, 200]) \          # |Θ₁| = 4
    .addGrid(rf.maxDepth, [5, 10, 15, 20]) \              # |Θ₂| = 4
    .addGrid(rf.maxBins, [16, 32, 64]) \                  # |Θ₃| = 3
    .addGrid(rf.subsamplingRate, [0.6, 0.8, 1.0]) \       # |Θ₄| = 3
    .build()

# Tamaño del espacio: |Θ| = 4 × 4 × 3 × 3 = 144 configs

print(f"Total de configuraciones a evaluar: {len(paramGrid)}")
# Output: Total de configuraciones a evaluar: 144

# ============================================================
# PASO 4: Definir evaluador
# ============================================================
# Métrica: AUC-ROC (área bajo curva ROC)
evaluator = BinaryClassificationEvaluator(
    labelCol="label",
    rawPredictionCol="rawPrediction",
    metricName="areaUnderROC"  # Maximizar AUC
)

# ============================================================
# PASO 5: Configurar CrossValidator
# ============================================================
# K-fold CV con K=5, paralelización en 4 partitions
cv = CrossValidator(
    estimator=rf,                    # Modelo a tunear
    estimatorParamMaps=paramGrid,    # Grid de hiperparámetros
    evaluator=evaluator,             # Métrica de evaluación
    numFolds=5,                      # K=5 folds
    parallelism=4,                   # 4 configs en paralelo
    seed=42                          # Reproducibilidad
)

# Complejidad: 144 configs × 5 folds = 720 entrenamientos
# Con parallelism=4: 720 / 4 = 180 tareas secuenciales

# ============================================================
# PASO 6: Ejecutar Grid Search (¡esto puede tomar tiempo!)
# ============================================================
print("Iniciando Grid Search con 5-fold CV...")
print("Esto entrenará 720 modelos (144 configs × 5 folds)")

cvModel = cv.fit(df_assembled)

print("Grid Search completado!")

# ============================================================
# PASO 7: Extraer mejor modelo y parámetros
# ============================================================
# Mejor modelo encontrado
bestModel = cvModel.bestModel

# Extraer hiperparámetros óptimos
print("\n========== RESULTADOS ==========")
print(f"Mejor numTrees: {bestModel.getNumTrees}")
print(f"Mejor maxDepth: {bestModel.getMaxDepth()}")
print(f"Mejor maxBins: {bestModel.getMaxBins()}")
print(f"Mejor subsamplingRate: {bestModel.getSubsamplingRate()}")

# Mejor AUC en validación (promedio de 5 folds)
best_auc = max(cvModel.avgMetrics)
print(f"\nMejor AUC (CV): {best_auc:.4f}")

# ============================================================
# PASO 8: Analizar todos los resultados
# ============================================================
# cvModel.avgMetrics contiene AUC promedio para cada config
results = []
for idx, (params, auc) in enumerate(zip(paramGrid, cvModel.avgMetrics)):
    config = {
        "config_id": idx,
        "numTrees": params[rf.numTrees],
        "maxDepth": params[rf.maxDepth],
        "maxBins": params[rf.maxBins],
        "subsamplingRate": params[rf.subsamplingRate],
        "avg_auc": auc
    }
    results.append(config)

# Convertir a DataFrame para análisis
import pandas as pd
results_df = pd.DataFrame(results)

# Top 5 configuraciones
print("\nTop 5 configuraciones:")
print(results_df.nlargest(5, "avg_auc"))

# ============================================================
# PASO 9: Evaluar en test set
# ============================================================
df_test_assembled = assembler.transform(df_test)

predictions = bestModel.transform(df_test_assembled)
test_auc = evaluator.evaluate(predictions)

print(f"\nAUC en Test Set: {test_auc:.4f}")

# ============================================================
# PASO 10: Análisis de sensibilidad (opcional)
# ============================================================
# Ver cómo cada hiperparámetro afecta el rendimiento
print("\n========== SENSIBILIDAD POR HIPERPARÁMETRO ==========")

for param_name in ["numTrees", "maxDepth", "maxBins", "subsamplingRate"]:
    print(f"\n{param_name}:")
    sensitivity = results_df.groupby(param_name)["avg_auc"].agg(["mean", "std"])
    print(sensitivity)

# Ejemplo Output:
#             mean       std
# numTrees
# 10          0.8234    0.0123
# 50          0.8567    0.0089
# 100         0.8623    0.0076  ← Mejor promedio
# 200         0.8619    0.0081

# ============================================================
# OBSERVACIONES FINALES
# ============================================================
# 1. Grid Search garantiza encontrar el óptimo DENTRO del grid
# 2. Con 144 configs × 5 folds = 720 entrenamientos
# 3. Paralelización (parallelism=4) reduce tiempo 4x
# 4. El mejor modelo se puede usar directamente: bestModel.transform(...)
# 5. Considerar Random Search si el espacio es > 500 configs

Optimizaciones para Grid Search en Producción

  • 1.
    Coarse-to-Fine: Primero grid grueso (3 valores/dim), luego refinar región óptima.
  • 2.
    Early Stopping: Si una config es claramente mala en fold 1-2, abortar.
  • 3.
    Caching: Persistir df_assembled en memoria para evitar recomputación.
  • 4.
    Samplear datos: Para exploración inicial, usar 20-30% de datos.
  • 5.
    Guardar checkpoints: Serializar cvModel para no perder progreso.
Volver al Hub Siguiente: ParamGrid & Evaluadores