-
Neural Semantic Encoders
The NSE is made up of three neural networks-
- the read layer,
- the write layer
- and the compose layer.
They operate on the encoding memory to perform the namesake operations. The encoding memory is different form the neural network parameters. It is of dimension M ∈ Rk × l where k is the hidden dimension of the representations stored and l is the sequence length. Note: this is a single matrix maintained for all the data points in the set. The memory is initialized by the embedding vectors of the input sequence and is evolved over time. In some cases it is found as expected that the read module produces a key or points to a memory slot same as the input word, in this case they chose the second most probable memory slot as the associatively coherent word.
Important list of vectors -
- xt ∈ Rk this is the input to the LSTM (word embedding)
- ot ∈ Rk this is the hidden state (output) produced by the LSTM
- zt ∈ Rl this is the key vector shared between the read and write module
the read module neural network ot = frLSTM(xt)
the key vector zt is produced by attending over the memory at the previous time step, indicated by the equation zt = softmax(otTMt-1) Note: this is essentially a dot product happening between the hidden state and the memory slots to find the most coherently associated memory slot
Sine the key vector is fuzzy the final answer is got by taking a weighted sum of the key vector with all the memory slots, this is indicated by the equation mr,t = ztTMt-1 This can also be viewed as a soft attention mechanism
The next equations compose and write to the memory slot previously read
-
longest palindromic substring
In this post I want to guide you to develop intuition and understanding for the longest palindromic substring Pi and ∑iPi
Brute force
Using two points i, j we can run down all possible substrings of a string. There would be $N^2$ of them. For each substring we iterate the substring to check if it is a palindrome. This would result in a total worst case complexity of $N^3$
Slightly better approach
Here, we use the insight that a palindrome is symmetric around its centre (for odd length palindromes) and for even this centre is the empty space between the characters. Consider the examples,
“madam” symmetric about ‘d’ “oo” symmetric about
for k in xrange(0, len(str_s)): #for odd length palindromes centred around str_s[k] i, j, opl = k - 1, k + 1, 1 while i > 0 and j < len(str_s): if str_s[i] == str_s[j]: opl++ i -= 1 j += 1 #for even length palindromes i, j, epl = k, k+1, 1 while i > 0 and j < len(str_s): if str_s[i] == str_s[j]: epl++ i -= 1 j += 1 max_pl = math.max(epl, opl)
-
multicast in distributed systems
FIFO multicast
Basically says that messsages from the same sender are delivered at each receiver in the order in which it was sent from that particular sender, we do not care in what relative order messages from different senders are delivered. Hence, the algorithm
Notation: the vector
pi[,,,]
denotes the number of events seen so far for each respective index (length of vector equals number of processes in the multicast group)- When process pj sent a message
- pj[j] += 1
- include pj[j] in the multicast message as its sequence number
- When process pi receives a mulicast from pj with sequence number S in message
if msg.ts == pi[j] + 1: deliver msg to application pi[j] += 1 else: buffer msg till condition is true
Totally ordered multicast
Ensures that all receivers get the messages in the same order i.e. its focus is on the consistency of messages received across all processes in the multicast group. It doesn’t guarentee messages of one sender are received in the same order it was sent.
We use a central sequencer, so first we run a leader election algorithm to choose a sequencer or leader. Then the algorithm,
- When a process Pi wants to send a message
- Sends the multicast to the group as well as the sequencer/leader
- Sequencer maintains a global sequence number
S
initially 0 - When it receives a message
M
, it setsS = S + 1
and multicasts<M,S>
- Receive multicast at Pi
- It maintains a local received global sequence number
Si
(initially 0) - If Pi receives a multicast M from Pj, it buffers it untill
- Pi receives the multicast
<M, S(M)>
from the sequencer Si + 1 == S(M)
- After delivering the message to the application set
Si += 1
- It maintains a local received global sequence number
Causal ordering
Multicasts whose send events are causally related by a causal path, must be received in the same causality-obeying order at all receivers. Formally,
- If send_event_multicast(g,m) -> send_event_mutlicast(g, m’) then any correct process that delivers m’ would already have been delivered m.
- Each process Pi maintains a vector Pi[1..N] whose length equals the number of processes in the multicast group
- Each value of the vector indicates the number of events that Pi has seen occured
When a process Pi wants to send a message
- Sets Pi[i] += 1
- Include the whole vector Pi in the multicast message
When a process Pj receives a message from Pi. It buffers the message untill both
- Pj is expecting msg.ts[i] as the next sequence from Process Pi
Pj[i] + 1 == msg.ts[i]
- Receiver Pj satisfies causality which was true at the time of send for Pi
for k != i Pj[k] >= msg.ts[k]
After the above condition is satisfied logical clock needs to be updated before message delivery.
- set
Pj[i] = max(msg.ts[i], Pj[i])
- Before delivery to app layer update self clock
Pj[j] += 1
Note: Causal ordering implies FIFO ordering
- set
- When process pj sent a message