∑MathIntermediate

Maximum A Posteriori (MAP) Estimation

Key Points

•
Maximum A Posteriori (MAP) estimation chooses the parameter value with the highest posterior probability after seeing data.
•
MAP combines evidence from the data (likelihood) with prior beliefs (prior), formalized as P( $θ ∣ D)$ ∝ P(D| $θ) P (θ) .$
•
Taking logs turns MAP into maximizing log-likelihood plus log-prior, which is numerically stable and often convex for common models.
•
With a Gaussian prior on weights, MAP reduces to L2-regularized learning (e.g., ridge regression or regularized logistic regression).
•
For conjugate priors, MAP often has a closed-form solution (e.g., Normal–Normal, Beta–Binomial, Dirichlet–Multinomial).
•
MAP is useful when data are scarce or noisy because the prior prevents extreme estimates and reduces overfitting.
•
Unlike full Bayesian inference, MAP gives a single point estimate (the mode), not a full uncertainty distribution.
•
MAP is not invariant to reparameterization; different parameterizations can yield different MAP estimates.

Prerequisites

→Basic probability and conditional probability — MAP relies on Bayes’ rule and understanding of likelihoods, priors, and posteriors.
→Calculus (derivatives, gradients, Hessians) — Optimizing the log-posterior requires gradients, and curvature (Hessian) helps identify maxima.
→Linear algebra — Vector/matrix notation and norms are used in MAP for linear and logistic models.
→Convex optimization and gradient methods — Practical MAP often uses gradient ascent/descent and benefits from convexity insights.
→Common distributions (Normal, Bernoulli, Binomial, Dirichlet) — Recognizing conjugate pairs enables closed-form MAP solutions.

Detailed Explanation

Tap terms for definitions

01Overview

Maximum A Posteriori (MAP) estimation is a way to pick a single “best guess” for model parameters after observing data while incorporating prior knowledge. Instead of only asking which parameter values make the data most likely (as in Maximum Likelihood Estimation, MLE), MAP also weighs how plausible those parameter values were before seeing the data. Mathematically, MAP maximizes the posterior probability P(θ|D), which is proportional to the product of the likelihood P(D|θ) and the prior P(θ). In practice, we maximize the log-posterior, which is the sum of the log-likelihood and the log-prior. This makes computations numerically stable and links MAP to regularization: common priors correspond to familiar penalty terms in optimization.

MAP can produce closed-form solutions when the prior and likelihood are conjugate pairs (such as Gaussian–Gaussian or Beta–Binomial). In more complex models, we optimize the log-posterior numerically using gradient-based methods. MAP is especially appealing when data are limited or when domain knowledge suggests reasonable parameter ranges. The trade-off is that MAP provides a single point estimate rather than a full distribution over parameters. Still, it is simple, fast, and often robust, making it a practical choice in many machine learning and statistical applications.

02Intuition & Analogies

Imagine you’re trying to guess the weight of a sealed package. If you only rely on lifting it (the data), you might be fooled if the box is oddly shaped or your grip is off. But if you also know from past experience that similar boxes typically weigh around 2 kg (your prior), you’ll blend both sources: what the lift suggests and what history suggests. MAP is exactly this blend: it picks the parameter value that best balances new evidence with prior beliefs.

Another analogy: choosing a restaurant with both online reviews (data) and a trusted friend’s recommendation (prior). If reviews are few or noisy, your friend’s opinion carries more weight; as more high-quality reviews come in, they dominate your decision. MAP formalizes this trade-off: the prior is strong when data are scarce, and fades as data accumulates.

In optimization terms, think of a landscape (the log-likelihood surface) where higher elevation means better fit to data. The prior adds hills or valleys that favor plausible regions and discourage absurd ones. Maximizing the sum—the log-posterior—finds a peak that is high both because data like it and because prior knowledge approves it. With a Gaussian prior on parameters, this added landscape looks like a smooth bowl centered at zero, which is the same shape created by an L2 regularization penalty. That’s why MAP in many models is equivalent to regularized learning: it nudges parameters toward simpler, less extreme values unless the data strongly argue otherwise.

