DEV Community: saksham780

Shapley Addictive Explanation

saksham780 — Thu, 08 Oct 2026 11:00:27 +0000

A practical, beginner-friendly guide to SHapley Additive exPlanations with a simple example and Python implementation

Imagine applying for a loan and getting rejected by a machine learning model. You ask, “Why was my application rejected?” and someone simply tells you, “The algorithm decided.”

That answer is not very useful.

Modern machine learning models such as gradient boosting, random forests, and neural networks can make highly accurate predictions, but understanding why they made those predictions can be difficult.

This is where SHAP, short for SHapley Additive exPlanations, becomes useful. SHAP explains a prediction by showing how much each feature contributed to moving the prediction up or down.

In this article, we will understand the basic idea behind SHAP, work through a small example by hand, and then use the Python shap library to explain a real machine learning model.

What Is SHAP?

SHAP is based on Shapley values, a concept from cooperative game theory introduced by mathematician Lloyd Shapley in 1953.

The basic idea is simple: when several people work together to earn a reward, how should the reward be divided fairly among them?

Imagine three friends working together on a project. Each person may contribute differently, and some contributions may become more valuable when combined with another person's contribution.

Shapley's approach is to consider the different possible orders in which the participants could join the project. For each order, we calculate how much additional value a participant brings when they join. The average of those contributions becomes that participant's fair share.

Now replace:

Friends → Features
Project reward → Model prediction
Contribution → Feature's effect on the prediction

That is the basic idea behind SHAP.

SHAP asks:

How much did each feature contribute to this particular prediction?

A Simple SHAP Example

Let's consider a fictional loan prediction model with three features:

Income
Debt
Credit history

Suppose our simplified model starts with a score of 0 when it knows nothing about the applicant.

The model behaves like this:

High income adds 30 points
Good credit history adds 20 points
Debt subtracts 10 points
Income and credit history together add an additional 10-point bonus

Therefore, when all three features are known:

30 + 20 − 10 + 10 = 50

The final score is 50.

But how much of that score should be attributed to each feature?

The interaction between income and credit history makes this less obvious

Looking at Every Possible Order

There are six possible orders in which the three features can be added.

Order	Income	Debt	History
Income → Debt → History	+30	−10	+30
Income → History → Debt	+30	−10	+30
Debt → Income → History	+30	−10	+30
Debt → History → Income	+40	−10	+20
History → Income → Debt	+40	−10	+20
History → Debt → Income	+40	−10	+20
Average	+35	−10	+25

The final SHAP contributions are therefore:

Income: +35
Debt: −10
Credit history: +25

Adding them together:

35 − 10 + 25 = 50

So the contributions exactly reconstruct the model's prediction.

The extra 10-point interaction bonus is effectively shared between income and credit history.

This is the basic idea of Shapley fairness.

The SHAP Formula

In general, the contribution of feature i can be written as:

text
φᵢ = Σ [ |S|! (n − |S| − 1)! / n! ] × [f(S ∪ {i}) − f(S)]

You do not need to memorize this formula to use SHAP.

In simple terms, it calculates the feature's average marginal contribution across different subsets of the other features, with appropriate weights so that the possible feature orderings are treated fairly.

What Does "Additive" Mean in SHAP?

The A in SHAP stands for Additive.

One of the most useful properties of SHAP is that the individual feature contributions add up to the model's output.

In simplified form:

text
Prediction =
Base value

SHAP(feature 1)
SHAP(feature 2)
...
SHAP(feature n)

Thebase value represents the model's expected output before considering the specific features of the case being explained.

Each SHAP value then moves the prediction higher or lower.

In our loan example:

text
Base value = 0

Income = +35
Debt = −10
Credit history = +25

Final prediction = 50

Why Are SHAP Values Useful?

SHAP is popular because its approach is based on several desirable properties.

Local Accuracy

The feature contributions add up to the model's output.

