Re: Question
Federico Miyara <[email protected]> Tue, 20 May 2025 03:19:22 -0300
| Newsgroups | gmane.comp.gnu.glpk |
|---|---|
| Message-ID | <[email protected]> |
This is a multi-part message in MIME format.
--------------yxgALWZkT0uL6I4H402AoKlg
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 8bit
Thank you, Reginald and Michael, for paying attention to my problem.
First of all, and since I'm replying to the list after some private
conversation with Reginald (very interesting, by the way), I'll try
first to clarify the motivations, and then remove the anecdotal
information leaving the bare mathematical problem so that it is easier
to cast it into an adequate conceptual framework. If too boring, go to
paragraph 6 or 7.
My problem is to get lists of phonetically balanced words for use in
intelligibility tests (either in an audiological context, an
architectural acoustics one or a communication receiver one).
Phonetically balanced means that the phonemes appear in the list of
words with approximately the same probability as they appear in general
language usage. This way, the test exposes the subject or patient to a
situation similar to natural language speech with far less utterances.
There is a number of observations. First, the probabilities of the
phonemes are drawn from statistics over some corpus. Second, the
dictionary from which the words of my target lists are taken may or may
not be the same set of words used in the corpus. For instance, may be I
want to include all the words of a general dictionary as potential
members of the lists or that for different reasons I wish to limit it to
a subset, for instance, the 2000 words more frequently used, the words
with two syllables, or the words used in a given context (for instance a
local community, a profesional specialty).
The process that converts words into groups of phonemes, called
phonemic transcription, is not straightforward but for my purposes we
can assume it has been performed previously. The process of getting the
statistics of appearance in the corpus is really straightforward and we
can also assume it has been already performed. Notice that the
probabilities might also be imposed arbitrarily (for instance, for an
experiment one might want to exaggerate the probability of certain
particular phonemes).
Let's call the phonemes "symbols"; the set of all phonemes, "alphabet";
any (typically short) sequence of symbols, "word"; the set from which
the words that form the target list are taken, "dictionary". Let p =
[p(1), ..., P(n) ] be the vector of probabilities corresponding to the
vector of symbols [S(1), ..., S(n)]
Then the problem can be stated as follows:
Given an alphabet of n symbols S(1), ..., S(n) and a dictionary D
containing N words of variable length, generate a list L of M words such
that the probability of finding symbol S(k) in the list matches as
better as possible some given probabilities p(k) or, symbolically,
SUM ( |P(s = S(k) / s belongs to L) - p(k)| ) = min { SUM ( |P(s =
S(k) / s belongs to Li) - p(k)| ) }
where P is the probability and the minimum is taken over all possible
M-word lists Li that can be taken from D. The SUM operator is over k =
1, ..., n, and could be replaced by the sum of squares or any other
suitable metrics. Note that "s belongs to L" is abuse of language, short
for "s belongs to a word belonging to L".
Typically the words are restricted, for example, to disyllables. This is
transparent to the problem, since the dictionary can be cropped to
reflect such restriction. Of course, the symbols may and will repeat.
Note also that the words in the list shouldn't be repeated, the M words
should be different.
Hope this clarifies the problem.
Best regards,
Federico Miyara
On 19/5/2025 23:59, Reginald Beardsley wrote:
>
> FWIW Below is my attempt at disambiguating the problem. I have *some*
> confidence it is an accurate description, but assert no more. I've not
> had a reply from Federico yet, but expect one soon.
>
> Translating a word problem into a mathematical problem is fraught with
> peril. Much of my career was spent helping people convert their word
> problem into a mathematical problem. Most of the time they immediately
> knew how to solve the problem after I asked some questions and gave
> them the proper mathematical formulation. My English lit BA degree had
> broad application to PhD level mathematics. Go figure. I'd never
> expected that.
>
> From a series of emails with Federico, I *think* this is an accurate
> description:
>
> Given phoneme frequencies for all of a language, e.g. Spanish, how
> does one select the best combination of repetitions of a subset of the
> entire lexicon to best match the phoneme distribution of the entire
> language? The goal being evaluating verbal intelligibility in speech
> communication. It looks to me to be a straight forward linear error
> minimization problem.
>
> This seems to me a classic sparse L1 program as described in a paper
> by Emanuel Candes which he called it "The Dantzig Selector" in the
> early 2000s as an application of sparse L1 pursuits. I am acutely
> interested in whether that is correct. Not merely in the solution of
> Federico's problem, but my own understanding of sparse L1 pursuits as
> I learned from Focuart and Rauhut's "A Mathematical Introduction to
> Compressive Sensing." Having worked for 3 years without almost no one
> with whom to converse, I'm less than confident I have all the nuances
> correct. If I am wrong, I should very much appreciate an explanation.
> I no longer have the pleasure of doing this as an occupation, but
> money was never what motivated me.
>
> My perception is that the solution is straight forward, but tedious to
> implement because of size. The obvious solution to me is, write a
> program to generate a GMPL file. I *think* it is a mixed integer
> problem, but not yet convinced that's the best formulation.
>
> I am very grateful for the assistance provided by this list 8-10 years
> ago and should very much enjoy contributing something useful. GLPK is
> a true "tour de force". Many thanks to Andrew et al.
>
> Have Fun!
> Reg
> ----- Forwarded Message -----
> *From:* Reginald Beardsley <[email protected]>
> *To:* Federico Miyara <[email protected]>
> *Sent:* Monday, May 19, 2025 at 12:10:37 PM CDT
> *Subject:* Re: Question
>
> Federico,
>
> Is this a correct statement of your problem?
>
> You have a dictionary of N words composed of various elements from a
> set of M symbols each of which has a certain number of occurrences in
> the N words. The number of symbols from M which form an word in the
> set N varies but is small.
>
> You wish to determine the number of recurrences of a smaller subset of
> P words which have the same proportion of the M symbols as the entire
> set of N words, but with P << N. Further, you wish to be able to
> select different subsets of P words that all have the best matched
> frequency of occurrence of the M symbols in P as in N with Q
> selections from P. The particular sets of P words in each case being
> chosen independently based on other criteria unrelated to the
> frequency of occurrence of the M symbols in N.
>
> The desired output is a list of the number of occurrences of each word
> in the set P which best approximates the number of occurrences of the
> M symbols in the set N for Q selections from the list M for the case Q
> >= P.
>
> The fundamental problem is then constructing Ax=y where y is the
> vector of probabilities of each element in M in N. The vector x is a
> integer valued number of repetitions of words in P. The hard part is
> creating the correct A matrix.
>
> Have Fun!
> Reg
> On Friday, May 16, 2025 at 04:55:34 PM CDT, Federico Miyara
> <[email protected]> wrote:
>
>
>
> I need to solve the following problem:
>
> I have an alphabet of n symbols and a dictionary with N words of m
> symbols (n in the order of tens, N in the order of tens of thousands, m
> = 4, say)
>
> Assuming each symbol has a definite probability, I need to generate a
> list of M words (M in the order of 100) taken from the dictionary in
> which the proportion of each symbol matches as best as possible the
> required probability.
>
> Is this a problem that can be solved using GLPK?
>
> Thanks.
>
> Bes regards,
>
> Federico Miyara
>
> --
> Este correo electrónico ha sido analizado en busca de virus por el
> software antivirus de Avast.
> www.avast.com
>
--
Este correo electrónico ha sido analizado en busca de virus por el software antivirus de Avast.
www.avast.com
--------------yxgALWZkT0uL6I4H402AoKlg
Content-Type: text/html; charset=UTF-8
Content-Transfer-Encoding: 8bit
<html>
<head>
<meta http-equiv="Content-Type" content="text/html; charset=UTF-8">
</head>
<body>
<br>
Thank you, Reginald and Michael, for paying attention to my problem.<br>
<br>
First of all, and since I'm replying to the list after some private
conversation with Reginald (very interesting, by the way), I'll try
first to clarify the motivations, and then remove the anecdotal
information leaving the bare mathematical problem so that it is
easier to cast it into an adequate conceptual framework. If too
boring, go to paragraph 6 or 7.<br>
<br>
My problem is to get lists of phonetically balanced words for use in
intelligibility tests (either in an audiological context, an
architectural acoustics one or a communication receiver one).
Phonetically balanced means that the phonemes appear in the list of
words with approximately the same probability as they appear in
general language usage. This way, the test exposes the subject or
patient to a situation similar to natural language speech with far
less utterances. <br>
<br>
There is a number of observations. First, the probabilities of the
phonemes are drawn from statistics over some corpus. Second, the
dictionary from which the words of my target lists are taken may or
may not be the same set of words used in the corpus. For instance,
may be I want to include all the words of a general dictionary as
potential members of the lists or that for different reasons I wish
to limit it to a subset, for instance, the 2000 words more
frequently used, the words with two syllables, or the words used in
a given context (for instance a local community, a profesional
specialty).<br>
<br>
The process that converts words into groups of phonemes, called
phonemic transcription, is not straightforward but for my purposes
we can assume it has been performed previously. The process of
getting the statistics of appearance in the corpus is really
straightforward and we can also assume it has been already
performed. Notice that the probabilities might also be imposed
arbitrarily (for instance, for an experiment one might want to
exaggerate the probability of certain particular phonemes). <br>
<br>
Let's call the phonemes "symbols"; the set of all phonemes,
"alphabet"; any (typically short) sequence of symbols, "word"; the
set from which the words that form the target list are taken,
"dictionary". Let p = [p(1), ..., P(n) ] be the vector of
probabilities corresponding to the vector of symbols [S(1), ...,
S(n)] <br>
<br>
Then the problem can be stated as follows: <br>
Given an alphabet of n symbols S(1), ..., S(n) and a dictionary D
containing N words of variable length, generate a list L of M words
such that the probability of finding symbol S(k) in the list matches
as better as possible some given probabilities p(k) or,
symbolically,<br>
<br>
SUM ( |P(s = S(k) / s belongs to L) - p(k)| ) = min { SUM (
|P(s = S(k) / s belongs to Li) - p(k)| ) }<br>
<br>
where P is the probability and the minimum is taken over all
possible M-word lists Li that can be taken from D. The SUM operator
is over k = 1, ..., n, and could be replaced by the sum of squares
or any other suitable metrics. Note that "s belongs to L" is abuse
of language, short for "s belongs to a word belonging to L".<br>
<br>
Typically the words are restricted, for example, to disyllables.
This is transparent to the problem, since the dictionary can be
cropped to reflect such restriction. Of course, the symbols may and
will repeat.<br>
<br>
Note also that the words in the list shouldn't be repeated, the M
words should be different.<br>
<br>
Hope this clarifies the problem.<br>
<br>
Best regards,<br>
<br>
Federico Miyara <br>
<br>
<br>
<br>
<div class="moz-cite-prefix">On 19/5/2025 23:59, Reginald Beardsley
wrote:<br>
</div>
<blockquote type="cite"
cite="mid:[email protected]">
<meta http-equiv="content-type" content="text/html; charset=UTF-8">
<div> <br>
FWIW Below is my attempt at disambiguating the problem. I have
*some* confidence it is an accurate description, but assert no
more. I've not had a reply from Federico yet, but expect one
soon.<br>
<br>
Translating a word problem into a mathematical problem is
fraught with peril. Much of my career was spent helping people
convert their word problem into a mathematical problem. Most of
the time they immediately knew how to solve the problem after I
asked some questions and gave them the proper mathematical
formulation. My English lit BA degree had broad application to
PhD level mathematics. Go figure. I'd never expected that.<br>
<br>
From a series of emails with Federico, I *think* this is an
accurate description:<br>
<br>
Given phoneme frequencies for all of a language, e.g. Spanish,
how does one select the best combination of repetitions of a
subset of the entire lexicon to best match the phoneme
distribution of the entire language? The goal being evaluating
verbal intelligibility in speech communication. It looks to me
to be a straight forward linear error minimization problem.<br>
<br>
This seems to me a classic sparse L1 program as described in a
paper by Emanuel Candes which he called it "The Dantzig
Selector" in the early 2000s as an application of sparse L1
pursuits. I am acutely interested in whether that is correct.
Not merely in the solution of Federico's problem, but my own
understanding of sparse L1 pursuits as I learned from Focuart
and Rauhut's "A Mathematical Introduction to Compressive
Sensing." Having worked for 3 years without almost no one with
whom to converse, I'm less than confident I have all the nuances
correct. If I am wrong, I should very much appreciate an
explanation. I no longer have the pleasure of doing this as an
occupation, but money was never what motivated me.<br>
<br>
My perception is that the solution is straight forward, but
tedious to implement because of size. The obvious solution to me
is, write a program to generate a GMPL file. I *think* it is a
mixed integer problem, but not yet convinced that's the best
formulation.<br>
<br>
I am very grateful for the assistance provided by this list 8-10
years ago and should very much enjoy contributing something
useful. GLPK is a true "tour de force". Many thanks to Andrew et
al.<br>
<br>
Have Fun!<br>
Reg<br>
</div>
<div class="yahoo_quoted" style="margin:10px 0px 0px
0.8ex;border-left:1px solid #ccc;padding-left:1ex;">
<div style="font-family:'Helvetica Neue', Helvetica, Arial,
sans-serif;font-size:13px;color:#26282a;">
<div>----- Forwarded Message -----</div>
<div><b>From:</b> Reginald Beardsley
<a class="moz-txt-link-rfc2396E" href="mailto:[email protected]"><[email protected]></a></div>
<div><b>To:</b> Federico Miyara
<a class="moz-txt-link-rfc2396E" href="mailto:[email protected]"><[email protected]></a></div>
<div><b>Sent:</b> Monday, May 19, 2025 at 12:10:37 PM CDT</div>
<div><b>Subject:</b> Re: Question</div>
<div><br>
</div>
<div>
<div id="yiv6790832716">
<div>
<div> Federico,<br clear="none">
<br clear="none">
Is this a correct statement of your problem?<br
clear="none">
<br clear="none">
You have a dictionary of N words composed of various
elements from a set of M symbols each of which has a
certain number of occurrences in the N words. The
number of symbols from M which form an word in the set
N varies but is small.<br clear="none">
<br clear="none">
You wish to determine the number of recurrences of a
smaller subset of P words which have the same
proportion of the M symbols as the entire set of N
words, but with P << N. Further, you wish to be
able to select different subsets of P words that all
have the best matched frequency of occurrence of the M
symbols in P as in N with Q selections from P. The
particular sets of P words in each case being chosen
independently based on other criteria unrelated to the
frequency of occurrence of the M symbols in N.<br
clear="none">
<br clear="none">
The desired output is a list of the number of
occurrences of each word in the set P which best
approximates the number of occurrences of the M
symbols in the set N for Q selections from the list M
for the case Q >= P. <br clear="none">
<br clear="none">
The fundamental problem is then constructing Ax=y
where y is the vector of probabilities of each element
in M in N. The vector x is a integer valued number of
repetitions of words in P. The hard part is creating
the correct A matrix.<br clear="none">
<br clear="none">
Have Fun!<br clear="none">
Reg<br clear="none">
</div>
<div id="yiv6790832716yqt35542"
class="yiv6790832716yqt9332962494">
<div style="margin:10px 0px 0px 0.8ex;border-left:1px
solid #ccc;padding-left:1ex;"
class="yiv6790832716yahoo_quoted">
<div style="font-family:'Helvetica Neue', Helvetica,
Arial, sans-serif;font-size:13px;color:#26282a;">
<div> On Friday, May 16, 2025 at 04:55:34 PM CDT,
Federico Miyara <a class="moz-txt-link-rfc2396E" href="mailto:[email protected]"><[email protected]></a>
wrote: </div>
<div><br clear="none">
</div>
<div><br clear="none">
</div>
<div>
<div dir="ltr"><br clear="none">
</div>
<div dir="ltr">I need to solve the following
problem:<br clear="none">
</div>
<div dir="ltr"><br clear="none">
</div>
<div dir="ltr">I have an alphabet of n symbols
and a dictionary with N words of m<br
clear="none">
</div>
<div dir="ltr">symbols (n in the order of tens,
N in the order of tens of thousands, m<br
clear="none">
</div>
<div dir="ltr">= 4, say)<br clear="none">
</div>
<div dir="ltr"><br clear="none">
</div>
<div dir="ltr">Assuming each symbol has a
definite probability, I need to generate a<br
clear="none">
</div>
<div dir="ltr">list of M words (M in the order
of 100) taken from the dictionary in<br
clear="none">
</div>
<div dir="ltr">which the proportion of each
symbol matches as best as possible the<br
clear="none">
</div>
<div dir="ltr">required probability.<br
clear="none">
</div>
<div dir="ltr"><br clear="none">
</div>
<div dir="ltr">Is this a problem that can be
solved using GLPK?<br clear="none">
</div>
<div dir="ltr"><br clear="none">
</div>
<div dir="ltr">Thanks.<br clear="none">
</div>
<div dir="ltr"><br clear="none">
</div>
<div dir="ltr">Bes regards,<br clear="none">
</div>
<div dir="ltr"><br clear="none">
</div>
<div dir="ltr">Federico Miyara<br clear="none">
</div>
<div dir="ltr"><br clear="none">
</div>
<div dir="ltr">--<br clear="none">
</div>
<div dir="ltr">Este correo electrónico ha sido
analizado en busca de virus por el software
antivirus de Avast.<br clear="none">
</div>
<div dir="ltr"><a class="moz-txt-link-abbreviated" href="http://www.avast.com">www.avast.com</a><br clear="none">
</div>
<div dir="ltr"><br clear="none">
</div>
</div>
</div>
</div>
</div>
</div>
</div>
</div>
</div>
</div>
</blockquote>
<br>
<div id="DAB4FAD8-2DD7-40BB-A1B8-4E2AA1F9FDF2"><br /><table style="border-top: 1px solid #D3D4DE;"><tr><td style="width: 55px; padding-top: 13px;"><a href="https://www.avast.com/sig-email?utm_medium=email&utm_source=link&utm_campaign=sig-email&utm_content=emailclient" target="_blank"><img src="https://s-install.avcdn.net/ipm/preview/icons/icon-envelope-tick-round-orange-animated-no-repeat-v1.gif" alt="" width="46" height="29" style="width: 46px; height: 29px;"/></a></td><td style="width: 470px; padding-top: 12px; color: #41424e; font-size: 13px; font-family: Arial, Helvetica, sans-serif; line-height: 18px;">Libre de virus.<a href="https://www.avast.com/sig-email?utm_medium=email&utm_source=link&utm_campaign=sig-email&utm_content=emailclient" target="_blank" style="color: #4453ea;">www.av
ast.com</a></td></tr></table><a href="#DAB4FAD8-2DD7-40BB-A1B8-4E2AA1F9FDF2" width="1" height="1"> </a></div></body>
</html>
--------------yxgALWZkT0uL6I4H402AoKlg--