03Formal Definition

Given data D and parameter θ in a parameter space Θ, the posterior distribution is P(

θ ∣ D)

= P(D|

θ) P (θ) / P (D),

where P(D) = ∫_Θ P(D|

θ) P (θ)

dθ (or a sum for discrete Θ). The Maximum A Posteriori estimate is defined as θ_MA

P = a r g ma x_{θ \in Θ}

θ ∣ D) .

Because P(D) does not depend on

θ,

maximizing the posterior is equivalent to maximizing the unnormalized posterior: θ_MA

P = a r g ma x_{θ}

P(D

∣ θ) P (θ) . T akin g l o g s (m o n o t o n e), w ee q u a ll yso l v e θ_{M} A P = a r g ma x_{θ} [l o g P (D ∣ θ)

+ log P(

θ)

]. When P(

θ)

is uniform over Θ, MAP reduces to the Maximum Likelihood Estimator (MLE). For differentiable models on continuous Θ, stationary points satisfy ∇_θ [log P(D|

θ)

+ log P(

θ)]

= 0; local maxima are identified where the Hessian of the log-posterior is negative definite. For conjugate pairs (e.g., Normal prior with Normal likelihood, Beta prior with Binomial likelihood, Dirichlet prior with Multinomial likelihood), the posterior has the same functional form as the prior, often yielding closed-form MAP solutions. Note that MAP is a mode and is not invariant under nonlinear reparameterizations of

θ .

04When to Use

Use MAP when you have prior knowledge worth encoding (e.g., plausible parameter ranges, typical magnitudes, sparsity expectations) and when data alone may be insufficient or noisy. Common scenarios include:

Regularized learning: A Gaussian prior on weights yields L2-regularized estimators (ridge/logistic regression). A Laplace prior yields L1-regularized estimators (lasso). MAP connects Bayesian thinking with practical regularization.
Small-sample regimes: With few observations, MLE can be unstable or extreme. Priors stabilize estimates (e.g., Beta–Binomial for proportions, Dirichlet–Multinomial for categorical probabilities).
Incorporating domain constraints: Priors can encode physical constraints (positivity, bounds) or historical baselines.
Computational efficiency: MAP gives a single point and is often much faster than full Bayesian inference (e.g., MCMC). For large-scale problems, optimizing the log-posterior with gradients is tractable.
Online/iterative updates: Conjugate priors allow simple posterior updates as new data arrive, keeping MAP current with low overhead.

Avoid relying solely on MAP if uncertainty quantification is critical; consider approximate posteriors (e.g., Laplace approximation at the MAP) or full Bayesian methods instead.

⚠️Common Mistakes

Ignoring the prior’s role: Treating MAP like MLE by using an effectively flat prior when prior information exists wastes signal and can overfit.
Not taking logs: Maximizing raw probabilities leads to numerical underflow and poor optimization; always maximize the log-posterior.
Wrong sign in optimization: For Gaussian priors, the log-prior adds a negative quadratic term (−λ||θ||^2/2). Be careful whether you are doing ascent on log-posterior or descent on negative log-posterior.
Assuming invariance: MAP is not invariant to reparameterization (e.g., θ vs. φ = g(θ)). A flat prior in one parameterization is not flat in another, so MAP points can differ.
Choosing improper or ill-suited priors: Using a uniform prior on an unbounded domain is improper and can break the posterior; pick proper priors or check conditions.
Overconfident priors: Setting hyperparameters too tight can dominate the data and bias estimates heavily. Perform sensitivity analysis or tune hyperparameters (e.g., via cross-validation or empirical Bayes).
Boundary issues in conjugate models: Dirichlet–Multinomial MAP requires α_i + counts_i > 1 for interior modes; otherwise the mode lies on the boundary (some probabilities are zero). Implement checks and interpret carefully.
Stopping too early: For numerical MAP, insufficient iterations or poor step sizes can lead to suboptimal parameters; monitor the log-posterior and use line search or adaptive optimizers.

