Zero Crossings as an Effective Feature In Speech Recognition for Embedded Applications

Motivation: About a couple of months back i was wondering on designing a speaker dependent speech recognizer on the 8051 micro-controller or any of its derivatives for simple machine control. We would of course need an isolated word (or digit) recognizer.

Problem: Speech recognizers can be implemented using Hidden Markov Models or Artificial Neural Networks. There are plenty of such systems in place. However the problem with these algorithms is that they are computationally pretty intensive, and thus can not be implemented on a simple 8 bit fixed point micro-processor, and that is what we need for simple machine control applications. So there is a need for a simpler algorithm.

All these algorithms also employ a short term feature vector to take care of the non-stationary nature of speech. Generally the vector length is so chosen that the nature of the signal in this band is quasi-stationary. Feature vectors are an area of active research. Generally however at the university level, Mel Frequency Cepstrum Coefficients (MFCC) or Linear Predictive Coefficients are taken as features. These too require computations that are beyond the scope of a simple processor/ micro controller like the 8051.

Solution: I was thinking what could be done to reduce this burden and choose a simpler feature so that it could be implemented on 8051. While researching on this i came across a paper[1]. This papers deals with this problem exactly!

The researchers have used only zero crossings of the speech signal to determine the feature vector. Since this novel feature extraction method is based on zero crossings only, it just needs a one bit A to D conversion[2]. This feature extraction is computationally very simple and does not require the speech signal to be pre-processed.

This feature vector is basically the histogram of the time interval between successive zero-crossings of the utterance in a short time window[1]. These feature vectors for each window are then combined together to form a feature matrix. Since we are dealing with only small time series (isolated words), we can employ Dynamic Time Warping to compare the input matrix with the reference matrix’ stored. I will discuss this in another post sometime.

To obtain this vector the following steps need to be followed.

1. The speech signal x(t) is band-pass filtered to give s(t).

2. s(t) is then subjected to infinite amplitude clipping with the help of a ZCD to give u(t).

3. u(t) is then sampled at say 8Khz to give u[n]. The feature extraction is carried out on u[n].

4. u[n] is divided in a number of short time windows for every one of the calculated W samples.

5. The histogram for each of this short time window is found. The histogram(or vector) is found as follows: The number of times ONLY ONE sample is recorded between successive zero crossings will constitute the element number 1 of the vector. The number of times ONLY TWO samples are recorded between successive zero crossings will constitute the element number two of the feature vector and so on. In this way we construct an histogram which is an appropriate feature vector.

These vectors then can be combined for all windows to get the feature matrix. These as i said earlier can be compared using DTW/DDTW/Fast DTW or some other algorithm.

As an example take an utterance for the number three in Hindi which is spoken as “teen”. The first plot below gives the waveform for the utterance. The second plot gives the end-point detected version of the same, end point detection reduces computations (and hence the memory required) by removing the “useless” portions of the utterance which do not contain any intelligence.

The surface plot for the above utterance by me for the matrix (where, as i have mentioned implicitly the rows represent the windows and the columns represent the histogram terms) prepared is as:

References:

[1] A Microprocessor based Speech Recognizer for Isolated Hindi Digits, Ashutosh Saxena and Abhishek Singh, IEEE ACE.

[2] Zero-Crossing-Based Linear Prediction for Speech Recognition, Lipovac, Electronics Letters, pages 90-92, vol. 25 Issue 2,19 Jan 1989.

Onionesque Reality Home >>

Advertisement

Read Full Post »

Arthur Clarke is No More

Just a few weeks back in an article i had mentioned Arthur Clarke commenting on the Orion. I woke up today morning with the news that the celebrated thinker, novelist, writer had passed away in his Sri Lankan home due to heart failure.

I have read quite a few of his fictional works. I started reading his works at the age of 10. He thought ahead of the present generation. His famous works included 2001:A Space Odyssey. After military service in the great war Clarke wrote a lot of fictional stories and technical papers. His writings he Exploration of Space (1951) and The Promise of Space (1968 ) made him very famous for the concept of a geostationary satellite. The International Astronomical Union recognizes a geostationary satellite as a Clarke orbit. The idea of space elevator is also associated with him. I would not count on his achievements anymore. His detailed biography can be found here.

This is sad news, though not unexpected. He had recorded a good bye message for friends on his 90th birthday. Maybe he saw it coming. A legend is no more between us.

Onionesque Reality Home >>

