hidden_markov_model_part2.py

    def inference(self, sentence: List[str]) -> Tuple[List[int], List[float]]:
        probabilities = np.zeros((len(self.Q), len(sentence)))
        transitions = np.zeros((len(self.Q), len(sentence)))
        # Forward calculation
        for i, token in enumerate(sentence):
            observation = 0
            if token in self._reversed_V:
                observation = self._reversed_V[token]

            if i == 0:
                for index, _ in enumerate(self.Q):
                    probability = self.Pi[index] * self.B[index][observation]
                    probabilities[index][i] = probability
                    transitions[index][i] = -1
            else:
                for index, _ in enumerate(self.Q):
                    candidates = []
                    previous = probabilities[:, i - 1]
                    for previous_index, previous_probability in enumerate(previous):
                        probability = (
                            previous_probability
                            * self.A[previous_index][index]
                            * self.B[index][observation]
                        )
                        candidates.append(probability)

                    probabilities[index, i] = np.max(candidates)
                    transitions[index, i] = np.argmax(candidates)

        # Choose best probability path
        best_path = []  # type: List[int]
        best_probabilities = []  # type: List[float]
        for i in reversed(range(len(sentence))):
            probability = np.max(probabilities[:, i])
            max_index = int(np.argmax(probabilities[:, i]))
            best_probabilities.append(probability)
            if i == len(sentence) - 1:
                # Last state
                best_path.append(max_index)
            if i > 0:
                # Previous state
                previous = int(transitions[max_index, i])
                best_path.append(previous)

        best_path = best_path[::-1]  # reverse the order
        best_probabilities = best_probabilities[::-1]  # reverse the order
        return (best_path, best_probabilities)