Key Formulas

Bayes' Rule

P (θ ∣ D) = \frac{P ( D ∣ θ ) P ( θ )}{P ( D )}

Explanation: The posterior equals the likelihood times the prior divided by the evidence. It updates beliefs about parameters after observing data.

MAP Definition

θ_{MAP} = ar g θ max P (θ ∣ D)

Explanation: MAP picks the parameter value with the highest posterior probability. It is the mode of the posterior distribution.

Log-Posterior Objective

θ_{MAP} = ar g θ max [lo g P (D ∣ θ) + lo g P (θ)]

Explanation: Since the logarithm is monotone and P(D) is constant in $θ,$ maximizing the posterior is equivalent to maximizing log-likelihood plus log-prior. This is numerically stable and convenient for optimization.

Stationary Condition

\nabla_{θ} [lo g P (D ∣ θ) + lo g P (θ)] = 0

Explanation: At an interior maximum, the gradient of the log-posterior is zero. Solving this yields candidate MAP points.

Normal–Normal MAP for Mean

θ_{MAP}^{Normal-Mean} = \frac{\frac{n}{σ ^{2}} x ˉ + \frac{1}{τ ^{2}} μ _{0}}{\frac{n}{σ ^{2}} + \frac{1}{τ ^{2}}}

Explanation: With known variance $σ^{2}$ and prior N( $μ_{0},$ τ^2) on the mean, the MAP is a precision-weighted average of the sample mean and prior mean. More data or smaller $σ^{2}$ tilts the estimate toward the sample mean.

MAP Logistic Regression

\overset{w}{^}_{MAP} = ar g w max i = 1 \sum n [y_{i} lo g σ (w^{⊤} x_{i}) + (1 - y_{i}) lo g (1 - σ (w^{⊤} x_{i}))] - \frac{λ}{2} ∥ w ∥_{2}^{2}

Explanation: A Gaussian prior on weights adds an L2 penalty to the log-likelihood. Here λ = 1/ $σ_{p}^{2}$ is the prior precision; maximizing this objective yields the MAP weights.

Dirichlet–Multinomial MAP

\overset{π}{^}_{i, MAP} = \frac{α _{i} + c _{i} - 1}{\sum _{j = 1}^{K} ( α _{j} + c _{j} ) - K} if α_{i} + c_{i} > 1 \forall i

Explanation: For a Dirichlet prior and Multinomial likelihood, the MAP is interior only when all concentration parameters exceed 1 after observing counts. Otherwise, the mode lies on the boundary (some probabilities are zero).

Beta–Binomial MAP

\hat{θ}_{MAP}^{Beta-Binomial} = \frac{a + s - 1}{a + b + n - 2} if a + s > 1, b + (n - s) > 1

Explanation: With θ ~ Beta(a,b) and s successes in n trials, the interior MAP exists only when the updated parameters exceed 1. Otherwise, the mode is at 0 or 1.

Laplace Approximation

P (θ ∣ D) \approx N (θ_{MAP}, - H (θ_{MAP})^{- 1})

Explanation: Near the MAP, the log-posterior is approximated by a quadratic; the posterior is approximated by a Gaussian whose covariance is the negative inverse Hessian at the MAP. This gives uncertainty estimates cheaply.

Prior Precision–Penalty Link

λ = \frac{1}{σ _{p}^{2}}

Explanation: For a zero-mean Gaussian prior with variance $σ_{p}^{2},$ the L2 penalty strength λ equals the prior precision. Larger λ shrinks parameters more strongly toward zero.

Iterative MAP Complexity

T (n, d, T_{iter}) = O (n d T_{iter})

Explanation: For gradient-based MAP in generalized linear models, each iteration costs O(nd) and we need $T_{i} t er$ iterations. Memory is typically O(nd) to store data and O(d) for parameters.

Complexity Analysis