Missingness

A feature that is missing does not receive a contribution.

Consistency

If a feature becomes more important in the model, its SHAP contribution should not decrease under the SHAP framework.

These properties make SHAP particularly useful when we need explanations that are mathematically grounded.

SHAP in Practice

Calculating exact Shapley values can become computationally expensive because the number of possible feature combinations grows rapidly as the number of features increases.

For example, with 30 features, there are already more than a billion possible subsets.

The Python shap library therefore provides specialized explainers.

Explainer	Common Use	Speed
TreeExplainer	Random forests, XGBoost, LightGBM, gradient boosting	Fast
LinearExplainer	Linear and logistic regression	Very fast
DeepExplainer	Deep neural networks	Fast/approximate
KernelExplainer	General black-box models	Slower

For tree-based models, TreeExplainer is usually the most convenient choice.

Hands-On: Explaining a Real Model with SHAP

Let's train a gradient boosting classifier using scikit-learn's built-in breast cancer dataset.

This dataset is being used only as a teaching example. It should not be used to make real medical decisions.

First, install the required libraries:

bash
pip install shap scikit-learn matplotlib

Then use the following code:

python
import shap
from sklearn.datasets import load_breast_cancer
from sklearn.ensemble import GradientBoostingClassifier
from sklearn.model_selection import train_test_split

data = load_breast_cancer(as_frame=True)
X, y = data.data, data.target

X_train, X_test, y_train, y_test = train_test_split(
X, y, test_size=0.2, random_state=42
)

model = GradientBoostingClassifier(random_state=42)
model.fit(X_train, y_train)

print("Test accuracy:", round(model.score(X_test, y_test), 3))

explainer = shap.TreeExplainer(model)
shap_values = explainer(X_test)

i = 0
print("Base value:", round(float(shap_values.base_values[i]), 3))

top = sorted(
zip(X_test.columns, shap_values.values[i]),
key=lambda x: abs(x[1]),
reverse=True
)[:5]

for name, value in top:
print(f"{name:25s} {value:+.3f}")

You can also verify SHAP's additive property:

python
total = shap_values.base_values[i] + shap_values.values[i].sum()

print("Base + SHAP values:", round(float(total), 3))

raw = model.decision_function(X_test.iloc[[i]])[0]

print("Model raw output:", round(float(raw), 3))

Example Output

One example run produces:

text
Test accuracy: 0.956

mean concave points +1.140
worst concave points +1.119
worst perimeter +0.820
worst radius +0.582
worst area +0.566

Base + sum of SHAP : 7.055
Model raw output : 7.055

The important part is the final two values:

text
Base + sum of SHAP : 7.055
Model raw output : 7.055

They match exactly, demonstrating SHAP's additive property.

Understanding SHAP Units

One important detail is that SHAP values do not always represent probabilities.

For this classifier, the values are expressed in log-odds.

The raw model output of approximately 7.055 log-odds corresponds to a probability of roughly 99.9% for the benign class.

Positive SHAP values push the prediction toward the benign class, while negative values push it toward the malignant class.

Reading SHAP Visualizations

SHAP provides several useful plots.

Waterfall Plot

A waterfall plot explains one prediction.

It starts with the base value and shows how individual features push the prediction higher or lower until the final model output is reached.

python
shap.plots.waterfall(shap_values[0], max_display=8)

This is useful when you want to answer:

Why did the model make this particular prediction?

SHAP Bar Plot

A bar plot shows which features have the largest average absolute SHAP values across the dataset.

python
shap.plots.bar(shap_values, max_display=8)

Longer bars indicate features with larger average effects on predictions.

This is useful when you want to understand:

Which features does my model rely on most overall?

SHAP Beeswarm Plot

A beeswarm plot provides more detail by showing both the importance and direction of feature effects.

python
shap.plots.beeswarm(shap_values, max_display=8)

It is particularly useful for seeing how feature values influence predictions across many observations.

