Scrap Page

Gradient Descent With Multiple Variables

$$\begin{align*} \text{repeat}&\text{ until convergence:} ; \lbrace \newline;
& w_j := w_j - \alpha \frac{\partial J(\mathbf{w},b)}{\partial w_j} \tag{1} ; & \text{for j = 0..n-1}\newline
&b\ \ := b - \alpha \frac{\partial J(\mathbf{w},b)}{\partial b} \newline \rbrace
\end{align*}$$

where, n is the number of features, parameters $w_j$, $b$, are updated simultaneously and where

$$
\begin{align}
\frac{\partial J(\mathbf{w},b)}{\partial w_j} &= \frac{1}{m} \sum\limits_{i = 0}^{m-1} (f_{\mathbf{w},b}(\mathbf{x}^{(i)}) - y^{(i)})x_{j}^{(i)} \tag{2} \\\frac{\partial J(\mathbf{w},b)}{\partial b} &= \frac{1}{m} \sum\limits_{i = 0}^{m-1} (f_{\mathbf{w},b}(\mathbf{x}^{(i)}) - y^{(i)}) \tag{3}
\end{align}
$$

• m is the number of training examples in the data set

• $f_{\mathbf{w},b}(\mathbf{x}^{(i)})$ is the model's prediction, while $y^{(i)}$ is the target value

Normalizing Features

def zscore_normalize_features(X):
    """
    computes  X, zcore normalized by column
    
    Args:
      X (ndarray (m,n))     : input data, m examples, n features
      
    Returns:
      X_norm (ndarray (m,n)): input normalized by column
      mu (ndarray (n,))     : mean of each feature
      sigma (ndarray (n,))  : standard deviation of each feature
    """
    # find the mean of each column/feature
    mu     = np.mean(X, axis=0)                 # mu will have shape (n,)
    # find the standard deviation of each column/feature
    sigma  = np.std(X, axis=0)                  # sigma will have shape (n,)
    # element-wise, subtract mu for that column from each example, divide by std for that column
    X_norm = (X - mu) / sigma      

    return (X_norm, mu, sigma)
 
#check our work
#from sklearn.preprocessing import scale
#scale(X_orig, axis=0, with_mean=True, with_std=True, copy=True)

X_norm, X_mu, X_sigma = zscore_normalize_features(X_train)

Compute the Cost for Logistic Regression

Use the logistic loss instead of the squared difference, cuz its convex

def compute_cost_logistic(X, y, w, b):
    """
    Computes cost

    Args:
      X (ndarray (m,n)): Data, m examples with n features
      y (ndarray (m,)) : target values
      w (ndarray (n,)) : model parameters  
      b (scalar)       : model parameter
      
    Returns:
      cost (scalar): cost
    """

    m = X.shape[0]
    cost = 0.0
    for i in range(m):
        z_i = np.dot(X[i],w) + b
        f_wb_i = sigmoid(z_i)
        cost +=  -y[i]*np.log(f_wb_i) - (1-y[i])*np.log(1-f_wb_i)
             
    cost = cost / m
    return cost

Compute Gradient for Logistic Regression

def compute_gradient_logistic(X, y, w, b): 
    """
    Computes the gradient for logistic regression 
 
    Args:
      X (ndarray (m,n): Data, m examples with n features
      y (ndarray (m,)): target values
      w (ndarray (n,)): model parameters  
      b (scalar)      : model parameter
    Returns
      dj_dw (ndarray (n,)): The gradient of the cost w.r.t. the parameters w. 
      dj_db (scalar)      : The gradient of the cost w.r.t. the parameter b. 
    """
    m,n = X.shape
    dj_dw = np.zeros((n,))                           #(n,)
    dj_db = 0.

    for i in range(m):
        f_wb_i = sigmoid(np.dot(X[i],w) + b)          #(n,)(n,)=scalar
        err_i  = f_wb_i  - y[i]                       #scalar
        for j in range(n):
            dj_dw[j] = dj_dw[j] + err_i * X[i,j]      #scalar
        dj_db = dj_db + err_i
    dj_dw = dj_dw/m                                   #(n,)
    dj_db = dj_db/m                                   #scalar
        
    return dj_db, dj_dw  

Solution Explanation

We are given a deterministic two‐player zero‐sum turn‐based game where:

• One player is MAX (us).
• The other player is MIN (the opponent).

We also have an oracle (O(s)) that, given any state (s) in which MIN is to move, returns the move that MIN would choose if they were playing optimally for themselves (i.e., the minimizing move).

We want to reduce this two‐player game to a single‐player search problem that correctly computes our (MAX’s) optimal policy. The key idea is:

1. When it is our turn (MAX’s turn) in state (s):

   • We branch on each possible action (a) we can take.
   • Once we pick an action (a), the state transitions to (s' = \text{Result}(s, a)).
   • Now it should be MIN’s turn in (s').
   • Instead of branching on all possible moves of MIN, we use the oracle (O(s')) to get the single best (for MIN) move (a_{\text{opp}}).
   • We then transition immediately to (s'' = \text{Result}(s', a_{\text{opp}})).
   • Hence from MAX’s perspective, the next state after our move (a) is deterministic (because the oracle effectively “collapses” MIN’s possible moves to the single best one for MIN).

2. Hence, the new “single‐player” transition is:
   [
   s
   \xrightarrow[\text{our action}]{a}
   s' = \text{Result}(s,a)
   \xrightarrow[\text{oracle for MIN}]{O(s')}
   s'' = \text{Result}(s',,O(s')).
   ]
   We treat this combined step as a single “transition” in a single‐player game: from (s) to (s'') via our choice (a).

3. We can then do a standard single‐agent search (e.g., depth‐first with memoization, or any other exhaustive search technique) over this newly defined (deterministic) state space. At each node (s) (where “it is our turn”), we branch only over our possible actions, and the opponent’s reply is fixed by the oracle.

4. Correctness follows from the fact that in the original two‐player game, MIN would indeed choose that same move if playing optimally. Thus analyzing only that single MIN move in each state is equivalent to standard minimax, but with the branching factor for MIN collapsed to 1 (the known optimal MIN move).

1. Pseudocode

Below is a high‐level pseudocode for the Oracle‐Advised Single‐Player Search that yields the same result as a full minimax search but uses the oracle to avoid branching over MIN’s actions.

FUNCTION OracleAdvisedSearch(state s):
    # If s is a terminal state, return its utility for MAX.
    if IsTerminal(s):
        return Utility(s)

    best_value ← -∞

    # For each action we (MAX) can take in state s:
    for each action a in Actions(s):
        s' ← Result(s, a)              # State after our action a
        a_opp ← O(s')                  # Oracle gives MIN's best response
        s'' ← Result(s', a_opp)        # State after MIN's best response

        # Recursively evaluate the resulting position
        value_a ← OracleAdvisedSearch(s'')

        # Update best value
        if value_a > best_value:
            best_value ← value_a

    return best_value

• IsTerminal(s) checks if (s) is a game‐ending state.
• Utility(s) returns the terminal payoff (for MAX) if (s) is terminal.
• Actions(s) returns the actions available to MAX in state (s).
• Result(s, a) returns the next state if action (a) is played in state (s).
• O(s') returns the opponent’s (MIN’s) optimal move in state (s'), per the oracle.

In many implementations, one might also keep track of the best action (not just the best value) so we can return the policy. But above we show only the value computation for simplicity.

2. Proof of Correctness (Two‐Column Proof)

Use an inductive argument on the depth of the game tree to show that OracleAdvisedSearch returns the same value that would be computed by the standard Minimax value for MAX.

Statement of What We Prove

For every state (s) in which it is MAX’s turn, the function OracleAdvisedSearch(s) returns the same value as MinimaxValue(s) (the minimax value under optimal play for both sides).

Below is a typical two‐column proof outline.

Conclusion: For every state (s), OracleAdvisedSearch(s) returns the same value as the standard minimax search would. Therefore, using the oracle to collapse MIN’s branching to a single move is a correct way to turn a two‐player game (under optimal play by MIN) into a single‐player search problem from MAX’s perspective in a deterministic, zero‐sum setting.Solution Explanation

We are given a deterministic two‐player zero‐sum turn‐based game where:

• One player is MAX (us).
• The other player is MIN (the opponent).

We also have an oracle (O(s)) that, given any state (s) in which MIN is to move, returns the move that MIN would choose if they were playing optimally for themselves (i.e., the minimizing move).

We want to reduce this two‐player game to a single‐player search problem that correctly computes our (MAX’s) optimal policy. The key idea is:

1. When it is our turn (MAX’s turn) in state (s):

   • We branch on each possible action (a) we can take.
   • Once we pick an action (a), the state transitions to (s' = \text{Result}(s, a)).
   • Now it should be MIN’s turn in (s').
   • Instead of branching on all possible moves of MIN, we use the oracle (O(s')) to get the single best (for MIN) move (a_{\text{opp}}).
   • We then transition immediately to (s'' = \text{Result}(s', a_{\text{opp}})).
   • Hence from MAX’s perspective, the next state after our move (a) is deterministic (because the oracle effectively “collapses” MIN’s possible moves to the single best one for MIN).

2. Hence, the new “single‐player” transition is:
   [
   s
   \xrightarrow[\text{our action}]{a}
   s' = \text{Result}(s,a)
   \xrightarrow[\text{oracle for MIN}]{O(s')}
   s'' = \text{Result}(s',,O(s')).
   ]
   We treat this combined step as a single “transition” in a single‐player game: from (s) to (s'') via our choice (a).

3. We can then do a standard single‐agent search (e.g., depth‐first with memoization, or any other exhaustive search technique) over this newly defined (deterministic) state space. At each node (s) (where “it is our turn”), we branch only over our possible actions, and the opponent’s reply is fixed by the oracle.

4. Correctness follows from the fact that in the original two‐player game, MIN would indeed choose that same move if playing optimally. Thus analyzing only that single MIN move in each state is equivalent to standard minimax, but with the branching factor for MIN collapsed to 1 (the known optimal MIN move).

1. Pseudocode

Below is a high‐level pseudocode for the Oracle‐Advised Single‐Player Search that yields the same result as a full minimax search but uses the oracle to avoid branching over MIN’s actions.

FUNCTION OracleAdvisedSearch(state s):
    # If s is a terminal state, return its utility for MAX.
    if IsTerminal(s):
        return Utility(s)

    best_value ← -∞

    # For each action we (MAX) can take in state s:
    for each action a in Actions(s):
        s' ← Result(s, a)              # State after our action a
        a_opp ← O(s')                  # Oracle gives MIN's best response
        s'' ← Result(s', a_opp)        # State after MIN's best response

        # Recursively evaluate the resulting position
        value_a ← OracleAdvisedSearch(s'')

        # Update best value
        if value_a > best_value:
            best_value ← value_a

    return best_value

• IsTerminal(s) checks if (s) is a game‐ending state.
• Utility(s) returns the terminal payoff (for MAX) if (s) is terminal.
• Actions(s) returns the actions available to MAX in state (s).
• Result(s, a) returns the next state if action (a) is played in state (s).
• O(s') returns the opponent’s (MIN’s) optimal move in state (s'), per the oracle.

In many implementations, one might also keep track of the best action (not just the best value) so we can return the policy. But above we show only the value computation for simplicity.

2. Proof of Correctness (Two‐Column Proof)

Use an inductive argument on the depth of the game tree to show that OracleAdvisedSearch returns the same value that would be computed by the standard Minimax value for MAX.

Statement of What We Prove

For every state (s) in which it is MAX’s turn, the function OracleAdvisedSearch(s) returns the same value as MinimaxValue(s) (the minimax value under optimal play for both sides).

Below is a typical two‐column proof outline.

$$

$$

Conclusion: For every state (s), OracleAdvisedSearch(s) returns the same value as the standard minimax search would. Therefore, using the oracle to collapse MIN’s branching to a single move is a correct way to turn a two‐player game (under optimal play by MIN) into a single‐player search problem from MAX’s perspective in a deterministic, zero‐sum setting.

MinimaxValue
(
𝑠
)

max
⁡
𝑎
 
∈
 
Actions
(
𝑠
)
min
⁡
𝑏
 
∈
 
Actions
(
Result
(
𝑠
,
𝑎
)
)
MinimaxValue
(
Result
(
Result
(
𝑠
,
𝑎
)
,
𝑏
)
)
MinimaxValue(s)=
a∈Actions(s)
max
​

b∈Actions(Result(s,a))
min
​
MinimaxValue(Result(Result(s,a),b)) if
𝑠
s is non‐terminal on MAX’s turn, and similarly for MIN’s turn.