Closed-form MAP estimators (e.g., Normal–Normal mean, Beta–Binomial, Dirichlet–Multinomial under interior conditions) can be computed in linear time in the size of the sufficient statistics. For the Normal–Normal mean with known variance, computing the sample mean is O(n) time and O(1) extra space beyond storing the data. For Dirichlet–Multinomial, counting categories is O(n + K) with O(K) space for K categories. For models requiring numerical optimization (e.g., logistic regression with a Gaussian prior), the dominant cost per iteration is evaluating the objective and its gradient, typically O(n d) where n is the number of examples and d is the number of features (including bias). Using first-order methods like gradient ascent/descent, total time is O(n d

T_{i} t er

), with

T_{i} t er

iterations to reach convergence. Second-order methods (e.g., Newton’s method) reduce iterations but require forming and inverting a d×d Hessian, costing O(n

d^{2}

d^{3}

) per iteration, which is prohibitive for large d but effective for small to medium d. Space usage is usually O(nd) to store the dataset and O(d) for parameters. Streaming or mini-batch approaches can reduce memory by processing data in chunks, yielding O(B d) working memory for batch size B. Numerical stability considerations (e.g., using log-sum-exp, stable sigmoid, and regularization) do not change asymptotic complexity but significantly affect practical performance and convergence behavior.

Code Examples

Closed-form MAP for a Normal Mean with Normal Prior (Known Variance)

1 #include <bits/stdc++.h>
2 using namespace std;
3 
4 // Compute MAP estimate of the mean with Normal prior and Normal likelihood (known variance)
5 // Model: x_i | mu ~ N(mu, sigma2); Prior: mu ~ N(mu0, tau2)
6 // Closed-form: mu_MAP = ((n/sigma2) * xbar + (1/tau2) * mu0) / ((n/sigma2) + (1/tau2))
7 
8 int main() {
9     ios::sync_with_stdio(false);
10     cin.tie(nullptr);
11 
12     // Example data
13     vector<double> x = {2.3, 2.7, 1.9, 2.1, 2.5};
14     double sigma2 = 0.2 * 0.2; // known observation variance
15 
16     // Prior hyperparameters
17     double mu0 = 2.0;   // prior mean
18     double tau2 = 0.5 * 0.5; // prior variance (larger -> weaker prior)
19 
20     // Compute sample mean
21     double sumx = accumulate(x.begin(), x.end(), 0.0);
22     double xbar = sumx / x.size();
23 
24     // MAP for mu
25     double n = static_cast<double>(x.size());
26     double mu_map = ((n / sigma2) * xbar + (1.0 / tau2) * mu0) / ((n / sigma2) + (1.0 / tau2));
27 
28     // For comparison: MLE is just the sample mean when variance is known
29     double mu_mle = xbar;
30 
31     cout.setf(std::ios::fixed); cout << setprecision(6);
32     cout << "Sample mean (MLE): " << mu_mle << "\n";
33     cout << "MAP estimate:      " << mu_map << "\n";
34     
35     // Interpretation: mu_MAP is a precision-weighted average of xbar and mu0
36     double w_data = (n / sigma2) / ((n / sigma2) + (1.0 / tau2));
37     double w_prior = 1.0 - w_data;
38     cout << "Weights -> data: " << w_data << ", prior: " << w_prior << "\n";
39 
40     return 0;
41 }
42

This program computes the MAP estimate of the mean of a Normal distribution when the observation variance is known and the prior on the mean is Normal. The MAP is a precision-weighted average of the sample mean and the prior mean. As n grows or σ^2 shrinks, the data weight increases and the MAP approaches the MLE.

Time: O(n)Space: O(1) extra (O(n) if storing all data)

MAP Logistic Regression (Gaussian Prior = L2 Regularization)