Things to Be Careful About

SHAP is powerful, but it should not be interpreted as a perfect explanation of reality.

Correlated Features

Correlated features can share credit.

For example, worst radius, worst perimeter, and worst area measure related characteristics. SHAP may distribute their contribution among them.

SHAP Explains the Model, Not Reality

If the model learned an unusual pattern from the training data, SHAP will explain that pattern faithfully.

It does not prove that a feature causes an outcome.

Computational Cost

Model-agnostic explainers such as KernelExplainer can become slow on large datasets.

Background Data Matters

The base value depends on the reference/background data used by the explainer. Therefore, that data should reasonably represent the population you want to study.

Don't Overinterpret Tiny Values

A very small SHAP value may not be practically important. Focus on features showing clearer effects.

Final Thoughts

SHAP gives machine learning practitioners a practical way to look inside model predictions.

Instead of simply saying:

"The model predicted this."

you can ask:

"Which features pushed the prediction in this direction, and by how much?"

The key idea is simple:

text
Model prediction =
Base value + contribution of each feature

For individual predictions, waterfall plots are especially useful. For understanding overall feature importance, bar plots and beeswarm plots can provide a broader view.

If you are working with a tree-based model, trying SHAP can be a great first step toward making your machine learning model easier to understand.

Have you used SHAP on a real project? What did it reveal about your model? Share your experience in the comments.

A* Search on grid based pathfinding with obstacle avoidance

saksham780 — Tue, 06 Oct 2026 13:00:55 +0000

A* Pathfinding in Python: Build a Grid Navigation Engine Around Obstacles

How a smart heuristic guides a shortest-path search, with working Python code.

Every time an enemy in a video game walks around a wall to find you, or a warehouse robot moves between shelves to reach a package, something has to work out the route. One of the most widely used algorithms for this kind of problem is A* (pronounced “A-star”).

The idea is simple: instead of exploring every direction equally, A* asks which available position looks most promising. It combines the cost of the path so far with an estimate of the remaining distance.

In this post, we will build an A* pathfinder in Python for a grid with walls.

The problem we are solving

We have a 2D grid. Each cell is either open (0) or a wall (1). We start in one cell and want to reach another, moving up, down, left, or right.

Breadth-first search (BFS) can also solve this problem when every move has the same cost. A* can reduce unnecessary exploration by using information about where the goal is.

How A* thinks: f(n) = g(n) + h(n)

A* gives every candidate cell a score and expands the cell with the lowest score first.

Term	Name	Meaning
`g(n)`	Cost so far	Exact cost from the start to the current cell.
`h(n)`	Heuristic	Estimate of the remaining cost to the goal.
`f(n)`	Total score	`g(n) + h(n)`.

For a four-direction grid, Manhattan distance is a standard heuristic:
text

h(a, b) = |a.row - b.row| + |a.col - b.col|

Manhattan distance does not overestimate the true cost in this setting, which preserves the shortest-path guarantee.

The Python implementation

python
import heapq

class Node:
def init(self, row, col):
self.row = row
self.col = col
self.g = float("inf")
self.h = 0
self.f = float("inf")
self.parent = None

def __lt__(self, other):
    return self.f < other.f

def manhattan(a, b):
return abs(a.row - b.row) + abs(a.col - b.col)

def astar(grid, start, goal):
rows, cols = len(grid), len(grid[0])

for r, c in (start, goal):
    if not (0 <= r < rows and 0 <= c < cols) or grid[r][c] == 1:
        return []

start_node = Node(*start)
goal_node = Node(*goal)

start_node.g = 0
start_node.h = manhattan(start_node, goal_node)
start_node.f = start_node.h

open_heap = [(start_node.f, start_node)]
open_lookup = {start: start_node}
closed = set()

moves = [(-1, 0), (1, 0), (0, -1), (0, 1)]