Read Full Post »

Altruism in Animals

One of the problems that Swarm Intelligence research faces is a precise definition[1]. Many words that are associated with SI are generally Emergence, Self-Organization, Collective Intelligence etc. There is no general mathematical definition to it yet. This lack of a credible and workable framework has made research in this field ad-hoc. In simple words we need a theory to swarming. Is there a theory to swarming behavior or swarm intelligence? We basically have analogies. There is no theory yet i guess.

There have been efforts to rectify this and i will cover this in a post sometime soon.

However we also definitely need a theory to explain altruism in social insects (In a swarm), in animals or in Humans. I basically got interested in Altruism due to my interest in Swarm Intelligence and social insects.

Why does a honey bee do the ultimate sacrifice and lay down its life when it feels its kin is in danger? Why do walruses adopt orphans? How is it that dogs can adopt off-springs of cats, other dogs, and even tigers? There are scores of examples that show such altruistic behavior.There are variants obviously to the altruism that we are talking about.

Altruism as i have mentioned implicitly is a social behavior. A behavior is social if it has implications for both the actor and the recipient. Social behaviors can broadly be categorized depending on whether the actor or the recipients are benefited. Altruism is the category when the fitness level of the actor is reduced after a action and that of the recipient is increased. A selfish behavior contrasts the above exactly. Other two types are mutually beneficial and spiteful. Mutually beneficial is the type in which the fitness of both are increased and spiteful is the reverse of it.

In The God Delusion, Richard Dawkins summarizes some kinds of altruism and separates them and also gives some explanation.

1. The first kind he points out is altruism towards our kin, with individuals with whom we have common genes. The honey bee example in most probability fits into this “category”. Also like how we are evolved to be kind towards our kids. The genes that “code” for such behavior towards our kins people who share genes with us are more likely to survive. This is given by Hamilton’s Kin Selection Theory[2]. It states that altruism is favored when:

Where “c” is the fitness cost to the altruist, “b” is the fitness benefit to the recipient and “r” is a measure of their genetic relatedness.

2. The second kind is reciprocal altruism. The example of a buffalo / crow pair fits in here. This form does not require any sharing of genes. Individuals from VERY different species can actually exist in a symbiotic relationship through this altruistic form. Each individual contributes something that the other individual can not obtain on its own. Within a species, like in us humans, this trait has become more specific and has evolved into the form that we tend to do good to people who do/ can do good things for us.

3. Dawkins then also talks about the importance of building a good reputation.

4. One of the most interesting reasons that he mentions and which is very true IMO is that excessive altruism may be a show of superiority in some manner. That is that it can be because the person can afford to be “altruistic” This can in some way be understood as a payoff in a game theory scenario.

One interesting approach to the questions above is discussed in a nice paper that i read over the past week.

In this paper the two researchers, in their model consider a large and panmictic (unstructured) population where individuals interact pairwise in successive rounds.

Assumptions:

1. Number of rounds of interaction for an individual follows a geometric distribution with a parameter ω, which is a probability that an individual will interact with an individual after a round of interaction.
2. The Focal Individual can interact with two classes of individuals, one closely related genetically to it and the other not so closely related.
3. X is the probability of interacting non-randomly with an individual of the related class.
4. 1-X is the complimentary probability. 1− X interactions occur randomly with any member of the population.

All repeated rounds of interactions take place with the same partner. During each round of interaction the FI invests I• into helping with I• varying between 0 and 1. This investment incurs a cost CI• to the FI and generates a benefit BI• . A fraction ζ of the benefit generated by helping directly return to the FI and the complementary fraction 1−ζ goes to the partner[3].

The fecundity of FI can either be positive or negative depending on the value of the term:

ζBI• – CI•

The fecundity of the partner will always be positive unless the FI gets all the benefit of the act (i.e. ζ=1 ) or if it does not invest in helping at all (I• = 0). We noted earlier that the FI is interacting with two classes of individuals. And therefore the fecundity with both these classes of individuals will be different.

To generalise the relative fecundity of the FI interacting with a j class individual will be given by:

We assume that the individual follows a “tit for tat” kind of a approach i.e. that the investment level into helping at a given round depends linearly on the partner’s investment at the previous round. Hence, the investment depends on three traits:

1. the investment on the first round τ
2. The response slope β on the partner’s investment for the preceding round.
3. The memory m (varying between zero and one) of the partner’s investment at the preceding round.