1 #include <bits/stdc++.h>
2 using namespace std;
3 
4 // Binary logistic regression with MAP estimation under a zero-mean Gaussian prior on weights.
5 // Objective to maximize (log-posterior):
6 // L(w) = sum_i [ y_i log sigma(w^T x_i) + (1 - y_i) log(1 - sigma(w^T x_i)) ] - (lambda/2) ||w||^2
7 // We perform gradient ascent with a fixed learning rate and bias term included as an extra feature.
8 
9 static inline double sigmoid(double z) {
10     // Numerically stable sigmoid
11     if (z >= 0) {
12         double ez = exp(-z);
13         return 1.0 / (1.0 + ez);
14     } else {
15         double ez = exp(z);
16         return ez / (1.0 + ez);
17     }
18 }
19 
20 int main() {
21     ios::sync_with_stdio(false);
22     cin.tie(nullptr);
23 
24     // Toy dataset: AND-like pattern
25     // Features without bias
26     vector<array<double,2>> X0 = {{array<double,2>{0,0}}, {array<double,2>{0,1}}, {array<double,2>{1,0}}, {array<double,2>{1,1}}};
27     vector<int> y = {0, 0, 0, 1};
28     const int n = (int)X0.size();
29 
30     // Build design matrix with bias as last feature
31     const int d_no_bias = 2;
32     const int d = d_no_bias + 1; // +1 for bias
33     vector<vector<double>> X(n, vector<double>(d, 1.0));
34     for (int i = 0; i < n; ++i) {
35         for (int j = 0; j < d_no_bias; ++j) X[i][j] = X0[i][j];
36         X[i][d-1] = 1.0; // bias
37     }
38 
39     // Hyperparameters
40     double lambda = 1.0; // prior precision = 1/sigma_p^2 (L2 strength)
41     double lr = 0.5;     // learning rate
42     int iters = 2000;    // iterations
43 
44     // Initialize weights
45     vector<double> w(d, 0.0);
46 
47     auto log_posterior = [&](const vector<double>& wv){
48         double L = 0.0;
49         for (int i = 0; i < n; ++i) {
50             double z = 0.0; for (int j = 0; j < d; ++j) z += wv[j]*X[i][j];
51             double p = sigmoid(z);
52             // Clamp to avoid log(0)
53             p = min(max(p, 1e-12), 1.0 - 1e-12);
54             L += y[i]*log(p) + (1 - y[i])*log(1 - p);
55         }
56         // Gaussian prior: - (lambda/2) * ||w||^2 (include bias as well here; could exclude if desired)
57         double norm2 = 0.0; for (double v : wv) norm2 += v*v;
58         L -= 0.5 * lambda * norm2;
59         return L;
60     };
61 
62     for (int it = 0; it < iters; ++it) {
63         // Compute gradient of log-posterior
64         vector<double> g(d, 0.0);
65         for (int i = 0; i < n; ++i) {
66             double z = 0.0; for (int j = 0; j < d; ++j) z += w[j]*X[i][j];
67             double p = sigmoid(z);
68             double err = (double)y[i] - p; // gradient of log-likelihood part
69             for (int j = 0; j < d; ++j) g[j] += err * X[i][j];
70         }
71         // Add gradient of log-prior: -lambda * w
72         for (int j = 0; j < d; ++j) g[j] -= lambda * w[j];
73         
74         // Gradient ascent step
75         for (int j = 0; j < d; ++j) w[j] += lr * g[j];
76 
77         // Simple learning rate decay for stability
78         if ((it+1) % 500 == 0) lr *= 0.5;
79     }
80 
81     cout.setf(std::ios::fixed); cout << setprecision(6);
82     cout << "Weights (MAP):\n";
83     for (int j = 0; j < d; ++j) cout << "w[" << j << "] = " << w[j] << "\n";
84 
85     // Evaluate accuracy
86     int correct = 0;
87     for (int i = 0; i < n; ++i) {
88         double z = 0.0; for (int j = 0; j < d; ++j) z += w[j]*X[i][j];
89         double p = sigmoid(z);
90         int pred = (p >= 0.5) ? 1 : 0;
91         correct += (pred == y[i]);
92     }
93     cout << "Training accuracy: " << correct << "/" << n << "\n";
94     cout << "Final log-posterior: " << log_posterior(w) << "\n";
95 
96     return 0;
97 }
98