while open_heap:
    _, current = heapq.heappop(open_heap)
    pos = (current.row, current.col)

    if pos in closed:
        continue

    open_lookup.pop(pos, None)

    if pos == goal:
        path = []
        while current:
            path.append((current.row, current.col))
            current = current.parent
        return path[::-1]

    closed.add(pos)

    for dr, dc in moves:
        nr, nc = current.row + dr, current.col + dc

        if not (0 <= nr < rows and 0 <= nc < cols):
            continue
        if grid[nr][nc] == 1 or (nr, nc) in closed:
            continue

        new_g = current.g + 1
        neighbor = open_lookup.get((nr, nc))

        if neighbor is None:
            neighbor = Node(nr, nc)
            neighbor.h = manhattan(neighbor, goal_node)
            open_lookup[(nr, nc)] = neighbor
        elif new_g >= neighbor.g:
            continue

        neighbor.parent = current
        neighbor.g = new_g
        neighbor.f = new_g + neighbor.h
        heapq.heappush(open_heap, (neighbor.f, neighbor))

return []

Seeing it work

python
from astar import astar

grid = [
[0, 0, 0, 0, 0, 0],
[0, 1, 1, 1, 1, 0],
[0, 0, 0, 0, 1, 0],
[0, 1, 1, 0, 1, 0],
[0, 0, 0, 0, 0, 0],
]

path = astar(grid, start=(0, 0), goal=(4, 5))
print("Path found in", len(path) - 1, "steps")
print(path)


Output:

text
Path found in 9 steps
[(0, 0), (1, 0), (2, 0), (3, 0), (4, 0),
 (4, 1), (4, 2), (4, 3), (4, 4), (4, 5)]

The route can be visualised as:

text
S . . . . .

# # # # .
. . . # .
# # . # .
* * * * G

How fast is it?

In the worst case, A* may need to examine many or even all cells. With a binary heap, a common rough bound for this implementation is O(N log N) for N discovered cells. In practice, a good heuristic can keep the search focused.

Memory usage is O(N) because the algorithm stores information about discovered cells.

Common mistakes to avoid

Mixing up row and column.
Forgetting the closed-set check.
Using a heuristic that overestimates the remaining cost when you need a shortest-path guarantee.
Not validating the start and goal.

Where to go from here

Add diagonal movement and use octile distance.
Add weighted terrain.
Explore Jump Point Search or hierarchical pathfinding.
Visualise the open and closed sets.

Final takeaway

A* connects a simple mathematical idea with practical software. The formula f(n) = g(n) + h(n), a priority queue, and a few sets are enough to build a shortest-path solver for a four-direction grid.

Once you understand this version, the same structure can be adapted to game maps, road networks, warehouse robots, and other navigation problems.

Suggested tags: Python, Algorithms, A-Star, Pathfinding, Data Structures, DSA, Programming

Stimulate TRIE data structure

saksham780 — Tue, 06 Oct 2026 12:34:14 +0000

How to Build a Fast Search-as-You-Type Autocomplete Engine Using Tries

A practical guide to prefix trees in Python, with code you can run and extend.

You type two letters into a search bar and, before you have even decided on the third, a list of suggestions is already waiting. It feels like magic, but it is really a data structure doing its job. Behind many autocomplete boxes is a system that can answer a simple question quickly: “What starts with these letters?”
If you have ever tried to build this with a database query or a loop over a list, you may have noticed the problem: it works well with a small list and becomes less attractive as the number of words grows. A Trie, also called a prefix tree, is a data structure designed specifically for prefix-based lookups.
In this post, we will see why the obvious approach can become slow, how a Trie works, and how to build a simple autocomplete engine in Python from scratch.

Why the obvious approach gets slow

Imagine an online shop with 100,000 product names. A customer types "cat". A simple solution is to check every product and keep the names that start with "cat". In Python, that could be a loop using starts with; in SQL, it could be a prefix query such as WHERE name LIKE 'cat%'.