“m” is the probability of not making an error in assignment by considering that a partner has not co-operated in the previous move when he infact has. τ and β can evolve. The paper gives a well put and terse presentation of the idea to generate a formula and then considers cases when co-operation and when altruism can evolve. I highly recommend this paper. It is a wonderful paper and a must read! I thoroughly enjoyed it. It can be obtained here.
The same problem has also been approached by Richard Dawkins comprehensively in the following video that was shown on the BBC. This video has been obtained courtesy of richarddawkins.net

In the video Dawkins starts off with how his seminal book “The Selfish Gene” was misunderstood and how it lead to the phrase “Nice Guys Finish Last”, this phrase was coined by Garrett Hardin to sum up the selfish gene idea. Then how do these “nice guys/altruistic agents” survive? Should not have natural selection wiped them off? Dawkins then argues that the idea of selfish genes can actually give rise to co-operative and altruistic behavior*. It leads to the development of a pre-wired programme or strategy for achieving some desired goal. This is analogous to human strategy in situations. Dawkins then moves to game theory and gives a wonderful explanation of the Prisoners Dilemma and concepts like the tragedy of the commons and tries to explain how altruistic behavior (coupled with a tit for tat kind learning behavior) can actually fetch best pay-offs. It is this “selfish” advantage that actually leads to altruistic behavior. And finally suggests that Hardin’s idea could be slightly modified after this analysis to “Nice Guys Finish First”, which also is the name of the programme.
To sum up, this wonderful video leads to the same conclusion in part as the paper described above does.

That is that the following conditions lead to the evolution of
altruism and cooperation :

1. Direct benefits to the individual performing a cooperative act.

2. Direct or indirect information allowing a better than random guess about whether a given individual will behave cooperatively in repeated reciprocal interactions.

3. Altruism or cooperation can evolve if the cost-to-benefit ratio of altruistic and cooperative acts is greater than a threshold value. The cost-to-benefit ratio can be altered by coercion, punishment and policing which therefore act as mechanisms facilitating the evolution of altruism and cooperation. [3] Dawkins explained this idea by the PD example in the video.

However integrating the four ideas mentioned at the start of the post is a problem. Can it be possible to do so? This can have massive implications in understanding social insect behavior and swarm intelligence among many others.

* Co-operative behavior may not always be altruistic.

References:

[1] Foundations of Swarm Intelligence: From Principles to Practice, Mark Fleischer, Institute for Systems Research, University of Maryland College Park.

[2] The genetical evolution of social behaviour. Hamilton, W. D. 1964. I. Journal of Theoretical Biology 7:1-16.

[3] The evolution of cooperation and altruism. A general framework and a classification of models. Laurent Lehmann and Laurent Keller.

Onionesque Reality Home >>

Read Full Post »

The {Grass} is Always Greener on the Other Side

A couple of years back when i was in the process of shock recovery. I used to have a 30 page-long collection of nerdy jokes. Sadly, I lost that book one Diwali .

Those jokes went on their way to ethernity, and from that long list, I can only recall one joke word to word:

The phosphor CRT monitor is always greener on the other side.

Onionesque Reality Home >>

Read Full Post »

Hidden Answers

Pictures, videos and other visual inputs can be very misleading. We sometimes think that pictures reveal their stories easily, which is not the case!

As an example take a little story of Harold C Urey.

Urey has been one of the most respected physical chemists in history. He has been known for his pioneering work related to isotopes, particularly heavy Hydrogen or Deuterium. He was awarded the Nobel prize in Chemistry in 1934.

After he had already won the Nobel and was considered a giant he set out on the discovery for an understanding of the origin of the moon. He had huge pictures of the moon and the lunar landscape in his office and would look at them day after day. It was only after a year that he started seeing new things in the same pictures, things and patterns that he never thought existed.

I am not a Nobel winner ;) , but i have had such experiences and i am sure most of us did too, with certain pictures that we had to look over long periods of time. The amount of information in a picture or a video is so massive that we can take a lot of time to find out the abstract hidden patterns that lie in it.

_____

As a bonus to the above story, have a look at this rare film of Harold Urey. Here he talks about what he thought about a theory of the origin of the Moon (i.e that the Moon was formed by detachment of huge quantities of mass from the Earth and the pacific basin was a ‘scar’ of this change)

_____

Possibly Related:

To think what nobody had yet thought By Rod.

Onionesque Reality Home >>

Read Full Post »