This program fits a binary logistic regression model via MAP with a zero-mean Gaussian prior on the weights, which is equivalent to L2-regularized logistic regression. It maximizes the log-posterior using gradient ascent with a decaying learning rate. The gradient combines the data term and the prior term (−λw).

Time: O(n d T)Space: O(n d)

MAP for Categorical Probabilities with Dirichlet Prior (Dirichlet–Multinomial)

1 #include <bits/stdc++.h>
2 using namespace std;
3 
4 // Compute MAP estimate for categorical probabilities under a Dirichlet prior
5 // Posterior: Dir(alpha + counts). Interior MAP exists only if (alpha_i + c_i) > 1 for all i.
6 // If not interior, the posterior mode lies on the boundary; we report the posterior mean as a safe fallback.
7 
8 int main() {
9     ios::sync_with_stdio(false);
10     cin.tie(nullptr);
11 
12     // Observed categories (0..K-1)
13     vector<int> data = {0,0,1,2,2,2,1,0,2,2,1};
14     int K = 3; // number of categories
15 
16     // Dirichlet prior parameters (concentrations)
17     vector<double> alpha = {2.0, 2.0, 2.0}; // symmetric prior; >1 encourages interior MAP
18 
19     // Count occurrences
20     vector<int> counts(K, 0);
21     for (int v : data) {
22         if (v < 0 || v >= K) { cerr << "Category out of range\n"; return 1; }
23         counts[v]++;
24     }
25     int N = (int)data.size();
26 
27     // Check interior condition
28     bool interior = true;
29     for (int i = 0; i < K; ++i) if (alpha[i] + counts[i] <= 1.0) { interior = false; break; }
30 
31     vector<double> pi_hat(K, 0.0);
32     if (interior) {
33         double denom = 0.0;
34         for (int j = 0; j < K; ++j) denom += alpha[j] + counts[j] - 1.0;
35         for (int i = 0; i < K; ++i) pi_hat[i] = (alpha[i] + counts[i] - 1.0) / denom;
36         cout << "Using interior MAP (Dirichlet–Multinomial).\n";
37     } else {
38         // Fallback: posterior mean to avoid boundary degeneracy
39         double denom = 0.0; for (int j = 0; j < K; ++j) denom += alpha[j] + counts[j];
40         for (int i = 0; i < K; ++i) pi_hat[i] = (alpha[i] + counts[i]) / denom;
41         cout << "Interior MAP does not exist (some alpha_i + c_i <= 1). Reporting posterior mean instead.\n";
42     }
43 
44     cout.setf(std::ios::fixed); cout << setprecision(6);
45     cout << "Counts: "; for (int c : counts) cout << c << ' '; cout << "\n";
46     cout << "Estimated probabilities: ";
47     for (int i = 0; i < K; ++i) cout << pi_hat[i] << (i+1==K?'\n':' ');
48 
49     return 0;
50 }
51

This program estimates categorical probabilities under a Dirichlet prior. If all α_i + c_i > 1, the mode is interior and the MAP has a simple formula. Otherwise, the posterior mode lies on the boundary; the code then returns the posterior mean as a practical fallback, noting the condition.

Time: O(N + K)Space: O(K)