With N words, you may perform up to N comparisons for every keystroke. As the catalogue grows, the search box has more work to do.

A database index can make prefix queries fast, and for many applications that is enough. But when you want a lightweight in-memory autocomplete engine that responds on every keystroke, a Trie is a useful alternative because it stores shared prefixes together.

What is a Trie?

A Trie (the name comes from "retrieval", and is usually pronounced "try") is a tree where each step down the tree adds one character. Instead of storing each word as one separate object, words are represented as paths from the root.

Words with the same beginning share the same path. This means a prefix is represented once, and the node you reach tells you exactly which prefix you have matched.

For example, here is how cat, to, and top can be stored. A star (*) marks a node where a complete word ends:

text
(root)
/ \
c t
| |
a o*
| |
t* p*

Reading down the left branch gives cat. On the right, to is a complete word, while top extends it. The star is what tells us that a node represents a complete stored word.

Why is it fast?

To find words beginning with c, we do not scan the entire dictionary. We start at the root, follow the c branch, and immediately reach the part of the tree containing that prefix.

Finding the prefix takes O(L) time, where L is the length of the prefix. However, collecting the suggestions underneath that prefix still depends on how many matching words there are.

Building a Trie in Python

python
class TrieNode:
def init(self):
self.children = {}
self.is_end_of_word = False

class Trie:
def init(self):
self.root = TrieNode()

def insert(self, word: str) -> None:
    node = self.root
    for char in word:
        if char not in node.children:
            node.children[char] = TrieNode()
        node = node.children[char]
    node.is_end_of_word = True

def search_prefix(self, prefix: str) -> list:
    node = self.root
    for char in prefix:
        if char not in node.children:
            return []
        node = node.children[char]

    results = []
    self._collect(node, prefix, results)
    return results

def _collect(self, node: TrieNode, word: str, results: list) -> None:
    if node.is_end_of_word:
        results.append(word)

    for char, child in node.children.items():
        self._collect(child, word + char, results)

if name == "main":
engine = Trie()
words = ["cat", "car", "cart", "dog", "dodge", "deer", "testing"]

for word in words:
    engine.insert(word)

user_input = "ca"
suggestions = engine.search_prefix(user_input)

print(f"User typed: '{user_input}'")
print(f"Suggestions: {suggestions}")

Output:

text
User typed: 'ca'
Suggestions: ['cat', 'car', 'cart']

How the code works

Inserting a word

insert() walks through the word one character at a time. If a character branch does not exist, it creates a new node. When the last character is reached, is_end_of_word is set to True.

Searching by prefix

search_prefix() first follows the typed prefix. If a character is missing, no stored word starts with that prefix. It then uses _collect() to traverse the matching subtree and gather complete words.

Time and space complexity

Operation	Complexity	Explanation
Insert a word	O(L)	L is the length of the word.
Check a prefix	O(L)	Depends on the prefix length.
Get suggestions	O(L + M)	M is the number of visited nodes while collecting matches.
Memory	O(total characters)	Shared prefixes reduce repeated storage.

Taking it to production

Frequency weights: rank popular suggestions higher.
Top-k caching: store the best few completions at each node.
Radix trees: compress chains of single-child nodes.
Input normalization and fuzzy matching: handle case differences and typing mistakes.

When a Trie is not the right tool

If the list is tiny, a normal list with startswith() may be simpler. For full-text search, typo tolerance, and relevance ranking across large documents, a dedicated search engine may be a better fit.

Final takeaway

A Trie changes autocomplete from “scan everything” into “follow the letters.” The core idea is small, but the same prefix-tree concept can support search boxes, spell checkers, keyboard suggestions, and other prefix-based features.

A good next exercise is to add a frequency counter and return only the top five suggestions.

Suggested tags: Python, Data Structures, Algorithms, Trie, Autocomplete, Programming