@Override
	public Iterable<Token> determineMostLikelyTags(Iterable<Token> sentence) {
		List<Map<String, Double>> matrix = new ArrayList<>();
		Map<String, List<String>> paths = createPath();
		Iterator<Token> tokenIter = sentence.iterator();
		
		// initialize base cases (t == 0)
		String firstToken = tokenIter.next().getText();
		for (String tag : tagSet) {
			double startProb = languageModel.beginningOfSentenceTagProbability(tag);
			double emitProb = languageModel.tokenProbability(firstToken, tag);
			put(matrix, 0, tag, Math.log(startProb * emitProb));
			paths.get(tag).add(tag);
		}
		
		// run Viterbi for t > 0
		int i = 0;
		while (tokenIter.hasNext()) {
			String token = tokenIter.next().getText();
			i++;
			
			Map<String, List<String>> newPaths = createPath();
			for (String tag : tagSet) {
				double maxProbLog = Double.NEGATIVE_INFINITY;
				String prevTagWithMaxProb = null;
				for (String prevTag : tagSet) {
					double prevProbLog = matrix.get(i-1).get(prevTag);
					double transProb = languageModel.tagTransitionProbability(prevTag, tag);
					double emitProb = languageModel.tokenProbability(token, tag);
					double overallProbLog = prevProbLog + Math.log(transProb * emitProb);
					if (overallProbLog > maxProbLog) {
						maxProbLog = overallProbLog;
						prevTagWithMaxProb = prevTag;
					}
				}
				put(matrix, i, tag, maxProbLog);
				List<String> extended = new ArrayList<>(paths.get(prevTagWithMaxProb));
				extended.add(tag);
				newPaths.put(tag, extended);
			}
			
			paths = newPaths;
		}
		
		double maxProbLog = Double.NEGATIVE_INFINITY;
		String lastTagForMaxState = null;
		for (String tag : tagSet) {
			double probLog = matrix.get(i).get(tag);
			if (probLog > maxProbLog) {
				maxProbLog = probLog;
				lastTagForMaxState = tag;
			}
		}
		
		List<String> path = paths.get(lastTagForMaxState);
		List<Token> result = new ArrayList<>();
		i = 0;
		for (Token oldToken : sentence) {
			Token newToken = new Token(path.get(i), oldToken.getText());
			result.add(newToken);
			i++;
		}
		return result;
	}