1	#include <bits/stdc++.h>
2	using namespace std;
3
4	// Compute MAP estimate of the mean with Normal prior and Normal likelihood (known variance)
5	// Model: x_i \| mu ~ N(mu, sigma2); Prior: mu ~ N(mu0, tau2)
6	// Closed-form: mu_MAP = ((n/sigma2) * xbar + (1/tau2) * mu0) / ((n/sigma2) + (1/tau2))
7
8	int main() {
9	ios::sync_with_stdio(false);
10	cin.tie(nullptr);
11
12	// Example data
13	vector<double> x = {2.3, 2.7, 1.9, 2.1, 2.5};
14	double sigma2 = 0.2 * 0.2; // known observation variance
15
16	// Prior hyperparameters
17	double mu0 = 2.0; // prior mean
18	double tau2 = 0.5 * 0.5; // prior variance (larger -> weaker prior)
19
20	// Compute sample mean
21	double sumx = accumulate(x.begin(), x.end(), 0.0);
22	double xbar = sumx / x.size();
23
24	// MAP for mu
25	double n = static_cast<double>(x.size());
26	double mu_map = ((n / sigma2) * xbar + (1.0 / tau2) * mu0) / ((n / sigma2) + (1.0 / tau2));
27
28	// For comparison: MLE is just the sample mean when variance is known
29	double mu_mle = xbar;
30
31	cout.setf(std::ios::fixed); cout << setprecision(6);
32	cout << "Sample mean (MLE): " << mu_mle << "\n";
33	cout << "MAP estimate: " << mu_map << "\n";
34
35	// Interpretation: mu_MAP is a precision-weighted average of xbar and mu0
36	double w_data = (n / sigma2) / ((n / sigma2) + (1.0 / tau2));
37	double w_prior = 1.0 - w_data;
38	cout << "Weights -> data: " << w_data << ", prior: " << w_prior << "\n";
39
40	return 0;
41	}
42

1	#include <bits/stdc++.h>
2	using namespace std;
3
4	// Binary logistic regression with MAP estimation under a zero-mean Gaussian prior on weights.
5	// Objective to maximize (log-posterior):
6	// L(w) = sum_i [ y_i log sigma(w^T x_i) + (1 - y_i) log(1 - sigma(w^T x_i)) ] - (lambda/2) \|\|w\|\|^2
7	// We perform gradient ascent with a fixed learning rate and bias term included as an extra feature.
8
9	static inline double sigmoid(double z) {
10	// Numerically stable sigmoid
11	if (z >= 0) {
12	double ez = exp(-z);
13	return 1.0 / (1.0 + ez);
14	} else {
15	double ez = exp(z);
16	return ez / (1.0 + ez);
17	}
18	}
19
20	int main() {
21	ios::sync_with_stdio(false);
22	cin.tie(nullptr);
23
24	// Toy dataset: AND-like pattern
25	// Features without bias
26	vector<array<double,2>> X0 = {{array<double,2>{0,0}}, {array<double,2>{0,1}}, {array<double,2>{1,0}}, {array<double,2>{1,1}}};
27	vector<int> y = {0, 0, 0, 1};
28	const int n = (int)X0.size();
29
30	// Build design matrix with bias as last feature
31	const int d_no_bias = 2;
32	const int d = d_no_bias + 1; // +1 for bias
33	vector<vector<double>> X(n, vector<double>(d, 1.0));
34	for (int i = 0; i < n; ++i) {
35	for (int j = 0; j < d_no_bias; ++j) X[i][j] = X0[i][j];
36	X[i][d-1] = 1.0; // bias
37	}
38
39	// Hyperparameters
40	double lambda = 1.0; // prior precision = 1/sigma_p^2 (L2 strength)
41	double lr = 0.5; // learning rate
42	int iters = 2000; // iterations
43
44	// Initialize weights
45	vector<double> w(d, 0.0);
46
47	auto log_posterior = [&](const vector<double>& wv){
48	double L = 0.0;
49	for (int i = 0; i < n; ++i) {
50	double z = 0.0; for (int j = 0; j < d; ++j) z += wv[j]*X[i][j];
51	double p = sigmoid(z);
52	// Clamp to avoid log(0)
53	p = min(max(p, 1e-12), 1.0 - 1e-12);
54	L += y[i]log(p) + (1 - y[i])log(1 - p);
55	}
56	// Gaussian prior: - (lambda/2) * \|\|w\|\|^2 (include bias as well here; could exclude if desired)
57	double norm2 = 0.0; for (double v : wv) norm2 += v*v;
58	L -= 0.5 * lambda * norm2;
59	return L;
60	};
61
62	for (int it = 0; it < iters; ++it) {
63	// Compute gradient of log-posterior
64	vector<double> g(d, 0.0);
65	for (int i = 0; i < n; ++i) {
66	double z = 0.0; for (int j = 0; j < d; ++j) z += w[j]*X[i][j];
67	double p = sigmoid(z);
68	double err = (double)y[i] - p; // gradient of log-likelihood part
69	for (int j = 0; j < d; ++j) g[j] += err * X[i][j];
70	}
71	// Add gradient of log-prior: -lambda * w
72	for (int j = 0; j < d; ++j) g[j] -= lambda * w[j];
73
74	// Gradient ascent step
75	for (int j = 0; j < d; ++j) w[j] += lr * g[j];
76
77	// Simple learning rate decay for stability
78	if ((it+1) % 500 == 0) lr *= 0.5;
79	}
80
81	cout.setf(std::ios::fixed); cout << setprecision(6);
82	cout << "Weights (MAP):\n";
83	for (int j = 0; j < d; ++j) cout << "w[" << j << "] = " << w[j] << "\n";
84
85	// Evaluate accuracy
86	int correct = 0;
87	for (int i = 0; i < n; ++i) {
88	double z = 0.0; for (int j = 0; j < d; ++j) z += w[j]*X[i][j];
89	double p = sigmoid(z);
90	int pred = (p >= 0.5) ? 1 : 0;
91	correct += (pred == y[i]);
92	}
93	cout << "Training accuracy: " << correct << "/" << n << "\n";
94	cout << "Final log-posterior: " << log_posterior(w) << "\n";
95
96	return 0;
97	}
98

