3
$\begingroup$

I have done some AI projects involving inference, neural networks, etc., but I'm not sure what the right algorithm would be for this problem.

  • Say there is a set of pills, where each type is visually unique. So, for example, a pain reliever might be a red pill and an allergy medication might be a blue pill. One is seeing all of these pills for the first time and they are unlabeled, so you don't know what the red pill is or the blue pill is for, other than that you know know all red pills are the same and that they are all different from blue pills.

  • The way you are given new pills is that some assortment is put into a bag according to type (e.g., 2 allergy pills, 3 pain pills, 5 sleeping pills) and you take one from the bag at random. You are told what the assortment is, so when you pull a red pill from the bag you know (independent from anything else) that there was a 20% chance for it to have been allergy, 30% pain, etc.

  • This process repeats itself with new independent bags and different percentages, so that you can make inferences about the function of the pill, such as knowing that you pulled a red from an {allergy (20%), pain(30%), sleeping(50%)} bag and another red from an {allergy(90%), pain (5%), antibiotic(5%)} bag means that it's either allergy or pain with allergy being more likely. Testing a pill to rule out possibilities of labels is possible, e.g., to completely rule out the possibility that a green pill is a pain pill.

So, how would I set up some sort of inference engine to track this sort of thing?

The output would be, for each of the colors, a percentage value for how likely it is to have a given label based on all of the information known at that point. The system would need to handle being given new random draw events with the new result and underlying percentages, along with events where labels are ruled out or confirmed outside of the random drawings.

I could probably figure out how to do the individual calculations using conditional probability, but I want to make an efficient algorithm to do it automatically. If it matters, I would be planning on implementing this in Python.

$\endgroup$
1
$\begingroup$

You could treat the sample of colors as being drawn from a Multinomial distribution with parameters given as percentages i.e. $\{\text{#red}, \text{#yellow}, \text{#blue}\} \sim Multi(\alpha_{\text{pain}}, \alpha_{\text{allergy}}, \alpha_{\text{sleeping}})$. You don't know which $\alpha$ corresponds to which color, but you could find the mapping of colors that maximizes the likelihood by exhaustive search. This, admittedly naive, strategy would be very simple to implement in any language. However, it would only be feasible for a relatively small number, $N$, of pill types as the search space is $O(N!)$. Also, there could be uninformative samples (e.g. similar probabilities for several pills).

The interventions could help in reducing the search space and distributions of pills with high entropy. I assume there is a cost to testing the pills so you would want a balance between the cost of a smaller search space and less entropy and the cost of enumerating all the possibilities. This now introduces a whole new area of literature related to a famous model--the Multi-armed Bandit. However, simply testing when there are pills with similar probabilities within some threshold may be enough.

$\endgroup$
1
$\begingroup$

Model each color pill as a multinomial distribution (as Sameer says) over functions (whose natural parameter is the total log probability of the pill having that function). With each draw, you add the bag's log-probabilities to the appropriate color's multinomial distribution parameters. This Bayesian evidence combination is called a "product of experts" by some people.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.