A easy guide to gradients of softmax cross entropy loss

¶Softmax function

The softmax function, generally in neural networks, is pervasively used as the output layer of a classification task. In fact, you can think of softmax as outputting the probability of several category selections. For example, if I have a classification task to be divided into three categories, the softmax function can output the probability of three category selections based on their relative sizes, and the probability sums to 1. The input to softmax function is often called logits z_i. The function comes in the following form.

$$
a_i = \frac{e^{z_i}}{\sum_k e^{z_k}}
$$
So it’s easy to see that this function is a multiple-input-multiple-output mapping.

✏️ Leetcode Solutions with Python

Update time: 2021-02-25 09:41:32

I have solved 261 / 1772 problems

If you have any question, please give me an issue.

If you are loving solving problems in leetcode, please contact me to enjoy it together!

Welcome to Hexo! This is your very first post. Check documentation for more info. If you get any problems when using Hexo, you can find the answer in troubleshooting or you can ask me on GitHub.

¶Quick Start

¶Create a new post

1

$ hexo new "My New Post"

More info: Writing

¶Run server

1

$ hexo server

More info: Server

¶Generate static files

1

$ hexo generate

More info: Generating

¶Deploy to remote sites

1

$ hexo deploy

More info: Deployment

¶Introduction

The so-called double pointer algorithm refers to the process of traversal, instead of the normal use of a single pointer for cyclic access, two pointers in the same or opposite direction are used for scanning, so as to achieve the corresponding purpose. The double pointer method makes full use of the array ordering feature, which can simplify some operations and reduce time complexity in some cases.

It’s worthy to point out that, no matter how fancy the algorithm is, it’s just a variant of some well-known and easy-sought algorithm at the bottom. In this case, double pointer, which is O(n) in time complexity, is a special case to brutal force search. e.g. A naive brutal force algorithm can be written as:

1
2
3
4
5

​```
for (int i = 0; i < N; i++)
  for (int j = 0; j < N; j++)
    if (condition)
      continue

It’s O(n^2) at first glance, but it can essentially be O(nlogn) or O(n) depending on how condition is designed and met. So double pointers algorithm can effectively kill tons of solution space to land on a O(n) time complexity.

This article summarizes several applications of the double pointer algorithm in array-like topics.

¶Colliding Pointers

The first kind of double pointer algorithms are AKA sliding windows. Normally there will be two pointers from both end of an array and the search scope will narrow down. The data is typically sorted. A valid question to ask is, how to ensure that the sliding window covers all feasible solutions? Let’s dive in.
*167-Two sum(sorted)
*11-Container With Most Water

167-Two sum(sorted)
Given an array of integers numbers that is already *sorted in ascending order*, find two numbers such that they add up to a specific target number.

Return the indices of the two numbers (1-indexed) as an integer array answer of size 2, where 1 <= answer[0] < answer[1] <= numbers.length.

Attack

Set two pointers i and j at begin and last element. The branch pruning (or solution space compression) strategy is, if answer[i]+answer[j]<target, answer[i] can be excluded from searching because answer[i]+answer[k]<targer,k<j.

11-Container With Most Water
Given n non-negative integers a1, a2, ..., an , where each represents a point at coordinate (i, ai). n vertical lines are drawn such that the two endpoints of the line i is at (i, ai) and (i, 0). Find two lines, which, together with the x-axis forms a container, such that the container contains the most water.

Attack

Pretty similar to previous one: if min(ai,aj)*(aj-ai+1)<current_max, min(ai,aj) can be excluded from searching because cureent_max can never be attained.

¶Chasing Pointers

Chasing pointers is a pair of pointes starting one end and the left one chaseing the right. It’s a variant or representation of sliding window.
*3-Longest Substring Without Repeating Characters
*1590-Delete Sublist to Make Sum Divisible By K
*713-Subarray Product Less Than K

3-Longest Substring Without Repeating Characters

Given a string s, find the length of the longest substring without repeating characters.

Attack

If s[start]...s[end] satisfies, keep pushing right boundary, otherwise, s[end] is a repeat of some char with the above range. Find that first occurance, say index j, then start from j+1. Here we prove by contradiction why there is no missing feasible solution.
Assume candidate s[i]...s[j] is a valid substring and missed. Since the right boundary j increments by 1, the only possibility to miss is to skip over i. Assume m < i < k < j, at one point, m is fast forwarded to k. It is obvious that s[m]...s[j] is another valid substring and also longer than candidate. No need to consider the candidate and just let it go!
Similar problems:

• 30. Substring with Concatenation of All Words
• 485. Max Consecutive Ones
• 209. Minimum Size Subarray Sum

1590-Delete Sublist to Make Sum Divisible By K
You are given a list of positive integers nums and a positive integer k. Return the length of the shortest sublist (can be empty sublist ) you can delete such that the resulting list’s sum is divisible by k. You cannot delete the entire list. If it’s not possible, return -1.

Attack

You need the help from hashtable to record the mods of prefix sums. The main point of this problem is: remainderSum = totalSum - prefixsum[j] + prefixsum[i], i < j and it has to meet the requirement that mod(remainderSum,k)===0. With the pointer increments, mod(prefimsum[i],k) can be recoreded and updated by a hastable. Say prefixsum[m]-prefixsum[n], m > n, is a multiple of k , entry prefixsum[n] will be flushed out by prefixsum[m] as they both meet the requirement. Looks though only once pointer is used, the hashtable acts as a pointer.

713-Subarray Product Less Than K
Your are given an array of positive integers nums.

Count and print the number of (contiguous) subarrays where the product of all the elements in the subarray is less than k.

Attack
The solution space can be viewed as a union of A_j, 0<j<n, where A_j is the set of solutions ended with j(included). [i...j] being a solution implies [i+1...j],...,[j-1...j] are all solutions. With these, we can increment right boundary j and find the left boundary i under a certain j. Moving to next j, the last left boundary i can be reused.

¶Fast and Slow Ponters

The fast and slow pointers are also double pointers, but the two pointers traverse the array from the same side, defining the two pointers as fast and slow respectively, and the two pointers move with different strategies until the values of the two pointers are equal (or other special conditions), e.g. fast grows by two at a time and slow grows by one at a time.
*26-Remove Duplicates from Sorted Array

26-Remove Duplicates from Sorted Array
Given a sorted array nums, remove the duplicates in-place such that each element appears only once and returns the new length.

Attack
After the array is sorted, we can place two pointers i and j, where i is the slow pointer and j is the fast pointer. As soon as nums[i] = nums[j], we increment j to skip duplicate items. when encountered nums[j]!=nums[i], copy its nums[j] to nums[i+1]. Then increment i.

Similar problems:

• 27. Remove element
• 80. Remove Duplicates from Sorted Array II
• 283. Move zeros

¶Introduction

The ID recognition system is a system that can recognize ID numbers in Chinese ID card. The source of ID card can be from videos or images. For video ID recognition, this system first track ID card in a video and then recognize ID in the clearest frame. For accurate result of tracking the moving speed of the ID card should not be too fast. Also the resolution of the video should be at least 1000*600 if the ID card occupies 1/3 of one frame. To realize functions above, we used 3 image processing methods, including intelligent scissors, SURF feature tracking and ID recognition.