1	#include <bits/stdc++.h>
2	using namespace std;
3
4	// Compute MAP estimate for categorical probabilities under a Dirichlet prior
5	// Posterior: Dir(alpha + counts). Interior MAP exists only if (alpha_i + c_i) > 1 for all i.
6	// If not interior, the posterior mode lies on the boundary; we report the posterior mean as a safe fallback.
7
8	int main() {
9	ios::sync_with_stdio(false);
10	cin.tie(nullptr);
11
12	// Observed categories (0..K-1)
13	vector<int> data = {0,0,1,2,2,2,1,0,2,2,1};
14	int K = 3; // number of categories
15
16	// Dirichlet prior parameters (concentrations)
17	vector<double> alpha = {2.0, 2.0, 2.0}; // symmetric prior; >1 encourages interior MAP
18
19	// Count occurrences
20	vector<int> counts(K, 0);
21	for (int v : data) {
22	if (v < 0 \|\| v >= K) { cerr << "Category out of range\n"; return 1; }
23	counts[v]++;
24	}
25	int N = (int)data.size();
26
27	// Check interior condition
28	bool interior = true;
29	for (int i = 0; i < K; ++i) if (alpha[i] + counts[i] <= 1.0) { interior = false; break; }
30
31	vector<double> pi_hat(K, 0.0);
32	if (interior) {
33	double denom = 0.0;
34	for (int j = 0; j < K; ++j) denom += alpha[j] + counts[j] - 1.0;
35	for (int i = 0; i < K; ++i) pi_hat[i] = (alpha[i] + counts[i] - 1.0) / denom;
36	cout << "Using interior MAP (Dirichlet–Multinomial).\n";
37	} else {
38	// Fallback: posterior mean to avoid boundary degeneracy
39	double denom = 0.0; for (int j = 0; j < K; ++j) denom += alpha[j] + counts[j];
40	for (int i = 0; i < K; ++i) pi_hat[i] = (alpha[i] + counts[i]) / denom;
41	cout << "Interior MAP does not exist (some alpha_i + c_i <= 1). Reporting posterior mean instead.\n";
42	}
43
44	cout.setf(std::ios::fixed); cout << setprecision(6);
45	cout << "Counts: "; for (int c : counts) cout << c << ' '; cout << "\n";
46	cout << "Estimated probabilities: ";
47	for (int i = 0; i < K; ++i) cout << pi_hat[i] << (i+1==K?'\n':' ');
48
49	return 0;
50	}
51